- •Державний комітет зв’язку та інформатизації
- •Перелік умовних позначень
- •Розділ 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.7. Дослідження метричних властивостейk-значних кодів
1.7.1. Метричні властивості систематичних кодів. Як показав К. Шеннон [1], завадостiйкiсть передачi повiдомлення на вiддаль забезпечується зі заданою мiрою ймовiрностi шляхом уведення надлишковостi, причому для виправлення r помилок k-значний символ потрібно повторити m = 2r+1 разів. Звiдси необхiдно випливає ще один параметр метрики k-значного коду – мiнiмальна кодова вiдстань d, або те число позицiй, у яких вiдрiзняються мiж собою два кодових слова. Нагадаємо, що невід’ємна функція d(X, Y) називається відстанню, чи метрикою, в деякій множині Ek, якщо для довільних упорядкованих елементів X, Y, Z із Ek виконуються такі властивості: d(X, Y) = 0 тоді, і тільки тоді, коли X = Y; d(X, Y) = d(Y, X); d(X, Y) d(X, Z) + d(Y, Z). k-значний код із мiнiмальною кодовою вiдстанню d дозволяє вiдшукати d – 1 помилок чи одночасно скоректувати довiльну конфiгурацiю з t стирань та r помилок за умови, що d > 2r + t + 1.
Верхня межа [2] числа можливих послiдовностей М для k-значного коду з надлишковiстю, що коректує r помилок, визначається як
, (1.21)
де М – число можливих послiдовностей (n, r)-коду; k – значнiсть коду; n – число розрядiв коду; – число сполучень зn по m; m = ;r – число помилок, що коректується.
Доведення. Число послiдовностей, що вiдрiзняється вiд довiльної даної послiдовностi на один знак, дорiвнює (k– 1), де перший множник – це число сполучень із n по одному, а k– 1 – число значень сповiщення, що можуть на данiй позицiї зайняти мiсце сигналу, що передається. При рiзницi у двох знаках даної послiдовностi число таких послiдовностей становитиме (k– 1)2. Тут (k–1)2 –число можливих пар сигналiв, що можуть зайняти мiсця сигналiв, які передаються. Далi, продовжуючи за iндукцiєю, можна за наявностi r знакiв записати значення (k– 1)r. Очевидно, що для числа послiдовностей М, якi рiзняться одна вiд одної не менше нiж на 2r + 1 знакiв, можна вказати верхню межу як нерiвність (1.21), де kn – загальне число послiдовностей.
1.7.2. Метричні властивості k-значних двомісних функцій. Процедури синтезу k-значних комутацiйних логiчних структур передбачають наявнiсть двовходових (двовимiрних) мультиплексорiв, якi працюють із k-значним структурним алфавiтом, що приймає значення з множини Ek= {0, 1, ..., k – 1}, і реалізують двомісні функції k-значної логіки. За наявностi розробки унiверсального одновходового k-значного функцiонального перетворювача [82], на його основi можна синтезувати дво- та багатовходовi мультиплексори, якi, при фiксованому налагодженнi базисних сигналiв одновходового мультиплексора, володiють багатофункцiональнiстю [76]. Комутацiйнi властивостi двовходового мультиплексора можуть бути описанi суперпозицiєю одномiсних функцiй k-значної логiки так [3]:
, (1.22)
де f () –довiльна фiксована функцiя з (– множина всiх функцiй двохk-значних змiнних); –функцiя, що реалiзується одновходовим унiверсальним елементом чи мультиплексором (пробiгає всю множину функцiй ізоднiєї змiнної).
Усi функції визначенi на Ek зi значеннями також в Ek = {0, 1, ..., k – 1}. Суперпозицiєю функцiй iз Pk називається:
довiльна функцiя, яка отримується зі системи функцiй однієї змінної Pk шляхом замiни змiнних;
будь-яка функція, що отримується шляхом заміни змінних із функції
,
де – суперпозиція функцій системиPk і/або є(тут не припускається, що всі функціїрізні).
Для прикладу, при k = 3, функції f() можуть бути поданi у формі таблиць істинності двох видiв:
Таблиця 1.1
Таблиця істинності тризначної функції (вид 1)
|
000 |
111 |
222 |
|
012 |
012 |
012 |
|
210 |
021 |
000 |
Таблиця 1.2
Таблиця істинності тризначної функції (вид 2)
f() |
| |||
0 |
1 |
2 | ||
|
0 |
2 |
1 |
0 |
1 |
0 |
2 |
1 | |
2 |
0 |
0 |
0 |
Максимально можливе число рiзних комутацiйних функцiй, що реалiзуються двоходовим мультиплексором i описуються суперпозицiєю (1.22), залежить вiд виду фiксованої функції налагодження f() та обмежене зверху величиною [3].
У роботі [76] отримано низку оцiнок для трьох базисних для синтезу k-значних комутацiйних структур функцiй виду max (x1, x2), min (x1, x2), (x1, x2)modk щодо числа рiзних функцiй, якi реалiзуються суперпозицiєю (1.22). Річ у тому, що такi суперпозиції породжують k2k комутацiйних функцiй, але не всi вони попарно рiзнi. Ось чому розроблення алгоритму визначення числа попарно рiзних функцiй, що породжуються суперпозицiєю (1.22), є фундаментальною проблемою для синтезу k-значних комутацiйних структур. Фундаментальнiсть такої оцiнки пов’язана з проблемою функцiональної повноти систем k-значних логiчних (комутацiйних) функцiй та є NP-cкладною задачею. Зокрема, проблема оптимального вибору виду фiксованого налагодження f() дозволяє, як наслiдок, вибрати й оптимальний функцiонально повний набiр з погляду мiнiмуму необхiдних значень iз Ek при максимумi можливих варiантiв попарно рiзних комутацiйних функцiй. Проблема формування оптимальних функцiонально повних базисiв для k-значної логiки надзвичайно складна [3], мало дослiджена, хоча на даний момент набуває щораз більшого значення з погляду створення апаратних і програмних обчислювальних засобiв штучного інтелекту.
У зв’язку з «комбiнаторним вибухом», що супроводжує спроби вирiшення поставленої задачi методом прямого перебору, необхiдно розробити вiдповiдні методи розбиття на класи еквiвалентностi, що не перетинаються, множини функцiй f() і пiддаються пiдрахунку та дослiдженню. Адже загальне число функцiй для довiльного налагодження двовходового мультиплексора оцiнюється величиною і вже дляk = 3 становить величину 19 683, що гальмує подальшi пошуки та дослiдження як із використання k-значних систем числення, так i розроблення засобiв на цiй основi.
Частковий результат, отриманий у [76], щодо оцiнки числа рiзних функцiй, які породжуються суперпозицiями ,тає для перших двох суперпозицiй такий:
, (1.23)
де i – iндекс розбиття множини Pk1 на класи еквiвалентностi такi, що до класу Qk-i вiдносяться тi з них, якi приймають з Ek значення не менше за k– i та не належать до класу Qk-l (l < i).
Для останньої суперпозицiї (суми за модулем k) отримано [76] напiвемпiричну залежнiсть такого виду:
. (1.24)
Як видно з наведених виразiв, результати досліджень метричних властивостей k-значних двомісних функцій отриманi на даний момент дуже скромнi й частковi – тiльки для суттєво упорядкованих суперпозицiй, i тому вимагають подальшого узагальнення та розвитку.