ДЕРЖАВНИЙ КОМІТЕТ ЗВ’ЯЗКУ ТА ІНФОРМАТИЗАЦІЇ

УКРАЇНИ

НАЦІОНАЛЬНА АКАДЕМІЯ НАУК УКРАЇНИ

ДЕРЖАВНИЙ НАУКОВО-ДОСЛІДНИЙ ІНСТИТУТ ІНФОРМАЦІЙНОЇ ІНФРАСТРУКТУРИ

На правах рукопису

УДК 519.95: 621.324: 681.3(07)

КОНОПЛЯНКО Зеновій Дмитрович

ТЕОРІЯ ПОБУДОВИ І КОДУВАННЯ ПРОСТОРОВИХ

k-ЗНАЧНИХ СТРУКТУР

Спеціальність 01.05.02 —математичне моделювання та

обчислювальні методи

Дисертацiя

на здобуття наукового ступеня

доктора технічних наук

Науковий консультант:

доктор технічних наук, професор,

Бондаренко М.Ф.

ЛЬВІВ 2005

ЗМІСТ

ПЕРЕЛІК УМОВНИХ ПОЗНАЧЕНЬ 5

ВСТУП 7

РОЗДІЛ 1. АНАЛІЗ ЗАКОНОМІРНОСТЕЙ ПОБУДОВИ k-ЗНАЧНИХ СТАТИЧНИХ МІКРОЕЛЕКТРОННИХ СТРУКТУР 21

1.1. Термінологічний аналіз та обґрунтування принципу симбіозу 21

1.2. Архітектурно-логічні побудови цифрових і k-значних структур 26

1.3. Дослідження архітектур просторових цифрових комутаторів 35

1.4. Завдання аналiзу та оцiнки надiйностi k-значних структур 41

1.5. Математичні моделі k-значного кодування 47

1.6. Методи і засоби k-значного кодування з надлишком 51

1.7. Дослідження метричних властивостей k-значних кодів 55

1.8. Вибір перспективних шляхів побудови просторових k-значних структур 59

Висновки до першого розділу 66

РОЗДІЛ 2. УЗАГАЛЬНЕНА ТЕОРІЯ ПОБУДОВИ ВИСОКОЕФЕКТИВНИХ ПРОСТОРОВИХ СТАТИЧНИХ k-ЗНАЧНИХ СТРУКТУР 69

2.1. Структура k-значної площинно-просторової комірки 69

2.2. Формалізація принципу симбіозу багатовходових k-значних структур 72

2.3. Метричні властивості k-значних комутацiйних структур 82

2.4. Аналіз узагальнених статистичних параметрів k-значних структур 89

2.5. Аналiз точності дії статичних k-значних структур 94

Висновки до другого розділу 97

РОЗДІЛ 3. МЕТОДИ ОЦІНКИ ПАРАМЕТРІВ КАНАЛІВ ІЗ k-ЗНАЧНИМ КОДУВАННЯМ 99

3.1. Ентропійні параметри k-значних каналів без завад 99

3.2. Властивості симетричних каналів із k-значним кодуванням 102

3.3. Імовiрнiсть помилки пiд час декодування k-значних систематичних кодiв 107

3.4. Необхідна вносима надлишковість статичних просторових k-значних структур 116

Висновки до третього розділу 122

РОЗДІЛ 4. МОДЕЛІ, АЛГОРИТМИ ТА СТРУКТУРИ k-ЗНАЧНОГО КОДУВАННЯ СИСТЕМАТИЧНИМИ КОДАМИ 124

4.1. Математичні моделі кодування кодами Ріда — Соломона з крос-перемежуванням (CIRC-кодами) 124

4.2. Математичні моделі декодування CIRC-кодів 129

4.3. Синтез алгоритмів k-значного кодування/декодування 134

4.4. Способи організації обчислень та синтезу структур операційних засобів CIRC-кодера/декодера 141

4.5. Аналіз принципів побудови та дії двокаскадного CIRC-декодера 148

4.6. Порівняльний аналіз cтратегій декодування CIRC-декодерів 157

Висновки до четвертого розділу 162

РОЗДІЛ 5. ПРИНЦИПИ ПОБУДОВИ k-ЗНАЧНИХ ПРОСТОРОВИХ ПРИСТРОЇВ ЗОВНІШНЬОГО ОБМІНУ (ПЗО) 164

