- •Державний комітет зв’язку та інформатизації
- •Перелік умовних позначень
- •Розділ 1 аналіз закономірностей побудовИk-значних статичних мікроелектронних структур
- •1.1. Термінологічний аналіз та обґрунтування принципу симбіозу
- •1.2. Архітектурно-логічні побудови цифрових іk-значних структур
- •1.3. Дослідження архітектур просторових цифрових комутаторів
- •1.4. Завдання аналiзу та оцiнки надiйностik-значних структур
- •1.5. Математичні моделіk-значного кодування
- •1.6. Методи і засобиk-значного кодування з надлишком
- •1.7. Дослідження метричних властивостейk-значних кодів
- •1.8. Вибір перспективних шляхів побудови просторовихk-значних структур
- •Висновки до першого розділу
- •Розділ 2 узагальнена теорія побудови високоефективних просторових статичниХk-значних структур
- •2.1. Структураk-значної площинно-просторової комірки
- •2.2. Формалізація принципу симбіозу багатовходовихk-значних структур
- •2.3. Метричні властивостіk-значних комутацiйних структур
- •2.4. Аналіз узагальнених статистичних параметрівk-значних структур
- •2.5. Аналiз точності дії статичнихk-значних структур
- •Висновки до другого розділу
- •Розділ 3 методи оцінки параметрів каналів іЗk-значним кодуванням
- •3.1. Ентропійні параметри k-значних каналів без завад
- •3.2. Властивості симетричних каналів ізk-значним кодуванням
- •3.3. Імовiрнiсть помилки пiд час декодуванняk-значних систематичних кодiв
- •3.4. Необхідна вносима надлишковість статичних просторовихk-значних структур
- •Висновки до третього розділу
- •Розділ 4 моделі, алгоритми та структурИk-значного кодування систематичними кодами
- •4.1. Математичні моделі кодування кодами Ріда – Соломона з крос-перемежуванням (circ-кодами)
- •4.2. Математичні моделі декодуванняCirc-кодів
- •4.3. Синтез алгоритмівk-значного кодування/декодування
- •4.4. Способи організації обчислень та синтезу структур операційних засобівCirc-кодера/декодера
- •4.5. Аналіз принципів побудови та дії двокаскадногоCirc-декодера
- •4.6. Порівняльний аналіз cтратегій декодуванняCirc-декодерів
- •Висновки до четвертого розділу
- •Розділ 5 принципи побудовИk-значних просторових пристроїв зовнішнього обміну (пзо)
- •5.1. Класифікації просторовихk-значних структур
- •5.2. Узагальнений рекурсивний структурний та формальний синтез пзо
- •5.3. Методи побудови рекурсивних струмових та потенційних пзо
- •5.4. Синтез просторових комутаторівk-значних сигналів
- •Висновки до п’ятого розділу
- •Розділ 6 математичні моделі, методи і структурні побудови універсальних функціональних перетворювачів (уфп) просторового типу
- •6.1. Моделі та методи структурного синтезу просторових уфп
- •6.2. Математичні моделі комбінаційного синтезу проміжних дешифраторів уфп
- •6.3. Моделі та методи структурного синтезу в асп просторових уфп
- •6.4. Моделі та методи синтезу в асп проміжних дешифраторів уфп
- •6.5. Моделі та методи синтезу в асп багатовходових уфп
- •Висновки до шостого розділу
- •Розділ 7 синтез та реалiзацiя k-значних операцiйних пристроїв новітніх обчислювальних систем
- •7.1. Класифікація операційних пристроїв
- •7.3. Чотиризначний матричний множник елементів поляґалуаGf(28)
- •7.4. Побудова паралельного конвеєрного арифметичного пристрою
- •7.5. Метод та засоби регенеруванняk-значних цифрових послiдовностей
- •Далі, оскільки сигнал має цифрову форму, то
- •Висновки до сьомого розділу
- •Основнi результати роботи та висновки
- •Список використаних джерел
1.5. Математичні моделіk-значного кодування
У науцi та технiцi сьогодення теорiя кодування базується переважно на двозначних зображеннях кодiв і використовується здебільшого термiнологiя та методи, що випливають із бiнарного зображення iнформацiї. В окремих роботах [120 - 126] автори дають загальнi визначення k-значного коду як вiдображення скiнченних чи зчисленних множин об’єктiв довiльної природи в множини послiдовностей із цифр <0, 1, ..., k– 1>, де k – деяке цiле додатне число (зокрема, k= 2). Практичних результатiв мало [1, 2, 127–129] і тому методи теорiї k-значного кодування вимагають відповідного опису, узагальнення й розвитку. З іншого боку, тільки в теорії інформації та кодування знаходимо ті першооснови, які від самого початку як формальні математичні поняття використовують k-значні основи і системи числення. Отже, теорія k-значного кодування випливає зі стику двох дисциплін, двох теорій: k-значної логіки та теорії інформації і кодування.
Попередньо дамо низку визначень та позначень, що вживаються при k-значному кодуваннi. Коди характеризують цiлий ряд параметрiв, cеред яких основними є довжина n, число iнформацiйних символiв r, = r / n, кодова вiддаль d та ймовiрнiсть помилки Pпом [127–129].
Нехай Ek – довiльний алфавiт. Елементи алфавiту Ek назвемо літерами, а скiнченнi послiдовностi, складенi з літер, – словами в Ek. Довжина (число літер) слова позначимоn(). Для елементiв алфавiту справедливi теоретико-множиннi операцiї об’єднання, перетину, рiзницi та прямого добутку множин.
Довiльне вiдображення множини M повiдомлень у множину слiв у алфавiтi Ek будемо називати k-значним кодуванням множини М.
Коди, що частину знакiв використовують для передачi iнформацiї (тодi як iншi знаки використовуються для перевiрки та виправлення помилок) і мають кодовi комбiнацiї однакової довжини, називають систематичними k-значними кодами.
У рамках цього розділу розглядаються такі параметри, характеристики та методи теорії k-значного кодування: перепускна здатнiсть каналiв із k-значним кодуванням у присутностi завад [1, 2, 127–129]; ентропiя фактично переданих послiдовностей k-значним систематичним кодом; верхня межа числа можливих послiдовностей, що передаються (n, r)-k-значними кодами з корекцiєю помилок [2] та оцiнки ймовiрностi помилки пiд час приймання k-значних коректуючих кодiв.
Одним з основних завдань теорії передачі інформації є визначення залежності швидкості передачі даних та перепускної здатності параметрів каналу, характеристик сигналів і завад [1, 2]. Швидкість передачі даних у каналі з k-значним кодуванням визначається, за К. Шенноном [1], як середня кількість інформації, що передається каналом за одиницю часу. Найвищу, теоретично доступну для даного каналу швидкість передачі інформації назвемо перепускною здатністю каналу з k-значним кодуванням.
У каналах без завад, для тривалості інформаційного кодового імпульсу i, кількість інформації в повідомленні, що триває Т, буде дорівнювати [58]:
, (1.12)
де I (X) – кількість інформації у повідомленні Х, Т – тривалість повідомлення; i– тривалість інформаційного кодового імпульсу.
Оскільки повний цикл k-значного повідомлення містить у собі k імпульсів тривалості i, то , а вираз (1.12) у граничному випадку перепишеться для повногоk-значного сповіщення як
. (1.13)
За наявності завад обсяг інформації, що передається каналом із k-значним кодом та просторовою k-значною структурною організацією, опишеться з допомогою моделі К. Шеннона ентропією сповіщення в каналах із завадами [1] таким виразом:
, (1.14)
де H (t, k) – структурна надійність k-значних структур.
Створення статичних k-значних просторових структур вимагає вирішення задачі забезпечення їх надійності. Ця обставина висуває на перший план дослідження та розробку методів забезпечення і підвищення надійності k-значних структур. Одним із найефективніших методів підвищення надійності є надлишкове кодування, що базується на застосуванні різних класів кодів зі знаходженням та виправленням помилок. Вибір таких методів для теоретичних досліджень визначається тим, що вони дозволяють виявити й усунути відмови та збої в каналах зв’язку, як зовнішніх, так і апаратних, у пристроях пам’яті, логічних елементах та структурах, арифметичних операційних пристроях тощо. Методи базуються на специфіці ентропійних моделей k-значних апаратурних каналів, а не на моделях інформаційних каналів зовнішнього зв’язку, отже, природним чином враховують особливості порушень k-значного структурного алфавіту за рахунок порушення алгоритму роботи k-значної структури.
Коди, що частину знакiв використовують для передачi iнформацiї (тодi як iншi знаки використовуються для перевiрки та виправлення помилок) і мають кодовi комбiнацiї однакової довжини, називають систематичними k-значними кодами, або (r, n)-кодами.
Для кодiв, що коректують r помилок та великого числа елементiв n у кодовiй комбiнацiї p = r/n, тому ентропiя фактично переданих послiдовностей запишеться так:
. (1.15)
Вiдповiдно [1, 2] верхня межа перепускної здатностi передачi iнформацiї апаратурним каналом зі систематичним k-значним коректуючим кодом є такою:
. (1.16)
Величина ймовірності помилки p символу в k-значному апаратурному каналі визначається [48] через його структурну надійність як:
, (1.17)
де L = ,k – значність; – інтенсивність структурних завад в апаратурному каналі;t – середній час безвідмовної роботи каналу.
Діапазон зміни p, у свою чергу, дає можливість визначити й діапазон зміни табульованих значень U залежно від зміни відповідних параметрів і характеристик k-значного апаратурного каналу.
Якщо помилки в k-значному повiдомленнi виникають незалежно одна вiд одної, то їх розподiл пiдпорядковується бiномному розподiловi. У цьому разі ймовiрнiсть враження кожного символу послiдовностi є постiйною величиною i ймовiрнiсть помилкового приймання для універсальних просторових статичних k-значних елементів та структур визначається згідно з (1.17). Імовiрнiсть помилки Рпом пiд час декодування k-значних систематичних кодiв для даного числа символiв n та числа помилок r, що коректуються, описується [2] спiввiдношенням:
, (1.18)
де i – кратнiсть помилки в послiдовностi.
Для аналiзу та розрахункiв ймовiрностi помилки пiд час розпізнавання k-значних коректуючих кодiв в апаратурному каналі використовується [2] така форма запису даного розподiлу:
. (1.19)