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

ІНСТИТУТ ПРОБЛЕМ МОДЕЛЮВАННЯ В ЕНЕРГЕТИЦІ ім. Г.Є.ПУХОВА

Пантєлєєва Наталія Миколаївна

УДК 681.3.14/21:519.713

МЕТОД СИНТЕЗУ ЦИФРОВИХ ПРИСТРОЇВ ЗА УМОВАМИ НАДІЙНОСТІ НА ОСНОВІ АЛЬТЕРНАТИВНИХ ФОРМ ПРЕДСТАВЛЕННЯ ІНФОРМАЦІЇ

Спеціальність 05.13.05 – “Елементи та пристрої обчислювальної техніки та систем керування”

АВТОРЕФЕРАТ

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

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

КИЇВ – 2003

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

Робота виконана на кафедрі загальнотехнічної підготовки Черкаського інституту управління при Черкаської академії менеджменту Асоціації навчальних закладів України недержавної форми власності.

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

Кочкарьов Юрій Олександрович,

Черкаський інститут управління,

зав. кафедрою загальнотехнічної підготовки

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

доктор технічних наук, професор Додонов Олександр Георгійович, Інститут проблем реєстрації інформації НАН України, заступник директора.

кандидат технічних наук Арістов Василь Васильович, Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України, провідний науковий співробітник.

Провідна установа

Національний технічний університет України “КПІ” Міністерства науки і освіти України, факультет електроніки, кафедра конструювання та виробництва електронно - обчислювальних засобів, м.Київ.

Захист відбудеться “28” жовтня 2003р. о “14.00” год. на засіданні спеціалізованої вченої ради К .185.02 Інституту проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України за адресою: 03164, м.Київ, вул. Генерала Наумова,15

З дисертацією можна ознайомитись у бібліотеці Інституту проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України за адресою: 03164, м.Київ, вул. Генерала Наумова,15

Автореферат розісланий “18” вересня 2003р.

Вчений секретар спеціалізованої вченої ради

кандидат технічних наук Е.П. Семагіна

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

Актуальність роботи. Постійне розширення галузі застосування засобів обчислювальної техніки і систем керування, побудова складних систем централізованого та розподіленого керування, в яких цифрові пристрої і системи є їх невід’ємною частиною, збільшення обсягів переданої та обробленої інформації призводять до зростання вимог по забезпеченню надійності. Вирішення даної проблеми можливе завдяки підвищенню надійності елементної бази, введенню різних видів надмірності, оптимізації логічних структур, поліпшенню технічного обслуговування на основі розробки ефективних методів прогнозування. Питання, які пов‘язані з вивченням, проектуванням та використанням цифрових елементів, вузлів та пристроїв для засобів обробки інформації, розглядались у роботах В.М.Глушкова, А.Д. Закревського, С.І. Баранова, В.А. Склярова, В.В. Соловйова, Є.П. Угрюмова, П.М. Бибила та ін. Значна частина методів забезпечення надійності засобів обчислювальної техніки ґрунтується на надмірності – апаратній або інформаційній. Аналіз існуючих методів забезпечення надійності на основі штучного введення апаратної надмірності, показав, що більшість з них призводять до погіршення показників швидкодії, складності, енергоспоживання; порушують ітераційність, модульність апаратури та роблять її менш технологічною з точки зору сучасної елементної бази. Можливості забезпечення високого рівня надійності завдяки лише апаратній надмірності на сучасному етапі можна вважати вичерпаними. Разом з тим дослідження альтернативних форм представлення логічних функцій виявило необхідність впровадження їх у практику проектування сучасних логічних структур цифрових пристроїв окремо або спільно з класичним базисом. Значний внесок у вирішення проблеми створення надійних систем керування за допомогою інформаційної надмірності, а саме кодування інформації, зроблено науковцями Дж. Фон Нейманом, К. Шенноном, Дж.Поуєном, С. Виноградовим, М.О. Гавриловим, О.П. Стаховим, Є.І. Брюховічем, Ю.Г. Дадаєвим та ін. Аналіз існуючих кодових систем свідчить, що їх властивості залежать від рівня надмірності. Так, негативним наслідком збільшення надмірності є підвищення інтенсивності потоку помилок, збільшення ймовірності виникнення помилок, зменшення ймовірності їх корекції. Тому перспективним напрямком досліджень є синтез кодів, які були б оптимальні з точки зору рівня надмірності, корегувальних здібностей, швидкості передачі і обробки інформації.

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

