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

УКРАЇНИ

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

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

Коноплянко Зеновiй Дмитрович

УДК 519.95: 621.324: 681.3(07)

МОДЕЛІ ТА МЕТОДИ

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

ВИСОКОЕФЕКТИВНИХ ПРОСТОРОВИХ

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

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

Автореферат

дисертацiї на здобуття наукового ступеня

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

ЛЬВІВ – 2005

Дисертацією є рукопис.

Робота виконана в Державному науково-дослідному інституті інформаційної інфраструктури, НАН України.

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

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

Бондаренко Михайло Федорович

Харківський національний університет радіоелектроніки,

завідувач кафедри “Програмне забезпечення ЕОМ”.

Офiцiйнi опоненти:

доктор технічних наук, професор, Кривуля Геннадій Федорович,

Харківський національний університет радіоелектроніки,

завідувач кафедри “Автоматизація проектування обчислювальної техніки”;

доктор технiчних наук, професор, Семерак михайло михайлович,

Львівський інститут пожежної безпеки МНС України,

професор кафедри “Наглядово-профілактична діяльність”;

доктор технiчних наук, професор, Русин Богдан Павлович,

Фізико-механічний інститут ім. Г. В. Карпенка НАН України,
завідувач відділу “Методи та системи обробки, аналізу
та ідентифікації зображень”, м. Львів.

Провiдна установа:

Національний технічний університет України
“Київський політехнічний інститут” Міністерства освіти і науки України, кафедра прикладної математики, м. Київ.

Захист відбудеться 23 грудня 2005 р. о 15 годині на засіданні спеціалізованої вченої ради Д 35.813.01 при Державному науково-дослідному інституті інформаційної інфраструктури Державного комітету зв’язку та інформатизації і НАН України (79000, МСП, м. Львів, вул. Тролейбусна, 11).

Із дисертацiєю можна ознайомитись у бiблiотецi Державного науково-дослідного інституту інформаційної інфраструктури Державного комітету зв’язку та інформатизації і НАН України (79000, МСП, м. Львів, вул. Тролейбусна, 11).

Реферат розiсланий 21 листопада 2005 року.

Вчений секретар

спецiалiзованої вченої ради Пеленський О.Л.

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Актуальн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-значних структур, проте відсутні їх систематизація та упорядкована система засобів реалізації, недостатньо опрацьована теорія математичного моделювання. В існуючих теоріях не розглядалась і не ставилась проблема наукового обґрунтування та визначення класу задач, для яких:

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

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

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

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

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

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

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

Відповідно до поставленої мети сформульовано та розв’язано такі задачі:

1. Проведення аналізу відомих наукових теорій створення k-значних структур просторового типу з метою визначення шляхів і наукових підходів їх удосконалення та узагальнення.

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

3. Розроблення математичних моделей для оцінки та встановлення визначальних параметрів апаратурних каналів із k-значним кодуванням і вносимою надлишковістю.

4. Проведення повного математичного дослідження моделей k-значного кодування каскадними кодами Ріда-Соломона (CIRC-кодами – Cross-Interleaved Reed-Solomon Code) для отримання повного комплексу варіацій стратегій кодування/декодування.

5. Дослідження та розроблення на базі отриманого комплексу варіації стратегій системи паралельних, послідовних та паралельно-послідовних алгоритмів побудови структур та операційних програмно-апаратних засобів k-значного кодування каскадними CIRC-кодами.

6. Розроблення принципів побудови k-значних просторових пристроїв зовнішнього обміну (ПЗО) та їх математичних моделей на основі рекурсивного методу синтезу структур перетворювачів кодів як визначальної компоненти універсальної комірки.

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

8. Розроблення математичних моделей для синтезу спеціалізованих операційних пристроїв обчислювальних структур і систем новітніх поколінь із застосуванням k-значного кодування даних.

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

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

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

Наукова новизна одержаних результатів:

1.

2.

3.

4.

5.

6.

7.

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

- розроблені математичні моделі k-значних структур за характером відображених властивостей належать до функціонального рівня і можуть використовуватись самостійно як елементи високоефективних обчислювальних структур і систем та цифрових мереж із урахуванням логічних, метричних, ентропійних та точнісних параметрів;

- розроблені методи побудови математичних моделей, k-значних структур і кодування утворють основу комплексного підходу до проблеми побудови універсальних просторових k-значних структур як нової елементної бази високоефективних обчислювальних систем та цифрових мереж;

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