5.1. Класифікації просторових k-значних структур 164

5.2. Узагальнений рекурсивний структурний та формальний синтез ПЗО 168

5.3. Методи побудови рекурсивних струмових та потенційних ПЗО 177

5.4. Синтез просторових комутаторів k-значних сигналів 185

Висновки до п’ятого розділу 192

РОЗДІЛ 6. МАТЕМАТИЧНІ МОДЕЛІ, МЕТОДИ І СТРУКТУРНІ ПОБУДОВИ УНІВЕРСАЛЬНИХ ФУНКЦІОНАЛЬНИХ ПЕРЕТВОРЮВАЧІВ (УФП) ПРОСТОРОВОГО ТИПУ 195

6.1. Моделі та методи структурного синтезу просторових УФП 195

6.2. Математичні моделі комбінаційного синтезу проміжних дешифраторів УФП 201

6.3. Моделі та методи структурного синтезу в АСП просторових УФП 208

6.4. Моделі та методи синтезу в АСП проміжних дешифраторів УФП 211

6.5. Моделі та методи синтезу в АСП багатовходових УФП 220

Висновки до шостого розділу 226

РОЗДІЛ 7. СИНТЕЗ ТА РЕАЛIЗАЦIЯ k-ЗНАЧНИХ ОПЕРАЦIЙНИХ ПРИСТРОЇВ НОВІТНІХ ОБЧИСЛЮВАЛЬНИХ СИСТЕМ 229

7.1. Класифікація операційних пристроїв 229

7.2. Паралельний нагромаджувальний підсумовувач k-значних AN + B-кодів 233

7.3. Чотиризначний матричний множник елементів поля ґалуа GF(2⁸) 239

7.4. Побудова паралельного конвеєрного арифметичного пристрою 248

7.5. Метод та засоби регенерування k-значних цифрових послiдовностей 253

Висновки до сьомого розділу 259

ОСНОВНI РЕЗУЛЬТАТИ РОБОТИ ТА ВИСНОВКИ 261

СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ 265

ДОДАТКИ 283

ПЕРЕЛІК УМОВНИХ ПОЗНАЧЕНЬ

АСП - алгебра скінчених предикатів;

АЦП - перетворювач аналого-цифровий ;

АП - пристрій арифметичний;

БК - блок керування;

ЛЕ - елемент логiчний;

БОС - система багатопроцесорна обчислювальна;

БЧХ - коди Боуза-Чоудхурі-Хоквінгема;

ВСВ - вiдхилення вiдносне середньоквадратичне;

ВС - відбивач струму;

ДДНФ - досконала диз’юнктивна нормальна форма;

ДБС - джерело базисних сигналів;

ДС - структура двозначна;

ДШ - дешифратор;

ЕФ - функція елементарна;

ЕЗЛ - логіка емітерно-зв’язана та технологiя схем;

ЕОМ - електронно-обчислювальна машина;

ЙБР - ймовірність безвідмовної роботи;

I²Л - логіка інтегральна інжекційна;

КМ - комутатор;

КМОН — комплементарний транзистор, виготовлений за технологією метал-окисел-напівпровідник;

ЛСК - логiчна схема комутацiї;

МС - селектор матричний;

НВІС - надвелика інтегрована схема;

ОБПЕ - елемент одновходовий k-значний потенційний;

ПЕ - елемент пороговий;

ПК - аргумент із плаваючою комою;

ПЗО - пристрій зовнiшнього обмiну;

ПЗП - пристрій постійний запам’ятовуючий;

T - структура - деревоподібна структура;

ТТЛ - транзисторно-транзисторна логіка та технологія схем;

УФП - перетворювач унiверсальний функціональний;

ФК - аргумент із фіксованою комою;

ФОП - процесор функціонально орієнтований;

ЦАП - перетворювач цифро-аналоговий;

ЦЕОМ - машина цифрова електронно-обчислювальна;

ШІ - інтелект штучний;

k - значність структурного алфавіту, основа системи числення визначені на множині E_k 0= {0,1,..., k-1};

S - статична ознака (кожному з символiв k-значного структурного алфавiту ставиться у вiдповiднiсть один із рiвнiв напруги чи струму);

P - просторова ознака (символи алфавiту зображаються збудженим станом одного з k просторових полюсiв);

