Моделі та методи теорії побудови і кодування високоефективних просторових k-значних структур

Размещено на http://www.allbest.ru/

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

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

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

УДК 519.95: 621.324: 681.3(07)

Автореферат

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

МОДЕЛІ ТА МЕТОДИ ТЕОРІЇ ПОБУДОВИ І КОДУВАННЯ ВИСОКОЕФЕКТИВНИХ ПРОСТОРОВИХ k-ЗНАЧНИХ СТРУКТУР

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

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

ЛЬВІВ - 2005

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Проведення повного математичного дослідження моделей k-значного кодування каскадними кодами Ріда-Соломона (CIRC-кодами - Cross-Intеrlеаvеd Rееd-Solomon Codе) для отримання повного комплексу варіацій стратегій кодування/декодування.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Особистий внесок здобувача. Основні результати теоретичних та експериментальних досліджень, що містяться в дисертації, отримані особисто та опубліковані в роботах [4-12; 25; 26; 29-34]. У працях, опублікованих у співавторстві, авторові дисертації належать: [1-3] - формулювання ідей та задач, розроблення основних положень теорії, математичних моделей, алгоритмів і методів аналізу, синтезу, побудови та реалізації k-значних функціональних перетворювачів, структур і засобів кодування з точки зору статистичних імовірнісних оцінок надійності та завадостійкості й вносимої надлишковості у швидкодіючих просторових 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] - розроблення методів аналізу і синтезу тексту на природній мові для досягнення високорівневої технології обробки інформації.

Апробація результатів роботи. Основні наукові результати та положення доповідалися й обговорювалися на таких конференціях: Всесоюзній школі-семінарі “Психологическая бионика” (Харків, 1986, 1988 рр.); Всесоюзній школі-семінарі “Бионика интеллекта” (Харків, 1987 р.); Всесоюзній науково-технічній конференції з спецрадіоелектроніки “Специализированная элементная база для РЭА” (Ташкент, 1989 р.); 2-й Всесоюзній конференції “Проблемы и перспективы развития цифровой звуковой техники” (Ленінград, 1990 р.); Міжнародній конференції UkrSаtCom-93 “Супутникові системи зв'язку та мовлення: Перспективи розвитку в Україні” (Одеса, 1993, 1995); НТК Державного університету “Львівська політехніка” (Львів, 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 г., Кацивели, Украина).

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

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

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

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

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

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

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

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

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

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

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

H(t, k) , (1)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(2)

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

Оскільки рівнів k, то і вихідних сигналів розпізнавання для просторового набору порогових елементів буде k: t₀, t₁, t₂, ...,t_k-₁ {0, 1}. Таким чином, уже на першому етапі, забезпечується розпаралелення процесу із забезпеченням гранично високої швидкості перетворень.

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

(3)

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

, (4)

де f_mn - вихідні сигнали матричного селектора, що приймають значення з множин E₂ {0, 1}, m, n = E_k {0, 1, ..., k - 1}.

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

(5)

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

(6)

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

, (7)

де <g₀, g₁, ..., g_{k - 1}> = PS_f - сигнали налагоджень вихідних функцій універсальної структури.

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

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

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

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

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

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

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

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

, (8)

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

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

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

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

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

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

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

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

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

, (9)

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

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

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

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

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

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

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

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

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

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

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

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

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

Як відомо, суть традиційного методу кодування кодом Ріда - Соломона полягає у визначенні, згідно з вхідними інформаційними символами, значень паритетних символів Q_і, P_і, таким чином, щоби синдроми помилок S₁, ..., S₄ були нульовими у разі відсутності збоїв. Корекція помилок здійснюється з допомогою декодерів С1 чи С2 шляхом додавання значення помилки до значення синдрому. При цьому кодування та декодування здійснюються в скінченному полі ґалуа GF(2⁸), що згенероване за модулем многочлена F(x) = x⁸+x⁴+x³+x²+1.

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

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

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

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

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

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

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

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

Синтез алгоритмів k-значного кодування/декодування і аналіз способів організації обчислень та побудови структур операційних засобів CIRC-кодера/декодера, принципів побудови та дії ФОП двокаскадного CIRC-декодера та порівняльний аналіз стратегій декодування CIRC-декодерів дають можливість:

- математичного моделювання методів кодування CIRC-кодами;

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

- синтезу граничних структур процесорів паралельного, послідовного та паралельно-послідовного типу дії й оцінки їх щодо складності та швидкодії;

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

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

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

У п'ятому розділі в рамках уведеної та обґрунтованої в першому розділі аксіоматики узагальненої теорії побудови k-значних структур розв'язана проблема розробки принципів побудови пристроїв зовнішнього обміну. Для вирішення цієї проблеми були поставлені і розв'язані такі задачі розроблення та дослідження методів математичного моделювання: класифікація методів побудови й синтезу просторових k-значних структур; створення узагальненого методу рекурсивного структурного й формального синтезу ПЗО; розроблення методів побудови рекурсивних інтегральних струмових та потенційних ПЗО; реалізація методів структурного та логічного синтезу просторових комутаторів k-значних сигналів. Ці задачі до цього часу не мали свого вирішення для k-значних структур. Це не давало можливості практичного застосування k-значних структур для створення новітніх поколінь високоефективних обчислювальних засобів.

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