- розроблені математичні моделі та програмно-апаратні засоби k-значного двоетапного CIRC-декодера можна використати як автономні продукти при проектуванні систем захисту даних від несанкціонованого доступу;

- розроблення та застосування k-значних просторових пристроїв зовнішнього обміну даними, паралельно-об’ємного комутатора k-значних сигналів та універсальних функціональних перетворювачів дозволяє в 2–4 рази зменшити число функціональних зв’язків у багатопроцесорних обчислювальних системах і системах штучного iнтелекту із відповідним зменшенням апаратурних затрат і вартості та забезпечити їм гранично високу швидкодію.

Створені перспективні класи елементів та операційних пристроїв просторового типу для нейроподібних обчислювальних структур і систем захищені авторськими свідоцтвами й патентами на винаходи, запроваджені у виробництво та використовуються на практиці, приносячи вiдповiдний економiчний ефект.

Основнi результати дослiджень впроваджено в таких органiзацiях та пiдприємствах пiд час розроблення:

- науково-дослiдної роботи “Фундаментальні основи синтезу багатовимірних нейромереж на базі універсальних нейронних елементів та нейроподібних систем” № 01.07/00236, м. Львiв, Державний науково-дослідний інститут інформаційної інфраструктури Міністерства транспорту та зв’язку і НАН України, 2005 р.;

- науково-дослiдної роботи “Аналіз та синтез моделей, алгоритмів та програмно-апаратних засобів адаптивних систем дистанційного навчання” (№ 0103U000693 держреєстрації), м. Київ, Національний банк України, 2002–2005 рр.;

- науково-дослiдних робiт “Експериментальна система дистанційного навчання стендової версії автоматизованої банківської системи “Барс-Міленіум”, а також “Моделі та програмно-апаратні засоби адаптивних інформаційних систем оцінювання, атестації та розвитку персоналу”, м. Львiв, Львівський банківський інститут, 2002–2004 рр.;

- високопродуктивних спецiалiзованих засобiв оброблення iнформацiї та забезпечення їх надiйностi i взаємозамiнюваностi на етапi проектування, а також гiбридних iнтегрованих схем перетворювачiв двозначного коду в багатозначний та навпаки, виготовлених у Фізико-механічному інституті згiдно замовлення Державного науково-дослiдного центру вивчення природних ресурсiв (ГОС НИЦ ИПР), м. Москва, 1983–1984 рр.;

- k-значної системи кодування iнформацiї, виготовленої на замовлення Інституту космiчних дослiджень АН СРСР у СКБ ВО “Мiкроприлад” м. Львiв, у якiй використовувались k-значні елементи паралельного типу з пiдвищеною швидкодiєю, 1983–1984 рр.;

- дешифратора телеметричного сигналу апаратури “Терра”, виготовленої за замовленням Iнституту земного магнетизму, йоносфери та розповсюдження радiохвиль АН СРСР, що використовувався пiд час дослiджень верхнiх шарiв атмосфери з допомогою аеростатiв, 1983 р.

Теоретичні результати роботи використовуються в навчальному процесi Харківського національного університету радіоелектроніки, Львівського банківського інституту НБУ та Національного унiверситету “Львiвська полiтехнiка” як навчальнi та методичнi посiбники при підготовці студентів за спеціальністю “Економічна кібернетика” у дисциплінах “Дискретний аналіз”, “Теорія відкритих систем та алгоритмізація і процедури програмування обробки даних” і “Системи штучного інтелекту в економіці”.

