- •Державний комітет зв’язку та інформатизації
- •Перелік умовних позначень
- •Розділ 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 результати роботи та висновки
- •Список використаних джерел
2.2. Формалізація принципу симбіозу багатовходовихk-значних структур
Для того, щоби в узагальненому вигляді аналітично описати та сформулювати принцип симбіозу в просторових k-значних структурах, укажемо, що присвоювання значень алфавіту Ek {0, 1, 2, ..., k– 1} здійснюється за рахунок вхідних сигналів X {0, 1, 2, ..., k– 1}. У загальному випадку кожному станові вхідного сигналу X відповідає певне значення вихідного сигналу Y{0, 1, 2,...,k–1}. Функціональний перетворювач є багатополюсником, що має n входів і один вихід, який відображає прямий добуток n множин {x}i (i = 1, 2, ..., n) на множину {y}. Об’єднання множин називається вхідним алфавітом, а множинаY – вихідним.
В узагальненому вигляді універсальні просторові k-значні структури [16-50, 77-88], згідно з узагальненим способом завдання функцій k-значної логіки з допомогою таблиць істинності [3, 4] та принципу симбіозу [140] дво- та багаторівневого кодування і засобів, включають до свого складу такі компоненти: паралельний аналого-цифровий перетворювач (елемент розпізнавання k-значної змінної); дешифратор (ДШ), селектор, комутатор, паралельний цифро-аналоговий перетворювач (ключовий комутатор, або підсумовувач струмів).
Елемент розпізнавання k-значної змінної (один пороговий елемент розпізнавання поодинокого k-значного рівня) реалізує предикат [148]:
, (2.1)
де t – двозначна (логічна) змінна; X – k-значна вхідна змінна; kі {0, 1, ..., k–1}, i - і-те значення k-значної змінної.
Оскільки рівнів k, то і вихідних сигналів розпізнавання для просторового набору порогових елементів буде k: t0, t1, t2, ..., tk– 1 {0, 1}.
За допомогою ДШ на другому етапі здійснюється перехід до двозначного просторового відображення результату розпізнавання. Введемо такі позначення для формалізації алгоритму: t1 ... tk– 1 – сигнали прямих виходів компараторів; – сигнали інверсних виходів компараторів; & – операція кон’юнкції;– вихідні сигнали розпізнаванняk-значних змінних, що приймають значення з множини E2 {0, 1}.
Логіку роботи дешифраторів описує така система предикатних рівнянь:
(2.2)
Вихідні сигнали першого та другого розпізнавачів вхідних змінних надходять на входи селектора матричного для однозначного встановлення відповідності кортежу вхідних сигналів X1X2 ... Xn для кожного значення таблиці істинності k-значної функції.
Логіку роботи селектора матричного у випадку двовходової одновихідної універсальної k-значної структури (рис. 2.2) описує така система рівнянь алгебри скінченних предикатів:
(2.3)
де fmn – вихідні сигнали матричного селектора, що приймають значення з множин E2 {0, 1}, m, n = Ek {0, 1, ..., k – 1}.
Комутатор для двовходової універсальної k-значної структури є двовимірним просторовим утворенням, що має дві групи по k входів двовходових елементів І, на першу з яких надходять сигнали t від дешифратора схеми керування, а на іншу – від селектора. Відповідні виходи елементів І об’єднані разом і утворюють виходи комутатора. Формально, в явному вигляді, робота просторового комутатора описується такою системою рівнянь алгебри скінченних предикатів:
(2.4)
Рис. 2.2. Двовходова універсальна k-значна просторова структура
Для тривходової універсальної структури просторового типу тримісної k-значної функції з її таблиці істинності (табл. 2.1) випливає внутрішня потреба в таких структурних одиницях: три набори алфавітних розпізнавачів, що складаються з порогових елементів (ПЕ, компараторів) із дешифраторами, тривимірні просторові селектор і комутатор та схема керування вибором виду реалізованої функції.
Логіку роботи матричного селектора у випадку n = 3 описує така система із k рівнянь:
(2.5)
Порівняно з одно- та двовходовою структурою [86, 87], тривимірний матричний селектор (рис. 2.3) складається із k груп двовимірних селекторів, побудованих на тривходових елементах І. Дві групи входів елементів І підключені до відповідних виходів алфавітних розпізнавачів X1 та X2, а третя група входів, у кожній з k груп, підключена до виходів алфавітного розпізнавача змінної X3. У кінцевому підсумку маємо в тривимірному селекторі kn виходів, що відповідає числу fmnp у таблиці істинності. Усі kn виходів необхідні для здійснення однозначного автоматичного вибору значень fmnp (m, n, p Ek = {0, 1, ..., k – 1}), використовуючи просторовий характер дії розпізнавачів вхідних змінних.
Рис. 2.3. Структура селектора тривходового функціонального перетворювача
Таблиця 2.1
Узагальнена таблиця істинності тримісної k-значної функції
x3 |
0 |
0 |
… |
0 |
|
1 |
… |
1 |
… |
k– 1 |
k– 1 |
… |
k– 1 |
x2 |
0 |
1 |
… |
k– 1 |
0 |
1 |
… |
k– 1 |
… |
0 |
1 |
… |
k– 1 |
0 |
f000 |
f010 |
… |
f0(k – 1)0 |
f001 |
f011 |
… |
f0(k – 1)1 |
… |
f00(k – 1) |
f01(k – 1) |
… |
f0(k – 1)(k – 1) |
1 |
f100 |
f110 |
… |
f1(k – 1)0 |
f101 |
f011 |
… |
f1(k – 1)1 |
… |
f10(k – 1) |
f11(k – 1) |
… |
f1(k – 1)(k – 1) |
. |
. |
. |
… |
. |
. |
. |
… |
. |
… |
. |
. |
… |
. |
. |
. |
. |
… |
. |
. |
. |
… |
. |
… |
. |
. |
… |
. |
. |
. |
. |
… |
. |
. |
. |
… |
. |
… |
. |
. |
… |
. |
k – 1 |
f(k – 1)00 |
f(k – 1)10 |
… |
f(k – 1)(k – 1)0 |
f(k – 1)01 |
f(k – 1)11 |
… |
f(k – 1)(k – 1)1 |
… |
f(k – 1)0(k-1) |
f(k – 1)1(k-1) |
… |
f(k – 1)(k – 1)(k – 1) |
x1 |
f |
-
77
Для керування роботою комутатора із kn вихідних сигналів селектора формується k груп по k2 виходів, у кожний такт роботи селектора активним є тільки один вихід із kn.
Формально, в явному вигляді, робота просторового комутатора, у разі n = 3, описується такою системою рівнянь алгебри скінченних предикатів:
для першої площини комутатора при нульових значеннях X3 та керуючих сигналах y4, що відповідають будь-якому значенню із Ek = {0, 1, ..., k – 1}:
(2.6)
для другої площини комутатора при одиничних значеннях X3 та керуючих сигналах y4, що відповідають будь-якому значенню із Ek = {0, 1, ..., k – 1}:
(2.7)
для k-ї площини комутатора при k– 1-му значенні X3 та керуючих сигналах y4, що відповідають будь-якому значенню із Ek = {0, 1, ..., k – 1}:
(2.8)
Структурно комутатор для реалізації тримісної функції теж є тривимірним просторовим утворенням, що має k площин матричних комутаторів розмірності k2 k. На перший вимір (на k2 рядків КМ) надходить один із сигналів від селектора, а на другий (на k стовпців КМ) – від входу керування вибором виду реалізованої функції. Третій вимір виникає через те, що змінна X3 утворює в таблиці істинності k субтаблиць розмірності k2 значень fmnp і в процесі пробігання змінною X3 Ek = {0, 1, ..., k– 1} викликає відповідну просторову зміну площини селекції та площини k2 вихідних сигналів селектора. Такий підхід зберігає однорідність проміжних просторових перетворювачів та величину затримки в один такт на кожному з них. Можливе інше вирішення [108] алгоритму дії та структури комутатора з використанням базової моделі (див. рис. 1.6) ієрархічних бан’яноподібних комутаційних структур, але з втратою незмінності затримки на один такт проміжних перетворень.
Таким чином, структурно будь-яка площина комутатора може бути реалізована на базі матриці розмірності k2 k двовходових елементів І, на один вхід яких надходять сигнали , а на інший – fmnp. Один вхід для k2 сигналів fmnp достатній, оскільки в кожному такті роботи структури в цілому можлива поява тільки одного з них. Багатовходова функція АБО в такому разі реалізується без додаткових затрат із допомогою шинного об’єднання всіх k2 cигналів fmnp. Відповідно вихідні сигнали комутатора в цілому будуть утворені за рахунок провідного АБО сигналів із однаковими індексами, але з різних площин комутації:
(2.9)
Остаточний результат універсального перетворення формально можна подати у вигляді операторного зображення:
, (2.10)
де <g0, g1, ..., gk–1> = PSf – сигнали налагоджень вихідних функцій універсальної структури.
Отже, зростання значності та числа вхідних змінних універсальної k-значної структури веде до суттєвих змін у побудові компонентів, що входять до її складу. Зокрема, на вході структури зростає пропорційно k число елементів розпізнавання; структури селекторів і комутаторів перетворюються в n-вимірні об’ємно-просторові утворення, а на виході структури зростає пропорційно k число ключів. Таким чином, в узагальненому вигляді універсальна просторова структура (рис. 2.4) може бути описана такою системою ознак SPVPS, де V – об’єм (вимірність простору селектора і комутатора).
Вирішення задач формалізації принципів організації багатовходових k-значних структур забезпечує побудову новітньої концепції синтезу структур для високошвидкісних обчислювальних систем; застосування просторового та часового паралелізму на структурному й алгоритмічному рівнях та k-значних методів кодування; створення процедурних і функціональних мов, паралельних машин баз знань і логічного виводу.
Рис. 2.4. Узагальнена структурна схема тривходового універсального просторового функціонального перетворювача