Зв‘язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконувалась згідно з планом науково-дослідних робіт Черкаського інституту управління при Черкаській академії менеджменту протягом 1998-2003рр., а також безпосередньо пов‘язана з держбюджетною НДР з теми №41 “Дослідження ізоморфізму логічних та кусково-постійних функцій” (номер державної реєстрації 0102U005507) за 2002-2003рр. Результати роботи відображено у звітах з науково-дослідної роботи академії.

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

§

§

§

§

§

Об'єкт дослідження – цифрові пристрої в системах обробки інформації реального часу.

Предмет дослідження – синтез цифрових пристроїв за умовами надійності на основі альтернативних форм представлення інформації.

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

Наукова новизна отриманих результатів полягає у наступному:

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

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

3. Розроблено метод мінімізації логічних функцій, представлених у вигляді поліномів Ріда-Мюллера (матричний метод міжбазисних переходів). Запропоновано розв‘язання класичної задачі мінімізації логічних функцій для альтернативних форм представлення, а саме у формі поліномів Жегалкіна шляхом зведення до розв’язання задачі лінійного програмування.

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

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

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

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

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

Теоретичні та практичні результати дисертаційної роботи використані та впроваджені в:

§

§

§

Особистий вклад здобувача. У друкованих працях, опублікованих у співавторстві, автору дисертації належать: [1] – огляд існуючих методів і розробка нового методу мінімізації ЛФ у класі поліномів РМФП, програмна реалізація повної множини ЛФ, графічне і табличне представлення результатів критеріального аналізу повної множини ЛФ у класичному і альтернативному базисах; [2] – процедура міжбазисного прямого і зворотного переходу між класичним базисом і РМФП; [4] – рішення задачі мінімізації ЛФ у базисі поліномів Жегалкіна як розв‘язання задачі лінійного програмування; [5] – критеріальний аналіз структури множини РМФП; [6] – розрахунок і аналіз границь можливого зменшення площі ПЛМ за рахунок введення альтернативної форми представлення; [7, 13]– оцінка потужності підмножин пріоритетів з урахуванням складності ПЛМ2; [8]–розрахунок і аналіз питомих ваг і границь підмножин пріоритетів у залежності від кількості аргументів та критеріальних оцінок; [9]– дослідження потужності об’єднань підмножин пріоритетів з урахуванням коефіцієнта схемотехнічного ускладнення ПЛМ; [10] –огляд методів синтезу кодів, узагальнені аналітичні залежності розрахунку основних характеристик структурних кодів; [11]–визначення відносного утримування підмножин пріоритетів і таблиць множення; [12] – розрахунок і аналіз зміни потужності підмножин пріоритетів для класичної і альтернативної форм представлення ЛФ; [14] – розрахунок і аналіз бінарних форм представлення ЛФ. Одна стаття [3] висвітлює результати, що отримані здобувачем особисто.

Апробація результатів дисертації. Основні положення і результати дисертаційної роботи доповідалися і обговорювалися на конференціях, семінарах, радах, у тому числі на: науково-практичних конференціях і семінарах Інституту проблем моделювання в енергетиці НАН України, Київ, 1998-2001р.; п'ятій міжнародній конференції “Advanced Computer Systems”, Szczecin, Poland, November 1998р.; шостій міжнародній науково-практичній конференції “Сучасні інформаційні та енергозберігаючі технології життєзабезпечення людини – СИЭТ6-99”, Харків, 1999р.; міжнародних науково-технічних конференціях “Проблеми фізичної і біомедичної електроніки”, НТТУ “КПІ”, Київ, 1998-2003рр.; конкурсі наукових праць, що проводився Ассоціацією навчальних закладів України недержавної форми власності у 2001р. (диплом за ІІІ місце з монографію “Классические и альтернативные минимальные формы логических функций: Каталог-справочник”).