Особистий внесок здобувача. Основнi результати теоретичних та експериментальних досліджень, що містяться в дисертації, отриманi особисто та опубліковані в роботах [4–12; 25; 26; 29–34]. У працях, опублікованих у співавторстві, авторові дисертації належать: [1–3] – формулювання iдей та задач, розроблення основних положень теорiї, математичних моделей, алгоритмiв і методiв аналiзу, синтезу, побудови та реалiзацiї k-значних функціональних перетворювачів, структур і засобiв кодування з точки зору статистичних імовірнісних оцiнок надійності та завадостійкості й вносимої надлишковостi у швидкодiючих просторових k-значних структурах; [13; 24; 37] – розроблення методів оптимізації стратегій декодування CIRC-кодов за ймовірнісними критеріями; розроблення методів побудови архітектур та алгоритмів багатозначного CIRC-кодування для систем штучного інтелекту; аналізу методів оцінки швидкодії двокаскадного CIRC-декодера; [14] – розроблення методів завадостійкого k-значного кодування та захисту інформації в україномовних інтерфейсах систем штучного інтелекту; [15] – формулювання проблем інтелектуалізації та українізації цифрових систем та мереж телекомунікацій; [16–17; 20] – розроблення математичних моделей оброблення української мови та структурно-функціональний аналіз системи штучного інтелекту та його підсистеми – національної (української) мови; [18] – розроблення методів k-значного кодування та захисту інформації в цифрових мережах та системах телекомунікацій; [21–23] – створення синтетичної теорії побудови інтерфейсних пристроїв систем штучного інтелекту з k-значним кодуванням; аналіз архітектурних побудов цифрових та k-значних структур для систем штучного інтелекту; дослідження архітектур і розроблення синтетичної теорії побудови та синтезу цифрових просторових комутаторів із k-значним кодуванням для систем штучного інтелекту; [27] – розроблення структури, принципів побудови і математичних моделей складових двовходового 10-значного логічного елемента; [28] – аналітичний огляд методів аналізу і синтезу k-значних структур; [35] – дослідження шляхів побудови та принципу симбіозу дво- та k-значних логік і технічних засобів систем штучного інтелекту з k-значним кодуванням; [36] – розроблення методів аналізу і синтезу тексту на природній мові для досягнення високорівневої технології обробки інформації.

Апробацiя результатів роботи. Основнi наукові результати та положення доповiдалися й обговорювалися на таких конференцiях: Всесоюзній школі-семiнарі “Психологическая бионика” (Харкiв, 1986, 1988 рр.); Всесоюзній школі-семiнарі “Бионика интеллекта” (Харкiв, 1987 р.); Всесоюзній науково-технiчній конференцiї з спецрадiоелектронiки “Специализированная элементная база для РЭА” (Ташкент, 1989 р.); 2-й Всесоюзнiй конференцiї “Проблемы и перспективы развития цифровой звуковой техники” (Ленiнград, 1990 р.); Мiжнародній конференцiї UkrSatCom-93 “Супутниковi системи зв’язку та мовлення: Перспективи розвитку в Українi” (Одеса, 1993, 1995); НТК Державного університету “Львiвська полiтехнiка” (Львiв, 1991–1995 рр.); 2-й Українській конференції з автоматичного кеpування” (Автоматика-95) (Львів, 1995 р.); Третій Всеукраїнській міжнародній конференції “Укробраз-96” (Київ, 1996 р.); 4-й Міжнародній конференції “Теорія та техніка передавання, приймання і оброблення інформації” (“Нові інформаційні технології”) (Харків, 1998 р.); 4-й Міжнародній конференції з телекомунікацій “НТК-Телеком-99” (Одеса, 1999 р.); Міжнародній науково-технічній конференції “Искусственный интеллект-2002” (16–20 вересня 2002 р., Кацивелі (Крим)); Міжнародній науково-технічній конференції “Интеллектуальные и многопроцессорные системы-2003” (22–27 сентября 2003 г., Дивноморское, Геленджик, Россия); 4-й Міжнародній міждисциплінарній науково-практичній конференції “Сучасні проблеми науки та освіти”, 1–10 травня 2003 р., м. Ялта/Харків; Міжнародній науково-технічній конференції “Искусственный интеллект. Интеллектуальные и многопроцессорные системы-2004” (20–25 сентября 2004 г., Кацивели, Украина).

Публiкацiї. Основні результати дисертації опубліковано в 37 наукових працях, серед яких 3 монографiї, 21 стаття у фахових виданнях, 2 депоновані монографії, 8 друкованих матеріалів конференцій та 3 авторських свiдоцтва і патенти на винаходи.

Обсяг та структура роботи. Дисертацiя складається зі вступу, семи роздiлiв, висновкiв і списку використаних літературних джерел та додатків. Загальний обсяг роботи становить 288 сторінок, у тому числі основного тексту – 240 стор., 25 сторінок ілюстрацій і таблиць, 18 сторінок – список використаних джерел із 203 назв та 5 стор. – додатки.