D - динамiчна ознака (символам алфавiту вiдповiдають певнi iнтервали часу для вибраного виду перiодичних послiдовностей iмпульсiв;

 - предикат розпізнавання букви а чи просто розпізнавання букви а, що залежить від змінної x_i;

P(t,k) - надійність схемна чи ймовірність того, що за час t не відбудеться раптова відмова k-значних структур;

R(t,k) - надійність параметрична чи ймовірність того, що за час t не відбудеться параметрична відмова k-значних структур;

H(t,k) - надiйнiсть структурна чи ймовірність того, що не відбудуться ні параметричні, ні раптові відмови k-значних структур за час t;

CIRC-код - (Cross-Interleaved Reed-Solomon Code) - k-значний код Рiда-Соломона з кросперемежуванням;

- коефіцієнт надлишковості.

ВСТУП

k-значними називають структури цифрових та радiоелектронних систем обробки iнформацiї, що утворенi множиною k-значних елементiв і множиною відповідних зв’язків, і які використовують k-значне кодування. При всій своїй привабливості, процес створення, побудови та застосування k-значних структур і кодування затягнувся, якщо зауважити те, що їх першооснови закладені в теорії інформації та k-значній логіці К. Шенноном, Варшавером Б.А. і Яблонским С.В. [1-4] ще у 50-х роках минулого століття. Причиною до цього стало, із одного боку, відсутність повної, завершеної теорії їх побудови, а із іншого - невизначеність задач (середовищ), для яких вкрай необхідні такі структури. Таким чином, очевидні можливості, переваги та позитивні ефекти від застосування k-значних елементів і структур до цього часу так і не знайшли широкого втілення в життя. Завдання створення та застосування
k-значних структур і кодування очевидним чином збігається із задачею структурного узгодження різних фундаментальних теорій (формальної логіки, комбінаторики, кодування, ймовірностей, надійності, синтезу автоматів, інформації, кібернетики, інтелекту тощо), їх трансформації та узгодження із тим середовищем де природним чином виникає задача побудови k-значних структур та їх застосування.

На сьогоднішній день таким середовищем, можливо і єдиним, є інтелектуальні інформаційні системи, у яких, починаючи з рівня застосування природної мови [5 - 8], на повний зріст постає питання про необхідність застосування k-значної логіки, структур і кодування. Визначившись із середовищем, якому необхідні k-значних структур легше визначитись, якими ж властивостями та характеристиками вони повинні володіти і за якими принципами будуватись. З іншого боку, бурхливий розвиток комп’ютеризації, проникнення обчислювальної техніки в усі сфери науки, промисловості, суспільного життя, її використання для рішення найскладніших задач сьогодення вступили в протиріччя з технологією оброблення даних традиційними нойманівськими комп’ютерами, спостерігається криза її основ, пов’язана з специфікою архітектури та принципів дії нойманівського процесора з застосуванням послідовних алгоритмів роботи та виключно двозначних елементів, структур і кодування. Перелічені проблеми вимагають вирішення задач розвитку нових принципів організації елементів, структур і методів кодування для обчислювальних систем, зокрема систем штучного інтелекту (ШІ).

Людський мозок зберігає об’єктивну модель світової реальності, інакше людина не змогла б еволюціонувати та вдосконалюватись у процесі свого розвитку. Природно, напрошується висновок про доцільність моделювання принципів дії людського мозку для задач створення ШІ. Оскільки всі розумові здібності, що необхідно передати машині із ШІ вже наявні в людини на достатньо високому рівні розвитку, і ніякий інший інтелект, крім людського, науці недоступний, то міркувати машини повинні за тими ж законами, що й людина. Нейрофізіологічні дослідження принципів дії природного інтелекту мозку людини виявили у ньому наявність дво- та k-значного кодування, просторового характеру активності мереж нервових клітин і організації діяльності мозку [9 - 15].

Звідси випливають основні вимоги щодо властивостей базових елементів і структур для побудови новітніх високоефективних систем ШІ. Вони повинні реалізувати функції k-значної логіки та кодування, володіти властивостями універсальності, просторовості, гібридності, гнучкого переналагодження без зміни структури, ієрархічності, за складністю бути порівнянні із складністю вирішуваних задач. Найближчими за вказаними властивостями є k-значні універсальні просторові елементи та структури і розвитку цих засобів надається велика увага в усьому світі [16, 17].

Розробка теорiї та iнженерних методiв проектування k-значних елементiв та структур розпочалась з 50-х рокiв i цей процес не припиняється ось уже більше третини століття. У 70-х роках ряд зарубіжних фiрм (Signetics, Texas Instruments, Fairchild Camera and Instrument Corp., Hitachi та Fhilips) почали вести iнтенсивнi розробки iнтегрованих схем із застосуванням k-значної логiки. У 80-х роках у нас в Україні теж були розробленi та виготовленi дослiднi зразки першої мiкросхеми з використанням k-значної логiки на базi I²Л-схемотехнiки. За період 1970-2005 рр. проведено 35 мiжнародних симпозiумiв із k-значної логiки (International Symposium on Multiple-Valued Logic (ISMVL)), організаторами яких були Association for Computing Machinery, IEEE Computer Society, а також університети США, Канади, Японії та інших держав світу [18 - 46].

Запропонована значна кількість підходів та методів побудови і застосування k-значних структур, проте відсутні їх систематизація та упорядкована система засобів реалізації, недостатньо опрацьовані принципи їх побудови і методи кількісної та якісної оцінки застосування під час створення високошвидкісних обчислювальних систем, що свідчить про недостатній рівень розвитку теорії побудови таких структур. Подальший прогрес суттєво залежить від узагальнення і систематизації на єдиній методологічній основі накопиченого досвіду, розвитку й удосконалення системи понять.

Для k-значних елементів і структур, відповідних для створення високошвидкісних обчислювальних систем, необхідний новий підхід, нова теоретична база їх побудови, тому недостатньо тільки досліджень у галузі однієї науки. Тобто, дослідження окремо методів синтезу, кодування, комбінаторики, надійності та точності не дають відповіді на питання оптимального шляху побудови відповідних за властивостями k-значних структур. Справа в тому, що усі перелічені теорії утворюють замкнуті математичні системи і ті істини, що ними породжуться не дають всебічного і єдиного підходу до побудови оптимальних k-значних структур. Створюється множина істин, явищ та факторів, що піддаються пізнанню та розумінню, але вони не дають відповіді на кардинальне питання, як та для яких задач можна і необхідно створювати k-значні структури. Істини, що виводяться з різних теорій можна ув’язати в єдине ціле, якщо перейти від аналізу та синтезу окремо взятих структур, у окремо взятих традиційних теоріях, до інтегрування знань на єдиній методологічній і цільовій основі, на логіко-ймовірнісному підході до створення, із наперед заданими властивостями і орієнтованими на вирішення зверхзадачі - побудови k-значних елементів і структур для високошвидкісних обчислювальних систем. Хід побудови теорії - феноменологічний, у основі якого лежить порівняльний аналіз властивостей та процесів у живих та технологічних системах, а далі - уявний експеримент із побудови k-значних елементів і структур на основі цього аналізу.

Основнi позитивнi ефекти вiд застосування k-значних елементiв та структур можна звести до наступного: створення високошвидкісних обчислювальних систем, здатних до самоорганiзацiї та самопрограмування, рiшення надскладних задач розпiзнавання образiв мовних та зорових зображень, а також k-значних аналiзаторiв i синтезаторiв сигналiв, призначених для оперативного аналiзу випадкових процесiв та формування радiолокацiйних зондуючих сигналiв; створення систем завадостiйкого кодування та захисту вiд несанкцiонованого доступу із застосуванням теорiї скiнченних полiв, що є за суттю k-значними; розвиток нового підходу до створення високоефективної потоково-просторової архiтектури систем з елементами штучного інтелекту, адекватної до складностi задач, що ними виконується; спрощення структури цифрових пристроїв оброблення даних через відсутність потреби промiжних перетворень десяткових чисел у двiйкову форму та суттєве збiльшення швидкості виконання арифметичних операцiй; зменшення апаратурних затрат за рахунок зменшення довжини кодових зображень даних із ростом значностi i, як наслiдок, зниження вартостi та енергоспоживання; рiст продуктивностi цифрових систем та ЕОМ за рахунок скорочення часу виконання таких непродуктивних операцiй як вирiвнювання порядкiв та нормалiзацiя; зменшення числа зв’язкiв на функцiональному та системному рiвнях i, як наслiдок, пiдвищення надiйностi пристроїв передачi цифрових даних, зниження масогабаритних показникiв та втрат дорогоцiнних металiв; створення високоефективних методiв та засобiв аналого-цифрового перетворення; створення методів моделювання елементiв та структур із сумiщенням процесiв логiчного моделювання та кiлькiсного аналiзу (на основi бiльшої деталiзацiї зображення форми реального фiзичного сигналу); забезпечення вищої швидкостi передачi цифрових сигналiв у межах заданої смуги частот; оптимiзацiя програм згiдно зі заданими критерiями з використанням k-значних алгебр Поста тощо [17, 18].

Актуальнiсть роботи. З часу виникнення обчислювальної техніки ведуться дослідження і здійснюється реалізація на рівні інженерних рішень k-значних структур і кодування у зв’язку з високою інформаційною насиченістю їх сигналів. k-значними називають структури засобів оброблення даних, що побудованi на базi k-значних логічних елементiв із відповідними зв’язками. До таких структур належать усi об’єкти, що описуються скiнченним структурним алфавiтом: елементи, структури та системи обчислювальної, вимiрчої, керуючої технiки та технiки зв’язку. Особливістю k-значних структур у модельному та фізичному плані є те, що вони є погано органiзованими — дифузними системами, в яких неможливо відокремити окремі явища, адже під час їх розробки, створення та експлуатацiї необхiдно враховувати дуже багато рiзних факторiв, якi визначають рiзнi за природою, але тiсно взаємодiючi процеси.

Важливий внесок у розвиток математичних методів дослідження
k-значних структур та методів їх побудови здійснили в теорії інформації,
k-значній логіці та теорії інтелекту Є. І. Брюхович, Б. А. Варшавер, Ю. Л. Іваськів, А. Б. Кметь, В. І. Корнейчук, Д. А. Поспєлов, В. П. Тарасенко, Ю. П. Шабанов-Кушнаренко, К. Шеннон, С. В. Яблонский.

На сьогодні відома значна кількість розрізнених підходів та методів побудови і застосування k-значних структур, проте відсутні їх систематизація та упорядкована система засобів реалізації, недостатньо опрацьована теорія математичного моделювання. В існуючих теоріях не розглядалась і не ставилась проблема наукового обґрунтування та визначення класу задач, для яких:

·      об’єктивно необхідна k-значна елементна база,

·      чому саме k-значна,

·      які математичні моделі та структурні побудови їм відповідають.

У той же час оптимальне проектування та технічна реалізація обчислювальних пристроїв на базі k-значних структур неможливі без одночасної розробки принципово нових (нетрадиційних) видів математичних моделей та їх дослідження для різних режимів роботи й інтерпретації результатів моделювання. Це призвело до кризової ситуації, пов’язаної з відсутністю цілісної теорїї побудови високоефективних k-значних структур та нагальною потребою одночасного зменшення неприйнятних за обсягом витрат часу і фінансів під час їх реалізації. Тому вирішення означеної проблеми є актуальним і має стратегічне значення для створення високоефективних обчислювальних структур і систем.

Проведений аналіз показує, що задачу створення узагальненої теорії побудови високоефективних k-значних структур і кодування як дифузних систем може бути вирішено тільки в рамках класу інтуїтивно-конструктивістських теорій. Цей підхід, його наукове обґрунтування і прикладне застосування розвивається в рамках дисертаційної роботи.

Зв’язок роботи з науковими програмами, планами, темами. Результати, включені в дисертаційну роботу, отримано при виконанні планових науково-дослідних робіт «Аналіз та синтез моделей, алгоритмів та програмно-апаратних засобів адаптивних систем дистанційного навчання» (№ 0103U000693 держреєстрації), «Експериментальна система дистанційного навчання стендової версії автоматизованої банківської системи «Барс-Міленіум» і «Моделі та програмно-апаратні засоби адаптивних інформаційних систем оцінювання, атестації та розвитку персоналу» (розробка методів аналізу та синтезу моделей та алгоритмів для систем дистанційного навчання, 2002-2003 рр.), «Фундаментальні основи синтезу багатовимірних нейромереж на базі універсальних нейронних елементів та нейроподібних систем»
№ 01.07/00236 (розроблення теорії та методології створення нового класу високоефективних універсальних нейроподібних структур із k-значним кодуванням, 2005 р.).