Публікації. Основні положення і результати дисертаційних досліджень викладені в 14 публікаціях, з яких одна монографія; 9 статей у журналах та збірниках наукових праць, що надруковані у виданнях, які входять до переліку фахових; 3 тез доповідей на наукових конференцій. Публікації відповідають вимогам ВАК України.

Структура й обсяг дисертації. Дисертація складається з вступу, чотирьох розділів, висновків, списку використаної літератури, трьох додатків. Загальний обсяг дисертації 253 сторінки. Основний зміст викладений на 163 сторінках, у тому числі на 42 сторінках розміщено: 59 таблиць, 33 рисунки. Список використаної літератури з 119 найменувань. Додатки на 83 сторінках.

ОСНОВНИЙ ЗМІСТ РОБОТИ

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

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

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

, (1)

де– загальна кількість вузлів цифрових пристроїв , охоплених контролем і корекцією; –

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

Для оцінки достовірності функціонування систем доцільно використовувати показник імовірності отримання достовірного результату

, (2)

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

, (3)

де – умовна ймовірність виявлення помилок, – умовна ймовірність виправлення помилок.

Розглядаючи цифрові пристрої на рівні структурних схем, будемо оцінювати функціональну повноту і складність через реалізацію ЛФ, використовуючи для цього критеріальні оцінки. Оскільки логічний синтез передбачається виконувати також у базисі ПЛМ, то для оцінки і порівняння функціонального опису, якості мінімізації і складності реалізації використовуються критерії: SL–кількість букв у записі ЛФ; SAD–кількість доданків у записі ЛФ; SSH–кількість шин; SS–габаритна площа і SAC–площа активних елементів ПЛМ1. Для кожного з вищенаведених критеріїв раніше введений відносний показник ефективності форми представлення ЛФ (ФП ЛФ), що являє собою середнє значення ймовірності реалізації ЛФ за обраним критерієм:

(4)

де – кількість ЛФ, реалізованих на ПЛМ, при заданому значенні відповідного критерію; – повна кількість ЛФ заданого числа аргументів n; – максимальне значення обраного критерію для усіх ФП, яке забезпечує реалізацію всіх ЛФ.

Коефіцієнт зміни ймовірності безвідмовної роботи, що враховує схемну реалізацію ЛФ у заданій формі представлення, визначається як

, (5)

де – мінімальна форма ЛФ; – імовірність безвідмовної роботи i-го функціонального елемента; – форма представлення ЛФ; – кількість функціональних елементів, що використовуються для реалізації синтезованої схеми.

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

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

На основі проведеного аналізу кодових систем і методів кодування інформації, які забезпечують інформаційну надійність, визначено, що стійкі до перешкод коди, які традиційно використовуються в синтезі, мають недоліки. Тому пропонується для розв‘язування наукових задач використовувати структурні коди. Існуюче поняття структурного коду як коду, для усіх комбінацій якого існує правило чергування символів, не дозволяє використовувати єдиний підхід до синтезу і аналізу кодів та пристроїв на їх основі. Тому було запропоновано поняття базової групи, якою називається мінімальний набір комбінацій символів, що допускаються в структурному коді. Тоді структурним кодом (СК) називатимемо код, синтезований на основі принципу чергування груп однойменних символів. Показниками оцінки СК визначені деякі якісні характеристики. Приватні якісні характеристики СК: потужність кодів довжиною n - і кількість одиниць у кодах довжиною n - . Загальні якісні характеристики: функція СК, що визначає алгоритм синтезу СК; потужність n-розрядного коду; кількість одиниць у n- розрядному коді; частка одиниць у розряді коду; кількість нулів у n-розрядному коді; вагозначимість коду.

З урахуванням якісних характеристик СК їх можна класифікувати і розподілити на такі кодові сукупності (рис.1). |

Для кожного СК заданого БГ існує вираз для розра-хунку його харак-теристик. Так, якщо СК з ОСС заданий БГ, яка утримує h слів і k1,k2,…,kh – кількість символів

Рис. 1

у кожному слові, m1,m2,…,mh – кількість одиничних символів у кожному слові, і при , , тоді:

?

, (6)

?

, (7)

?

(8)