ЗМІСТ ДИСЕРТАЦІЙНОЇ РОБОТИ

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

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

Показано, що k-значні структури в модельному та фізичному плані належать до погано органiзованих – дифузних систем, у яких неможливо відокремити окремi явища. Разом із тим під час розробки їх математичних моделей, побудови та експлуатацiї необхiдно враховувати дуже багато рiзних факторiв, якi визначають рiзнi за природою, але тiсно взаємодiючi процеси. Традиційні математичні моделі синтезу k-значних структур є вузькоспеціалізованими та недостатньо опрацьованими для створення узагальненої теорії їх побудови. Оглядові різних математичних методів синтезу k-значних структур присвячено роботи [28; 29], де доведено, що канонічні математичні моделі та методи синтезу для такого виду структур є надзвичайно складними і малоефективними. Крім цього, аналіз досягнень теорії інтелекту додатково дозволив зробити прогнозний висновок, що k-значні високоефективні обчислювальні методи та засоби спроможні подолати кризові явища, пов’язані з використанням нойманівських процесорів у системах штучного інтелекту.

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

- створення статичних k-значних просторових структур повинно базуватися на застосуванні принципу симбіозу (нерозривного зв’язку та взаємодiї) двозначних та аналого-дискретних засобiв опрацювання даних, для формалізації якого не існує відповідних математичних моделей;

- побудова статичних k-значних просторових структур та їх математичних моделей започатковується структурними дослідженнями архітектурних побудов цифрових систем новітніх поколінь, k-значних елементів та просторових цифрових комутаторів;

- розроблення математичних моделей для прогнозування надійності та аналізу точності дії k-значних структур здійснюється на базі статистичного підходу і служить з’єднувальним містком з ентропійними математичними моделями інформаційних каналів;

- закономірності зміни структурної надiйності від зміни значності описуються математичною моделлю такого вигляду

H(t, k) , (1)

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

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

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

- математичною основою k-значного кодування є методи і засоби k-значного кодування з надлишком та k-значного систематичного кодування кодами Рiда–Соломона із кросперемежуванням.

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

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

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

До складу k-значної площинно-просторової комiрки необхідним чином входять (рис. 1): n-вимiрний просторовий комутатор цифрових сигналiв; комплекс порогових пристроїв, дешифратори просторових промiжних ознак та формувачi k-значних функцiй, що утворюють універсальний просторовий функціональний перетворювач, а також перетворювачі кодів.

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

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

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

Універсальні просторові k-значні структури, згідно із принципом симбіозу, включають до свого складу (рис. 2) такі компоненти: паралельний аналого-цифровий перетворювач, який із дешифратором утворює елемент розпізнавання k-значної змінної (одновходовий багатопороговий елемент – ОБПЕ), селектор, комутатор, паралельний цифро-аналоговий перетворювач (ключовий комутатор або підсумовувач струмів).

Елемент розпізнавання k-значної змінної реалізує предикат

(2)

де t – двозначна (логічна) змінна; X – k-значна вхідна змінна; kі {0, 1, ..., k – 1} – і-те значення k-значної змінної.

Оскільки рівнів k, то і вихідних сигналів розпізнавання для просторового набору порогових елементів буде k: t0, t1, t2, ...,tk–1 {0, 1}. Таким чином, уже на першому етапі, забезпечується розпаралелення процесу із забезпеченням гранично високої швидкості перетворень.

Логіку роботи дешифраторів описує така система предикатних рівнянь

(3)

Логіку роботи матричного селектора описує система рівнянь АСП

, (4)

де fmn – вихідні сигнали матричного селектора, що приймають значення з множин E2 {0, 1}, m, n = Ek {0, 1, ..., k – 1}.

Формально, в явному вигляді, робота просторового комутатора описується такою системою рівнянь алгебри скінченних предикатів:

(5)

Відповідно вихідні сигнали комутатора будуть утворені за рахунок провідного АБО сигналів із однаковими індексами, але із різних площин комутації:

(6)

Остаточний результат універсального перетворення формально можна подати у вигляді операторного зображення

, (7)

де <g0, g1, ..., gk – 1> = PSf – сигнали налагоджень вихідних функцій універсальної структури.

Зростання значності та числа вхідних змінних універсальної k-значної структури веде до суттєвих змін у побудові компонентів: на вході структури зростає пропорційно k число елементів розпізнавання; структури селекторів і комутаторів перетворюються у n-вимірні об’ємно-просторові утворення, а на виході структури зростає пропорційно k число ключів. Універсальна просторова k-значна структура (див. рис. 2) може бути описана такою системою ознак: SPVPS, де V – об’єм (вимірність простору селектора і комутатора), причому отримані математичні моделі проміжних перетворювачів є паралельного (просторового) типу, мають однорідну структуру і володіють гранично високою швидкодією.

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

Проведені дослiдження дозволили практично подолати “комбінаторний вибух”, що супроводжує такого роду задачі. Розроблено швидкодіючий метод перебору і створено алгоритм пошуку класів еквівалентності двомісних 3-значних функцій щодо числа породжуваних різноманітних функцій. Для k = 3 та n = 2 отримано розбиття (табл. 1) на 45 класів еквівалентності всiх 19 683 породжуючих функцiй.

Подані результати отримані автором вперше і становлять основу інтуїтивно-конструктивістської теорії. Вони дають можливiсть:

1. без додаткового аналiзу та дослiджень у майбутньому оптимiзувати роботу комутацiйного обладнання, зокрема потрібний обсяг пам’ятi для здiйснення необхiдного числа комутацiй пiд час обслуговування процесiв обмiну даними, а також програмне забезпечення керуючих комплексiв у цифрових системах;

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

3. застосування отриманих результатiв для побудови систем штучного iнтелекту.

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

, (8)

де – відносне середньоквадратичне вiдхилення (ВСВ) одиничного кроку квантування (рiвня напруги чи струму); – абсолютне вiдхилення кроку квантування; – математичного очікування кроку квантування; k – значнiсть структурного алфавiту; U – параметр iнтеграла ймовiрностей, що відповідає заданому рівню ймовірності безвідмовної роботи (ЙБР).

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

Аналiз залежності ВСВ = (рис. 3) для k-значних структур показав, що у порiвняннi з двозначними структурами k-значні структури володiють 80-кратним запасом жорсткостi припускiв на вiдхилення своїх, квантованих за рiвнем сигналiв. Таким чином, k-значні структури займають проміжне становище щодо жорсткості припусків ВСВ між двозначними та аналоговими, що надає широкі можливості оптимального вибору параметрів на етапах проектування та експлуатації.

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

У третьому роздiлі наведено результати удосконалення методів і математичних моделей оцінки параметрів апаратурних та інформаційних каналів із k-значним кодуванням, зокрема: ентропійних параметрів k-значних каналів із завадами та без них; властивостей симетричних каналів із k-значним кодуванням; імовiрностей помилки пiд час декодування k-значних систематичних кодiв; необхідної вносимої надлишковості статичних просторових k-значних структур як теоретичних основ побудови k-значних статичних просторових структур і підвищення надійності проектованих структур за допомогою методів завадостійкого кодування.

Досліджено: 1) математичні моделі k-значних інформаційних каналів без завад, у результаті чого отримано тривимірну суттєво нелінійну залежність перепускної здатності від значності та тривалості інформаційного кодового сигналу, що є доповнюючою гранню теорії побудови та засобом оптимізації параметрів k-значних просторових структур; 2) властивості симетричних каналів із завадами та k-значним кодуванням. У результаті отримано тривимірні нелінійні залежності від значності та добутку інтенсивності відмов на час роботи верхньої межі перепускної здатності та можливих послідовностей кодів. Це надає потенційну можливість оптимізації параметрів на етапах проектування та експлуатації k-значних апаратурних каналів за надійнісними критеріями.

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

Показано, що для процесів побудови надійних високошвидкісних засобів із k-значним кодуванням базовими інформаційними характеристиками симетричних структурних k-значних каналів є залежності: 1) оптимальної значності від часу роботи та інтенсивності завад, 2) ентропії фактично переданих послідовностей k-значним систематичним кодом для різних значень r, n, k; 3) величини верхньої межі перепускної здатностi від параметрів k-значних апратурних каналів; 4) верхньої межі можливих послiдовностей для n-розрядного k-значного коду з надлишковiстю, від числа r коректованих помилок; 5) імовiрності (9) помилки ; 6) рівня вносимої в k-значних структурах надлишковостi від виду розподілу завад.