Запропонований новий матрично-аналітичний метод синтезу СК, на відміну від існуючих, спрощує алгоритм синтезу завдяки зміщенню операції виключення неприпустимих кодових слів та однозначно визначає алгоритм доповнення нових кодових слів до синтезованої кодової послідовності. Основними операціями методу є: вибір вихідної структурної форми, враховуючи вимоги надійності і надмірності; визначення БГ СК; синтез кодових слів початкових значень чисельного ряду; визначення функції коду; аналітичний розрахунок параметрів коду (6-8); визначення вагозначимості коду, розрахунок вагових коефіцієнтів, які визначають алгоритми виконання арифметичних операцій. Серед множини СК визначені групи кодів, які синтезовані на основі послідовного вибору з безнадлишкового двоїчного коду комбінацій символів, що відповідають вимогам БГ і мають однакові функції потужності кодів. Такі коди будемо називати альтернативними структурними кодами (АСК). З точки зору потужності пакетів “1” підмножину кодів АСК можна розглядати як сукупність 1-АСК, 2-АКС, … m-АСК кодів. Перетворення n-АСК у m-АСК, де n і m є натуральними числами при логічному стану входу, визначаються математичною моделлю виходу , де h– порядковий номер входу/виходу:

(9)

Математична модель пристрою виявлення помилок визначається виразом

(10)

Математична модель пристрою виправлення помилок визначається виразом

(11)

Математична модель пристрою перетворення 2-АСК у 3-АСК на підставі (9) визначатиметься виразом

. (12)

Математична модель пристрою- кодеру з виправленням помилок, що перетворить 3-АСК у 2-АСК, при відомому векторі помилок визначається виразом:

. (13)

Дослідження свідчать, що аналогічний відсоток виправлення помилок дає декодер 3-АСК у 2-АСК при наявності сигналу помилки, математична модель якого визначається як

(14)

Запропонований метод корекції інформації в альтернативних структурних кодах (АСК) полягає у виконанні таких операцій: знаходженні непоправних помилок в 2-АКС, перетворенні 2-АСК в 3-АСК, повторному виконанні операції в 3-АСК; декодуванні 3-АСК в 2-АСК з корекцією помилок.

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

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

Питання забезпечення надійності пов‘язане з розв‘язанням задачі оптимізації логічних структур, а саме задачі мінімізації. Проведено огляд методів мінімізації ЛФ, що представлені поліномами по mod2. Пропонується новий метод формування поліномів РМФП із використанням матриць міжбазисних переходів, особливістю якого є використання спеціального РМ-перетворення та процедури одержання поляризованої матриці переходу. Рівняння перетворення у даному випадку має вигляд:

, (15)

де n – кількість аргументів ЛФ; і - номер ЛФ множини L(n); - вектор полінома Ріда- Мюллера відповідно вектору поляризації множини, - процедура перетворення, яка виконується над матрицею переходу для заданого вектора поляризації, - вектор i-й ЛФ от n-аргументів у класичній формі представлення.

Розглядається можливість розв‘язання задачі мінімізації ЛФ у формі позитивно поляризованих поліномів Жегалкіна до оптимізаційної задачі лінійного програмування. Задачу можна вирішити, використовуючи канонічне Ф-перетворення кожного аргументу ЛФ, заміною алгебраїчної суми сумуванням по mod2 на основі формул ізоморфізму, приведенням подібних членів і отриманням представлення ЛФ у вигляді поліномів Жегалкіна. Методи використовувалися при програмній реалізації для формування повної множини поліномів Ріда-Мюллера з урахуванням вектора поляризації та критеріальних оцінок. Результати дослідження повної множини поліномів Ріда-Мюллера дозволили виділити окремі класи поліномів з урахуванням довжини кон‘юнкції і вектора поляризації, визначити потужність кожного класу та підкласу. Так, зазначені наступні класи поліномів: позитивної полярності (поліноми Жегалкіна), негативної полярності, фіксованої полярності, довільної полярності. Для кожного класу поліномів можливо також зазначити групи рівнозначних та нерівнозначних поліномів. Проведене дослідження РМФП як складової ОФП, а саме: вплив вектора поляризації на структуру множини ЛФ у РМФП; порівняльний аналіз двох форм представлення – КФП і РМФП за критеріями мінімізації. Результати аналізу свідчать, що продуктивність нульового вектору поляризації, якій відповідає поліномам Жегалкіна та нульовій індексній групі, дорівнює 17,89% при n=3 і 8% при n=4. Продуктивність одиничної індексної групи, де можливе використання однієї змінної в інверсному вигляді, дорівнює 40,63% при n=4. Таким чином, використання поліномів Ріда-Мюллера в синтезі логічних структур повинно здійснюватись з урахуванням вектору поляризації.