Використовуючи введену в першому розділі аксіоматику (1), приводимо класичний бiномний розподiл імовiрності помилок декодування для даного числа символiв n та числа помилок r до наступного вигляду для k-значних апаратурних каналів

, (9)

де i – кратнiсть помилки в послiдовностi, , – інтенсивність структурних завад в апаратурному каналі (див. також (1)), t – час – роботи каналу.

Отримана формула дала можливість провести нетрадиційні дослідження та отримати нові оцінки для вказаної ймовірності помилки. Дослідження залежностей (рис. 4) імовiрностей помилки k-значних систематичних кодiв для відповідних параметрів (інтенсивність структурних завад та середній час безвідмовної роботи) дозволили встановити суттєву відмінність k-значних інформаційних апаратурних каналів від традиційних двозначних каналів.

Різкий спад величини ймовірності помилки відбувається за умови, коли добуток Із залежності (див. рис. 4) випливає факт, що значності порядку 2...3 є найбільш нестійкими, тобто з високою ймовірністю помилки в повідомленні.

Імовірність помилки каскадних надлишкових кодів при дослідженнях розпадається на дві компоненти – власне помилки (рис. 5) та “хибної тривоги” (рис. 6) і є єдиним критерієм надання переваги у вiдношеннi ймовiрностi помилки на виходi декодера CIRC-коду для стратегiй декодування з різними коректуючими можливостями.

Дослiдження k-значних надлишкових кодiв показали, що для пiдвищення завадостійкостi даних необхiдно збільшувати число позицiй кодового сповiщення та зберiгати спiввiдношення числа помилок до числа позицiй у кодовому повiдомленнi <0,5, а також впливати на ймовiрнiсть помилки як на входi, так i в структурі.

Установивши припустимий рiвень імовiрностi помилки на виходi декодера, для мовних каналiв зв’язку ця величина порядку 10-12, за даним критерієм можна оптимiзувати стратегiї декодування.

Процедура декодування, за якою на етапi декодування С1 виявляються та виправляються до M помилок, а на етапi С2 – вiдшукуються до N помилок, отримала позначення як стратегiя декодування СMN. Відповідно застосування стратегії С13 для k-значних каскадних CIRC-кодів забезпечує підвищення ймовірності правильного декодування для помилок із великою протяжністю (l > 4) a також дає виграш у часі оброблення сигналу за рахунок зменшення числа обчислювальних операцій і звертань до пам’яті.

Для локалiзацiї критичних точок та областей iснування працездатностi k-значних структур здійснено екстремальний аналiз по k. Перша похiдна по k, при p = e–R, дає

де R = kt; – iнтенсивнiсть структурних вiдмов (завад) в апаратурному каналi; t – час роботи.

Дослідження статистичних ентропійних закономірностей (9) внесення надлишковості (рис. 7) для різних законів розподілу завад [а) експоненційний, б) Пуассона та в) нормальний] дозволяють забезпечити в k-значних структурах необхiдний рiвень надiйностi, точностi та завадостiйкостi в процесi експлуатацiї, а є тим показником, що забезпечує необхідну складність k-значних структур стосовно тих задач, що ними виконуються.

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

Проведені в розділі дослідження CIRC-коду пiд час декодування k-значних систематичних кодiв дозволили: 1) розкрити суттєву відмінність апаратурних каналів із k-значним кодуванням порівняно з традиційними двозначними каналами; 2) підтвердити вагомість принципу симбіозу в разі застосування надлишкових кодів і його надзвичайно високу ефективність під час практичної реалізації кодів із дуже великою довжиною блока даних та високою коректуючою здатністю; 3) постулювати те, що імовірність помилки, як універсальний параметр, є сполучною ланкою, який об’єднує в єдине ціле ентропійні математичні моделі апаратурних каналів із моделями надійності їх роботи та фізичними параметрами k-значних структур і служить основою до створення узагальненої математичної теорії їх побудови.

У четвертому розділі поставлено та вирішено такі задачі досліджень k-значного кодування каскадними кодами, що не мали свого вирішення: розроблення математичних моделей кодування і декодування кодів Рiда – Соломона з кросперемежуванням (CIRC-кодів); синтез алгоритмів k-значного кодування/декодування; розроблення способи організації обчислень та синтезу структур операційних засобів CIRC-кодера/декодера; аналіз принципів побудови та дії функціонально-орієнтованого процесора (ФОП) двокаскадного CIRC-декодера; порівняльний аналіз cтратегій декодування CIRC-декодерів.

Аналіз шляхів побудови k-значних структур, з одного боку, та побудови високоефективних обчислювальних систем – з іншого, були б неповними без розгляду математичних моделей k-значного кодування даних із допомогою кодів Ріда – Соломона. Власне запропонована автором і теоретично обґрунтована в роботі ідея проведення досліджень на стику вказаних дисциплін дозволяє повніше розкрити особливості: 1) математичного моделювання шляхів кодування CIRC-кодами; 2) побудови і структури алгоритмів кодування CIRC-кодами; 3) створення технічних засобів завадостійкого кодування та захисту інформації від несанкціонованого доступу; 4) характеристик та вимог до технічних засобів кодування CIRC-кодами тощо.

У розділі дістали подальший розвиток математичні моделі кодування і декодування кодами Ріда – Соломона із застосуванням принципу симбіозу різних видів кодування і гнучкого, адресного та просторового квазівипадкового переплетіння шляхів поширення сигналів. Це дозволило: 1) побудувати структури нових алгоритмів кодування для захисту від несанкціонованого доступу; 2) створити захищені і надійні обчислювальні системи; 3) проаналізувати характеристики й вимоги до технічних засобів кодування CIRC-кодами; 4) змінювати вид породжуючого многочлена поля, довжину блоків та вид перемежування символів.

Як відомо, суть традиційного методу кодування кодом Ріда – Соломона полягає у визначенні, згідно з вхідними інформаційними символами, значень паритетних символів Qi, Pi, таким чином, щоби синдроми помилок S1, ..., S4 були нульовими у разі відсутності збоїв. Корекцiя помилок здiйснюється з допомогою декодерiв С1 чи С2 шляхом додавання значення помилки до значення синдрому. При цьому кодування та декодування здійснюються в скінченному полі ґалуа GF(28), що згенероване за модулем многочлена F(x) = x8+x4+x3+x2+1.

Типова структура CIRC-декодера складається (рис. 8) із п’яти блокiв: блоку деперемежування (ДП1) парних та непарних символiв послiдовностi даних, декодера С1 коду РС(32, 28), блоку деперемежування на основi затримок неоднакової тривалості (псевдовипадкове перемежування) (ДП2), декодера С2 коду РС (28, 24) над GF(28) та блоку деперемежування на два кадри (ДП3).

Блоки деперемежування (ДП1-ДП3) дозволяють знизити ймовiрнiсть помилки на входi чи всерединi системи та забезпечити виправлення як поодиноких, так i пачок помилок за рахунок декореляцiї згрупованих помилок шляхом їх розкиду. Для декодера (див. рис. 8) таку операцiю здiйснює блок ДП2, для якого величина затримки блокiв символiв D = 4.

Блок деперемежування ДП1 пiдвищує ефективнiсть роботи декодера С1, здiйснюючи затримку парних символiв на один такт послiдовностi, оскільки випадковi помилки двох сусiднiх символiв найлегше рознести в рiзнi кодовi слова. Блок ДП3 забезпечує розширення меж корекцiї помилок серед непарних символiв, похибки яких додатково ще й маскуються з допомогою лiнiйної iнтерполяцiї (обчисленням середнього вiд двох сусiднiх достовiрних символiв).

За результатами досліджень третього розділу математичних моделей імовiрності помилки CIRC-коду синтезовано алгоритми k-значного кодування/декодування, що становлять теоретичний доробок автора.

На цій теоретичній базі реалізовано два комплекси програм для аналізу та моделювання шляхів побудови і процесів роботи CIRC-кодера/декодера. Перший – для кодування в складі головної програми, що отримала позначення KODPER (рис. 9), та підпрограм GALUA, KOD1, KOD2, RAND2, SUMQ, RSYS2, SUMP.

Другий комплекс програм – для декодування під керуванням програми MODC5 (рис. 10.) із підпрограмами SINDR, DSINDR, KORR1, KORR2, KORR22, KORR3, KORR4.

Перший та другий комплекси використовують також спільні підпрограми IADD, IADD2, POIND.

Структури С1, С2 декодерів ФОП (рис. 11) CIRC-декодування є об’єктом масового використання і вимагають створення компактних мікроелектронних засобів із застосуванням двозначного зображення k-значних символів, цифрових алгоритмів і