Виконана класифікація, яка визначила такі класи альтернативних ФП: унарні, бінарні та тернарні. До класу унарних належать ФП - КФП, АФП та РМФП, які є повними і дозволяють реалізовувати повну множину ЛФ. До класу тернарніх належить ОФП, яка об’єднує усі унарні ФП з попередньою оптимізацією по визначеним критеріям. У роботі особлива увага приділяється бінарним ФП: алгебро-класичній (БАКФП), алгебро-Ріда-Мюллерівській (БАРМФП), Ріда-Мюллерівсько-класичній (БРМКФП). Також до бінарних ФП віднесені форми, в яких тільки одна ФП є повною: бінарна безінверторна класична ФП з АФП (БИКАФП= БИКФП+ АФП); бінарна безінверторна класична ФП із РМФП (БИКРМФП= БИКФП+ РМФП); бінарна безсуматорна АФП із класичною ФП (БСАКФП= БСАФП+ КФП); бінарна безсуматорна АФП з РМФП (БСАРМФП). Сутність дослідження полягає у визначенні найкращої форми представлення ЛФ з погляду забезпечення мінімальних значень для показників складності реалізації. Проведений розрахунок ефективності усіх форм представлення та їх об'єднань доданий у табл.1.

Досліджена динаміка зміни потужності підмножин пріоритетів тернарної ОФП у залежності від росту кількості аргументів і вихідного розподілу потужності підмножин пріоритетів унарних АФП, КФП і РМФП (табл.2). Результати порівняльних розрахунків повних множин ЛФ (n=3,4) табл.1,2 свідчать, що класи бінарних форм за більшістю критеріїв мають перевагу і можуть розглядатись як рівноправні поряд з унарними формами. Аналіз ефективності форм представлення і потужності підмножин пріоритетів свідчить про те, що динаміка зміни потужності підмножин пріоритетів класичної форми має явно убуваючий характер зі збільшенням n, відносна потужність підмножини складає більш, ніж 95% та забезпечує дійсний мінімум площі (показники SS і SАС) у більшості випадків.

Таблиця 1

Форма | Крітеріальні показники ефективності і потужність підмножин приоритетів

N=3 | N=4

SAD | SS | SAC | KLASIC % | ALTER% | SAD | SS | SAC | KLASIC % | ALTER%

КФП | 0,74 | 0,45 | 0,53 | - | - | 0,74 | 0,49 | 0,50 | - | -

АФП | 0,69 | 0,67 | 0,85 | - | - | 0,64 | 0,65 | 0,77 | - | -

РМФП | 0,70 | 0,68 | 0,85 | - | - | 0,66 | 0,66 | 0,76 | - | -

БАКФП | 0,839 | 0,672 | 0,839 | 28,52 | 71,48 | 0,644 | 0,62 | 0,74 | 1,53 | 98,47

БРМКФП | 0,844 | 0,694 | 0,844 | 31,25 | 68,75 | 0,746 | 0,538 | 0,561 | 3,98 | 96,02

БАРМФП | 0,871 | 0,702 | 0,871 | - | 100 | 0,682 | 0,657 | 0,766 | - | 100

БИКАФП | 0,661 | 0,672 | 0,84 | 28,52 | 71,48 | 0,645 | 0,622 | 0,738 | 3,27 | 96,73

БИКРМФП | 0,682 | 0,695 | 0,844 | 31,64 | 68,36 | 0,659 | 0,635 | 0,727 | 4,13 | 95,87

БСАКФП | 0,716 | 0,492 | 0,584 | 62,89 | 37,11 | 0,742 | 0,479 | 0,484 | 95,20 | 4,80

БСАRMФП | 0,678 | 0,673 | 0,867 | - | 100 | 0,66 | 0,636 | 0,729 | - | 100

Таблиця 2

N | Підмножини пріоритетів множини за критерієм SS

1.

5 | 0,0015 | 0,3151 | 0,3895 | 0,0048 | 0 | 0,2763 | 0,0130

6 | 0,0023 | 0,2573 | 0,4496 | 0,0085 | 0 | 0,2579 | 0,0120

…

12 | 0,0009 | 0,1926 | 0,5628 | 0,0051 | 0 | 0,2187 | 0,0072

13 | 0,0009 | 0,1909 | 0,5663 | 0,0051 | 0 | 0,2175 | 0,0070

14 | 0,0009 | 0,1897 | 0,5686 | 0,0050 | 0 | 0,2167 | 0,0070

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

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

§

§

Рис. 3

§

§

§

§

§

§

§

§

§

§

§

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

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

, (18)

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

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

, (19)

де – імовірність виникнення помилки при перехідних процесах.

Для аналізу було обрано чотири СК заданих БГ. Для кожної БГ було синтезовано код і визначені його якісні характеристики. В якості традиційних кодів обрані: беззбитковий двійковий код, беззбитковий двійковий код з контролем на парність і арифметичний код на основі модуля 5. Для каналів обробки інформації відношення ймовірності виникнення помилки в СК і ймовірності виникнення помилок у двійковому беззбитковому коді, з урахуванням статико-динамічного режиму роботи пристроїв обробки, визначається як

. (20)

Результати розрахунків свідчать про те, що застосування СК у каналах передачі, зберігання і обробки інформації призводить до зменшення ймовірності виникнення помилок. Так, наприклад, при значенні ймовірності виникнення помилки 0,3 для переходу пристрою з “0” в “1” і при значенні ймовірності виникнення помилки у момент переключення логічного елемента 0,99 відносна ймовірність виникнення помилки дорівнює 0,04–0,05. Для каналів обробки інформації за тих самих умов відносна ймовірність виникнення помилки дорівнює 0,07–0,1. Запропоновані математичні вирази кількісної оцінки моделі помилок для означених СК, кількісних характеристик властивостей СК щодо виявлення і корегування помилок. Проведена оцінка змін імовірності виникнення помилок з урахуванням відшукувальних аналітичних здібностей альтернативних структурних кодів та їхнього впливу на узагальнену ймовірність безвідмовної роботи цифрових пристроїв. Отримані аналітичні залежності дозволяють підібрати оптимальний СК, який найбільш повно відповідає реальним фізичним каналам і умовам виникнення помилок. З практичної точки зору, це дозволяє адаптувати форму представлення інформації під існуючу модель пристрою, елементну базу і технологію виробництва, що дозволить значною мірою досягти мінімального значення потоку збоїв і відмов.

Впровадження альтернативних ФП ЛФ вимагає оцінки схемотехнічного ускладнення реалізації логічних структур. Для оцінки відносного схемного ускладнення елементів об’єднання кон‘юнкцій введено коефіцієнт , котрий можна розглядати як коефіцієнт схемної надмірності відповідно до кожної з альтернативних форм. Для оцінки змін площі ПЛМ уведений коефіцієнт , якій є відношенням площ ПЛМ2, котрі займані відповідно елементами додавання кон‘юнкцій у альтернативної і класичній формах представлення. Розрахункові результати аналізу множини ЛФ з точки зору оцінки впливу збільшення коефіцієнту і збільшення кількості аргументів n на площу ПЛМ і потужність підмножин пріоритетів свідчать, що, наприклад, для n=32 і <=15 більше половини всієї множини ЛФ доцільно реалізовувати в альтернативних формах, що, в свою чергу, приводить до зменшення площі ПЛМ1. Використання унарної КФП для реалізації пристроїв за допомогою ПЛМ забезпечує мінімальність площини ПЛМ менш ніж на 10%.

ВИСНОВКИ

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

1.

Проведено класифікацію структурних кодів, виділено і визначено основні кодові сукупності, аналітичні залежності розрахунку якісних і кількісних показників структурних кодів.

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

2.

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

3.

4.

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

5.

6.

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

7.

8.

СПИСОК ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1.

2.

3.

4.

5.