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

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

Національна академія наук України

Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова

Автореферат

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

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

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

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

Казарінова Наталія Леонідівна

Київ 2002

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

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

Науковий керівник: Доктор технічних наук, професор Кочкарьов Юрій Олександрович, Черкаський інститут управління, зав. кафедри загальнотехнічної підготовки

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

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

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

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

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

Захист відбудеться 11 квітня 2002 р. о 1400 годині на засіданні спеціалізованої вченої ради

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

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

Автореферат розісланий " 6 " березня 2002 р.

Учений секретар спеціалізованої вченої радиК 26.185.02, к.т.н. Семагіна Е. П.

1. Загальна характеристика роботи

цифровий ізоморфізм кусковий

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

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

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

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

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

Основні задачі, що визначаються поставленою метою:

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

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

- проаналізувати існуючі функціонально-повні базисні системи з точки зору вибору оптимального (з усіх розглянутих ФП) запису ЛФ;

- розробити методи мінімізації ЛФ в альтернативних базисах, запропонувати прагматичні критерії оцінки мінімальної реалізації класичної й альтернативних ФП;

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

Об'єктом дослідження є повна множина логічних функцій від n аргументів L(n), які використовуються для синтезу й оптимізації структур елементів обчислювальної техніки на основі спільного використання класичних і альтернативних ФП ЛФ.

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

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

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

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

2. Розроблено апарат дослідження структури повної множини логічних функцій, проведена точна оцінка потужності і границь підмножин пріоритетів класичної й альтернативної форм представлення ЛФ, у тому числі з урахуванням особливостей схемної реалізації ЛФ в альтернативних формах. Введено критерії оцінки ефективності різних ФП і визначені області ефективного використання альтернативних ФП в проектуванні елементів і пристроїв обчислювальної техніки.

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

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

5. Розроблено підхід до апріорного вибору оптимальної ФП для конкретного завдання ЛФ на основі спеціально створеного математичного апарату булєво-генетичної алгебри.

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

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

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

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

- розроблена і експериментально досліджена на моделюючому стенді мікрозбірка спеціального використання, проведена модифікація мікросхеми 556РТ5; роботи виконувались спільно з НВК "Фотоприлад".

Розроблений програмний комплекс, запропоновані методи синтезу для проектування елементної бази пристроїв та інші результати дослідження впроваджені в НВК "Фоторилад", Черкаському інженерно-науковому центрі та у навчальний процес у Черкаському інституті управління для студентів спеціальностей "Економічна кібернетика", "Електроніка", "Електронні апарати". Акт впровадження додається.

Зв'язок роботи з науковими програмами, темами. Одержані результати дисертаційної роботи пов'язані з темою № 41 наукової роботи Черкаського інституту управління: “Дослідження ізоморфізму логічних і кусочно-постійних функцій” (1998-2001 р.р.).

Особистий внесок здобувача

У роботі [1] автору належить програмна реалізація повної множини ЛФ усіх форм представлення, аналіз потужності підмножин пріоритетів, мінімізація в АФП; у роботі [2] автору належить розробка методів прямого і зворотного переходу представлення ЛФ між класичним і алгебраїчним базисами; у роботі [4] автору належить реалізація задачі лінійного програмування для мінімізації ЛФ в алгебраїчної формі представлення (АФП); у роботі [5] автору належить кількісний аналіз потужності підмножин класичної й альтернативних ФП; у роботі [6] автору належать розрахунки й аналіз породжених ЛФ на основі булєво-генетичної алгебри для класичної форми представлення (КФП) і алгебраїчної ФП; у роботі [7] автору належить формування масивів оптимізованих ФП і аналіз ефективності отриманої ФП; у роботі [8] автору належить проведення розрахунків і аналіз отриманих результатів питомої ваги множини альтернативних і класичної реалізацій. Одна стаття [3] видана без співавторів.

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

- Науково-практичних конференціях і семінарах Інституту проблем моделювання в енергетиці НАН України, Київ, 1998-2001.

- Щорічних науково-технічних конференціях "Проблеми фізичної і біомедичної електроніки", НТУУ “КПІ”, Київ, 1998-2001.

- П'ятій міжнародній конференції Advanced computer systems, Szczecin, Poland, November 1998

Публікації. Основні положення і результати дисертації відображені в 10 публікаціях, з них одна монографія; 7 робіт опубліковано в наукових виданнях, що входять до переліку фахових.

Структура й обсяг дисертації Дисертація складається з вступу, чотирьох розділів і додатків; всього 162 аркуш машинописного тексту, 31 ілюстрацій, 53 таблиці, 64 аркуша додатків, 106 найменування використаних джерел.

2. Основний зміст роботи

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

У першому розділі проводиться дослідження методики і засобів синтезу на етапі логічного проектування цифрових елементів і пристроїв. Дається огляд функціонально повних систем логічних елементів (операцій), з яких можуть бути побудовані будь-які комбінаційні схеми (КС). Досліджується реалізація мінімальної ЛФ від заданого числа n аргументів у класичній і в альтернативних формах представлення: класична форма представлення (КФП чи C) - система ЛФ AND-OR-NOT; алгебра Жегалкіна - система ЛФ AND-сума по mod2; Ріда-Мюллера ФП (РМФП чи RM), оскільки поліноми Жегалкіна, є частковим випадком більш загальної множини поліномів Ріда-Мюллера. Крім цього розглядається так звана алгебраїчна форма представлення (АФП чи A), як результат Ф-перетворення ЛФ в еквівалентні кусочно-постійні функції (КПФ).

Поліноми Ріда-Мюллера в загальному виді можна записати:

,

де - кон'юнкції вхідних аргументів чи їх заперечень;

- коефіцієнти полінома, що приймають значення 0 чи 1.

В канонічних поляризованих поліномах, що є узагальненням поліномів Жегалкіна, запис і операції над ЛФ здійснюються в алгебраїчній системі по mod2 з урахуванням так званого вектора поляризації, де частина чи всі аргументи ЛФ можуть бути інвертовані (поляризовані).

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

,

де - аргументи ЛФ; - відповідні їм КПФ

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

Введені базисні системи. Q-базис - n систем q-функцій, визначених у 2n мірному просторі КПФ, що у багатьох випадках є найбільш переважним для представлення логічних функцій у відповідні їм функції Ф(x). Застосування Q-базису ліквідує процедуру перебування коефіцієнтів розкладання в ортогональний ряд, тому що в зв'язку з властивістю Q-базису величини коефіцієнтів Q-рядів визначаються:

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

(1)

Вираз (1) містить 2n лінійно-незалежних складових, що являють собою базисну систему , за якою розкладається будь-яка функція . Дану систему будемо називати S-базисом. Система S-функцій n-го порядку складається з 2n функцій і для різного числа n може бути побудована рекурентно.

Використання S - базису відповідає уявленню ЛФ, а, точніше, її Ф- зображення в АФП, тобто у виді:

(2)

де - аргументи ЛФ; - відповідні цим аргументам КПФ

З використанням цього базису, будь-яку ЛФ n аргументів можна представити у виді лінійної комбінації S функцій (S- ряду).

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

Виходячи з вище сказаного, перехід від однієї форми ЛФ до іншої може трактуватися як зміна базису чи, що те ж саме, як перетворення координат ЛФ, тому що коефіцієнти Q-, S- і G-рядів можна розглядати як координати ЛФ у відповідному базисі.

Основні задачі дослідження альтернативних ФП.

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

Запропоновано розбити повну множину ЛФ від n аргументів (позначимо його як L(n)) на наступні чисті підмножини: С - підмножину ЛФ, для яких найбільш доцільна КФП; А - підмножина ЛФ, для яких найбільш доцільна АФП; RM - підмножина ЛФ, для яких найбільш доцільна РМФП.

Крім того, введено перехідні підмножини: СА - підмножина ЛФ, для яких однаково доцільні як КФП, так і AФП; CR - підмножина ЛФ, для яких однаково доцільні як КФП, так і РМФП; AR - підмножина ЛФ, для яких однаково доцільні як AФП, так і РМФП; CAR - підмножина ЛФ, для яких однаково доцільні будь-які форми представлення.

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

Відзначено, що з погляду реалізації конкретної ЛФ значення критеріїв можна розглядати як показники складності реалізації ЛФ, що, природно, залежать від обраної ФП.

У зв'язку з цим набуває не лише наукового, але і практичного інтересу питання - як часто можуть зустрітися на практиці ЛФ, для яких доцільна реалізація в альтернативних формах, тобто в АФП чи РМФП. Зазначені підмножини будемо називати підмножинами пріоритету (ПП) тієї чи іншої ФП.

Відзначено можливість використання Шеноновського каскадного розкладання релейно-контактних елементів у наступному виді:

. (3)

Розглядаючи (3) у зворотному порядку, тобто трактуючи вираження (3) як композицію ЛФ n аргументів із двох що породжують ЛФ (ПЛФ) n-1 аргументів.

Для РМФП аналогічне вираження:

. (4)

Для АФП має місце вираження:

, (5)

де Ф(х) - вид ЛФ, що шукається;

Ф(0) - верхня половина Ф-зображенння таблиці істинності ЛФ, що шукається;

Ф(1) - Ф-зображення нижньої половини ЛФ, що шукається.

Таким чином, у всіх ФП ЛФ маються аналоги (3), що дозволяють будь-яку ЛФ від n аргументів у будь-який ФП розглядати як композицію двох ПЛФ від n-1 аргументів.

В розділі запропоновано для вирішення питання спрощення структури цифрових елементів розглядати безліч L(n) як об'єднання підмножини пріоритетів К-, А-, РМ-, КА-, АР-, КР - та КАР-типів, а також запропоновано набір показників складності реалізації ЛФ для оцінки означених форм представлення ЛФ. Доведена проста методика перетворення ФП на основі відповідних матриць, вказані аналоги розкладу Шеннона в усіх ФП, необхідні для їх спільного використання.

В другому розділі розглядається альтернативні ФП пропонується розглядати не як конкурентні, а як опціонні форми реалізації ЦА, що дозволяють розроблювачу для кожної конкретної ЛФ вибрати найбільш просту структуру, тобто мінімальну реалізацію ПЛМ. Очевидно, що границі зазначених підмножин залежать від обраного варіанта критерію мінімізації.

Передбачається, що метою раціонального вибору форми представлення ЛФ є зменшення площі підматриці ПЛМ1.

В існуючих методах мінімізації (діаграма Вейча, Квайна-Мак-Класки, Блека-Порецького і т.д.) з ростом числа аргументів ускладнюється процес перебору находження МДНФ. Безсумнівний інтерес представляють наближені методи одержання МДНФ.

Сформульовано задачу мінімізації в АФП, як розгляд коефіцієнтів неканонічного S-ряду, що задовольняє мінімуму обраного критерію якості (SS, SAC, SAD, SSH, SL).

З використанням Ф-перетворень, що з погляду реалізації ЛФ відповідають АФП, задачу мінімізації ЛФ можна звести до класичної задачі лінійного програмування (ЗЛП). Задача зводиться до пошуку мінімуму цільової функції:

,. , (6)

- ki - коефіцієнти ваги цільової функції (ЦФ), що залежать від обраного критерію якості.

Таким чином, зазначене рішення можна одержати наступними способами:

- задати ЛФ від n аргументів і критерій оцінки якості мінімізації; (канонічне Ф-перетворення кожного аргументу ЛФ, заміна логічних операторів алгебраїчними на основі формул ізоморфізму і приведення подібних членів, що дозволяє одержати канонічне представлення ЛФ у S-базисі;);

- формування вектора вагових коефіцієнтів (залежить від критерію якості);

- формування цільової функції G;

- формування матриці , що представляє систему обмежень;

- рішення типової ЗЛП із канонічною правою частиною (з неканонічною правою частиною) пакетом ПП і визначення вектора - вектор невідомих коефіцієнтів S-ряду;

- висновок вектора отриманого показника якості.

Мінімізація з використанням вектора поляризації

Поляризованою поліноміальною ФП, чи поляризованою арифметичною формою представлення (ПАФП) - будемо називати арифметичний поліном функції F(x), представлений вектором коефіцієнтів Si ряду, як результат канонічного перетворення, у доданку якого одна частина перемінних входить тільки з запереченням, а інша - без заперечення. Перемінні xi (1<=i<=n) входять до складу F(x) без заперечення тільки при векторі поляризації Vp=0.

Відзначимо, що задана ЛФ із заданим вектором поляризації Vp - це інша ЛФ із нульовим V0. Звідси випливає задача використання поляризованих поліномів при рішенні задачі мінімізації. Основним математичним апаратом для рішення задач мінімізації з урахуванням вектора поляризації, є матричний апарат. Задачі дослідження мінімальних реалізацій ЛФ в АФП із використанням вектора поляризації:

- генерація масиву ЛФ при Vp=0;

- пошук номера ЛФ по заданому Vp;

- створення масиву поляризованих ЛФ;

- аналіз росту мінімальних реалізацій з використанням Vp;

- аналіз продуктивності мінімальних реалізацій для кожного Vp.

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

У табл.1 приведені результати розрахунків.

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

Метод приведених коефіцієнтів. Розробка направленопереборного алгоритму мінімізації ЛФ в АФП на підставі дослідження й аналізу властивостей множини Ci коефіцієнтів S-ряду.

Індекс входження (ІВ) Ci члена S-ряду розраховується як відношення:

kpi=[(Pp-Po)/nc], (7)

де kpi - індекс входження для всіх коефіцієнтів S-ряду множини L(n);

nc - число усіх входжень у систему нерівностей з будь-якими знаками.

У результаті сформована множина kpi, число значень якої обмежено для множини L(n). Аналіз розподілу значень Ci у залежності від введеного показника kґpi дозволив сформулювати метод приведених коефіцієнтів, що заснований на властивостях ІВ kpi. Алгоритм розрахунку мінімальної ЛФ (будь-якої заданої чи повної множини) в АФП з застосуванням індексу входження коефіцієнтів S-ряду приведений у роботі. Тимчасові показники розрахунку для n=3, 4 позначили зменшення часу розрахунку повної множини реалізації мінімальних ЛФ більш ніж на порядок у порівнянні із ЗЛП, як для нульової поляризації, так і для поляризованого полінома. Запропонований метод дозволяє виконувати розрахунок повної множини ЛФ для n=4 і представницьку вибірку для статистичної обробки ЛФ для будь-якого n.

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

Результати порівняльних розрахунків, приведені в таблиці 2, дозволяють робити висновок в припустимому використанні даного методу. З ростом числа n аргументів ЛФ, наближені методи розрахунку здобувають значну актуальність.

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

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

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

Для рішення питань розрахунку ефективності різних ФП використовуються введені раніше критерії якості: SAD, SSH, SL, SS, SAC. Введений відносний показник ефективності (ВПЕ), що розглядається як співвідношення площі криволінійної трапеції між реальною ФП і ідеальною ФП, для обраного показника якості, де Nj(S) - крива, що обмежується, на інтервалі зміни S[0,Smax].

За критеріями SAC (площа активних елементів) і SS (габаритна пл.) АФП і РМФП складають КФП вагому конкуренцію. Показники критеріїв SL, SS, SAD для КФП, АФП, РМФП відповідно, не спростовують точку зору на альтернативні представлення ЛФ, як на рівноправні для реалізації ЛФ. Запропонована методика і проведений аналіз дозволяють стверджувати, що альтернативні ФП конкурентноздатні і можуть розглядатися як рівноправні ФП поряд з класичною.

Проведені розрахунки дозволяють зробити висновок, що множина L(n) при досить великих значеннях n складається, в основному, із трьох мало пересічних підмножин К, A, Р и при реалізації конкретної ЛФ розроблювачу необхідно чітко уявляти, до якої підмножини відноситься кожна реалізована ЛФ чи їх система, і використовувати ПЛМ2 у відповідному виді. Питома вага підмножини, для якої доцільне збереження існуючої структури ПЛМ (кон'юнкції в ПЛМ1 і диз'юнкції в ПЛМ2), показана в табл.5.

З таблиці видно, що класична реалізація ПЛМ при n>=3 забезпечує дійсний мінімум площі ПЛМ1 (показники Ss і SAC) у незначній кількості випадків.

Можливий вид ПЛМ для застосовування ОФП наведений на рис.1.

В ПЛМ2 повинні бути шини з елементами OR, XOR, КОМПАРАТОР. Для наведеної на рис.1 структури, що лімітується фактором для функціональних можливостей ПЛМ, виявляється кількість зовнішніх виходів, тому необхідно забезпечувати можливість підключення зовнішніх виводів як вхідних, вихідних і проміжних.

Вказана структура ПЛМ дозволяє, крім розглянутих вище КФП, АФП і РМФП, реалізувати гетерогенні (змішані) ФП, в яких кон'юнкції об'єднуються в групи за допомогою одних елементів ПЛМ2, а групи потім об'єднуються іншими елементами ПЛМ2. Тут можливі наступні варіанти: класико-алгебраічна ФП (КАФП); алгебро-класична ФП (АКФП)(см. рис.2); класико-Ридо-Мюллерівська ФП (КРМФП); Рідо-Мюллерова-класична ФП (РМКФП); алгебро-Ридо-Мюллерівська ФП (АРМФП); Рідо-Мюллерова-алгебрічна ФП (РМАФП).

На рис.2 розглянута алгебро-класична гетерогенна форма представлення. Означена структура ПЛМ дозволяє, окрім розглянутої вище КФП, АФП і РМФП, АКФП реалізувати змішані ФП - КАФП, КРМФП РМКФП, АРМФП, РМАФП в яких кон'юнкції об'єднуються в групи з допомогою елементів ПЛМ2, а далі об'єднуються іншими елементами в залежності від ФП, яка реалізує ПЛМ2.

, (8)

Для n=4 k змінюється від 1 до 68, а із зростанням величини n виявлено зростання верхнього граничного значення k де технічне застосування ОФП можливо важити доцільним.

Розглянемо приклад реалізації ПЛМ в оптимізованой ФП (рис.3). Єдина матриця AND має 32 входи для подачі перемінних і два входи для подачі сигналів зворотного зв'язку з виходу мультіплексора. Кон'юнктури, що мають 68 виходів, виробляють терми, що подаються на елементи OR.

Мікросхема (рис.3) реалізована з використанням 3-х груп по чотири макроелемента в кожній - КФП, РМФП, АФП відповідно. Наведена схема дозволяє зекономити габаритну площу за рахунок зменшення числа входів з 32 в КФП до 16 в альтернативних формах подання. За рахунок комбінування своїх термів з термами сусідніх мікроелементів дозволяють одержувати логічні функції від 4, 8, 12 і 16 термів.

Реалізація проектування цифрових елементів і пристроїв обчислювальної техніки потребує вирішення проблем апріорного визначення ЛФ із до тієї чи іншої підмножини пріоритетів. Рішення цього питання привело до розробки спеціального математичного апарата, який можна віднести до класу лінійних алгебр. Зазначений апарат у роботі визначений як булєво-генетична алгебра (БГА). Елементами БГА є 7-ми мірні вектори наступного виду:

,

де речовинні ненегативні числа ( );

-n кількість аргументів множини ЛФ ;

- спеціальні символи, що грають роль одиничних векторів (ортів) у 7-ми мірному векторному просторі.

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

У роботі запропонований алгоритм статистичної перевірки гіпотез стабільності таблиці множення і структури L(n) з ростом числа аргументів ЛФ.

Кількість ЛФ, породжених зазначеними парами ПЛФ, що при цьому належать до С-підмножини, дорівнює:

,

де - частка С-функцій серед усіх ЛФ, породжених парами С-функцій з .

У такий спосіб дозволив здійснити об'єктивне порівняння продуктивності (ефективності) розглянутих у роботі ФП, для чого введено і розраховано для кожного критерію n усіх ФП відносні показники ефективності (ВПЕ). ВПЕ дозволяє аналізувати динаміку зміни ефективності будь-якої ФП із ростом n.

Таким чином, у розділі розглянуто використання ОФП на наступних етапах роботи, особливості схемної реалізації ПЛМ в ОФП, розробка спеціальної схемотехнічних рішень для елементів складання кон'юнкцій в альтернативних ФП.

Додаткове уточнення меж ПП з врахуванням схемотехнічного ускладнення елементів складання кон'юнкцій в альтернативних ФП у порівнянні з КФП дозволяє стверджувати, що завжди знайдеться кількість аргументів n для ЛФ, при яких використання ОФП стає доцільним із зростанням n, зони пріоритету ОФП поширюються. Розрахована питома вага всіх указаних ПП для L(n), причому з результатів розрахунків витікає, що загальноприйнята зараз КФП є найбільш переважною, наприклад, для критеріїв SS, SAC тільки в 1.92%, 0.21% випадків відповідно.

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

Більшість інструментальних CAD-пакетів логічного проектування (A+PLUS, MAX+PLUS, XACT, PALASM і т.д.) не враховує логічних обмежень в схемі в процесі проектування. Наповнення CAD-пакетів методикою ефективного проектування напівзамовлених і замовлених цифрових пристроїв дозволить удосконалити засоби проектування, використовуючи як типову елементну базу, так і знову створені схеми за вимогами конкретного замовника.

Представлене у роботі програмне забезпечення передбачає рішення питань проектування на рівні опису і перевірки працездатності алгоритму (комплекс програм REALIZ, MINFP, GENETIC, HEREDITY). Подальша задача - адаптація перевірених алгоритмів засобами мови орієнтованої на певну апаратуру, наприклад AHDL і ABEL (Altera HDL) або з використанням більш універсальних мов високого рівня VHDL.

На першому етапі базовими програмними модулями в складі REALIZ виконується розрахунок класичної й альтернативних ФП за заданими критеріями і заданого n в результаті роботи програм CLASSIC, AFP, RMFP.

Другий етап - робота комплексу MINFP. Програми даного комплексу дозволяють оцінити результати розрахунків за усіма ФП і визначити потужність кожної ФП (PR_FORM, PR_SVOD). При оцінці ФП, як було відзначено раніше, оптимальною може бути як одна з перерахованих "чистих" ФП, так і підмножини змішаного типу - класико-алгебраїчна; класико-рідо-мюллерівська ФП; алгебро-рідо-мюллерівська ФП; класико-рідо-мюлерово-алгебраїчна.

На третьому етапі (HEREDITY) виконуються дослідження апріорного визначення ЛФ і оптимальної реалізації кожної ЛФ для n>4, оцінка спадкоємних ознак на підставі показників за кожним критерієм функцій, що породжують.

Заключний етап дозволяє не тільки провести порівняння отриманих результатів реалізації ЛФ (декількох ЛФ, системи ЛФ) у різних формах представлення (АФП, КФП, РМФП, а також гетерогенних ФП і ОФП), але й оцінити можливе спрощення складності структури цифрового елемента, з погляду ефективності виконання заданих умов проектування. ОФП припускає оцінку можливих альтернатив і вибір форми представлення, найбільш доцільної для конкретної ЛФ.

На основі отриманих в дисертаційній роботі результатів на НВК "Фотоприлад" була проведена розробка мікрозбірки і мікросхеми спеціального застосування з використанням ОФП (рис.3). Підчас виконаних робіт були проведені розрахунки показників результуючої складності реалізації наступних виробів:

- мікрозбірка МГ16-3 приватного застосування (елемент системи управління комплексу "Буран-Э") ;

- спеціальна модифікація мікросхеми 556РТ5 для системи управління оптичного дзеркала вищезгаданого комплексу.

Розробка виконувалась відповідно до спеціальних технічних вимог указаних блоків. В результаті оцінювалась сумарна площа Ss МГ16-3, реалізована на основі виняткового використання КФП, а також площа Ss, одержана при спільному використанні класичної і альтернативних ФП, тобто ОФП.

В результаті вказаних розрахунків було визначено:

- в мікрозборці МГ16-3 з'явилося додаткова площа, яка складає 107,8% в порівнянні з базовою схемою, що дало можливість включити до складу мікрозборки додатково 7 елементів спеціального застосування;

- в модифікованій мікросхемі (умовна назва 556РТ-ОФП) додаткова площа склала 4,9%, що дало можливість організувати додаткові зворотні зв'язки і збільшити точність формування управляючої дії в системі управління

Представлена з дозволу НВК "Фотоприлад" блок-схема системи управління комплексом "Буран-Е" у якому проводилися розрахунки сумарних блоків. Результати розрахунків підтверджені актом від 04 листопада 2001г.

Проведені експериментальні дослідження, підтвердили достовірність теоретичних положень роботи.

Основні результати роботи і висновки

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

1. Запропоновано оцінку технічній доцільності застосування альтернативних форм представлення в проектуванні цифрових пристроїв, як коефіцієнт k схемного ускладнення елементів підсумовування кон'юнкції в альтернативних ФП у порівнянні з елементами OR для КФП. Для n=4 k змінюється від 1 до 68, а із зростанням величини n виявлено зростання верхнього граничного значення k де технічне застосування ОФП можливо важити доцільним. Доведено, що при будь-якому розумному ступені схемного ускладнення елемента альтернативного підсумовування завжди існує число аргументів n, при якому використання ОФП вважається доцільним.

2. На основі дослідження структури повної множини ЛФ виявлено доцільність використання альтернативних ФП, у яких підмножина пріоритетів має досить високу потужність при будь-яких критеріях оцінки якості мінімізації ЛФ. Зокрема, по найбільш важливому критерію Ss ( площа ПЛМ1, потрібна для формування всіх необхідних кон'юнкцій) відносні потужності зазначених підмножин дорівнюють: класична ФП- 1.92%, альтернативна ФП - 98.02%. Тим самим, доведена принципова можливість скорочення площі інтегральних схем для більшості ЛФ за рахунок спільного використання класичної й альтернативних ФП.

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

- розроблено методи переходу ЛФ з однієї форми представлення до будь-якої обраної ФП шляхом перетворення однієї базисної системи в іншу на основі рішення лінійно-алгебраїчної задачі. Запропоновано матричний апарат для переходу від однієї ФП до будь-якої обраної ФП на основі використання класичного (Q-) чи альтернативних (S-, G-) базисів для запису ЛФ;

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

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

- виконано аналіз продуктивності векторів поляризації для АФП, який показав, що нульовий вектор дозволяє одержати тільки 6-10% мінімальних реалізацій ЛФ, тобто врахування властивостей вектора поляризації є істотним чинником додаткової мінімізації ЛФ в альтернативних ФП;

- розроблено методи апріорного визначення найбільш доцільної ФП для заданих ЛФ у проектованих елементах і пристроях обчислювальної техніки. Проблема апріорного визначення ЛФ із до тієї чи іншої підмножини пріоритетів вирішується на основі запропонованого в роботі стохастичного апарата БГА.

4. Розроблено алгоритми реалізовані у інструментальному програмному комплексі "IZOMORF", який призначений для формування множини ЛФ усіх форм представлення з нарощуванням схемної реалізації за заданими критеріями добору; реалізації мінімальних ЛФ усіх ФП, оцінки потужності ФП, формування ОФП; генерації ЛФ композицією батьківських пар і оцінки передачі спадкоємних ознак в оптимізованих реалізаціях різних ФП, а також розв'язку інших задач спрощення структури реалізації цифрових елементів.

5. Розроблено і експериментально досліджено на моделюючому стенді мікрозборка МГ16-3 спеціального застосування (елемент системи управління комплексу "Буран-Е") та проведена модифікація мікросхеми 556РТ5 для системи управління оптичного дзеркала вищезгаданого комплексу, яка є результатом спільної науково-технічної співпраці з НВК "Фотоприлад". Підтверджена достовірність теоретичних положень, викладених у роботі.

Основні роботи, що опубліковані за темою дисертації

1. Кочкарев Ю.А., Казаринова Н.Л., Пантелеева Н.Н. Классические и альтернативные минимальные формы логических функций: Каталог- справочник. Монография / Институт проблем моделирования в энергетике им. Г.Е. Пухова, Черкасский институт управления. - Черкассы, 1999. - 195 с. - ISBN 966-95730-0-9.

2. Кочкарев Ю.А., Казаринова Н.Л., Пантелеева Н.Н. Взаимные преобразования классических и альтернативных представлений комбинационных схем цифровых автоматов. // Збірник наукових праць НАН України; Інститут проблем моделювання в енергетиці ім. Г. Є. Пухова. - Львів: Світ, 1998. - Вт.3 - С. 94-99.

3. Казаринова Н.Л. Алгебраическая форма представления логических функций как вариант минимизации площади программируемых логических матриц // Збірник наукових праць НАН України; Інститут проблем моделювання в енергетиці ім. Г. Є. Пухова. - Черкаси: ІУБ, 1998. - В.6. - С. 114-122.

4. Кочкарев Ю.А., Казаринова Н.Л., Пантелеева Н.Н. Минимизация логических функций как задача линейного программирования // УСиМ. - 1999. - №4. - С. 7-12.

5. Кочкарев Ю.А., Казаринова Н.Л., Пантелеева Н.Н. Альтернативные модели биомолекулярных вычислений на основе изоморфизма логических и кусочно-постоянных функций // Электроника и связь. - 1999. - №6. - Т.1. - С. 217-221.

6. КочкаревЮ.А., Казаринова Н.Л., Пантелеева Н.Н. Минимизация площади ПЛМ на основе оптимизированной формы цифрових автоматов // Электроника и связь. - 2000. - №8, Т.2. - С. 282-286.

7. Кочкарев Ю.А., Казаринова Н.Л. Оптимизационная форма представления логических функций // Збірник наукових праць / НАН України; Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова. - К., 2000. - Вип.5. - С. 23-33.

8. Кочкарев Ю.А., Казаринова Н.Л., Нечипоренко О.В. К вопросу об экономической целесообразности использования альтернативних форм представления логических функций // Электроника и связь. - 2001. - №11. - С. 86-88.

Додатково:

1. Исследование изоморфизма логических и кусочно-постоянных функций: Отчет о НИР / Черкасский институт управления. №41 (1998-2001). - Черкассы, 2001.

2. Кочкарев Ю.А., Казаринова Н.Л., Пантелеева Н.Н. Минимизация логических функций в оптимизационной форме представления / Тезисы докладов конференции Advanced computer systems, Szczecin (Poland), November 19-20, 1998. - 1998. - Р.567-568

Анотація

Казарінова Наталія Леонідівна. Методи і засоби синтезу цифрових елементів та пристроїв на основі ізоморфізму логічних та кусково-постійних функцій - Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.05 - “Елементи та пристрої обчислювальної техніки та систем керування”. - Інститут проблем моделювання в енергетиці НАН України ім. Г. Є. Пухова, Київ, 2001.

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

Досліджено впливи схемного ускладнення елементів підсумовування кон'юнкцій в альтернативних ФП в порівнянні з елементами OR для КФП. Доведено розширення зони доцільності використання ОФП із збільшенням n- числа аргументів ЛФ. Доведено, що при будь-якій розумній мірі схемного ускладнення елемента альтернативного підсумовування завжди існує число аргументів n, при якому використання ОФП вважається доцільним.

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

Основні ідеї роботи підтверджені експериментально у порядку сумісної науково-технічної співпраці з НВК „Фотоприлад” для проведення розробки мікрозборки і мікросхеми спеціального застосування.

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

Summary

Kazarinova N.L. Methods and means of synthesis of digital elements and devices on the basis of isomorphism of logic and partially-constant functions - Manuscript.

The thesis for obtaining candidate of science degree on speciality 05.13.05 -elements and devices of computer engineering and control systems. - The Institute of Modeling Problems in Power Engineering by G.E.Pukhov of the National Academy of Science of Ukraine, Kyiv, 2002.

The dissertation is devoted to develop methods of optimization of digital blocks and their usage in designing combinatorial circuits, in particular, on the basis of combined use of alternative and classic forms of logic functions' presentation. Strict proof of technical expediency of use of alternative bases of computer hardware presentation, in particular, on the basis of programmed logic arrays to design digital automatic devices has been substantiated.

Effects of circuit complication of conjunctions' summation elements in alternative PF as compared to OR elements for CFP have been studied. Expansion of expediency zone of ОFP use with the increase of n-number of LF arguments has been proved. It has been proved that at any reasonable measure of circuit complication of an alternative summation element there always exists n-number of arguments when ОFP use is considered expedient.

Results obtained in the process of work substantiate ways of further optimization of structure of computer hardware elements and devices on the basis of joint use of classic and alternative presentation bases in the form of a single optimized presentation base that allows a considerable reduction in complexity of realization.

Basic ideas of the work are confirmed through experiments in software development and calculations.

Key words: elements and devices computing engineering, planning digital devices, methods and synthesis means, logical functions, forms of performance, circuit realization, programmed logical arrays.

Аннотация

Казаринова Наталия Леонидовна. методы И средства синтеза цифровых элементов и устройств на основе изоморфизма логических и кусочно-постоянных функций - Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.05 - “Элементы и устройства вычислительной техники и систем управления”. - Институт проблем моделирования в энергетике НАН Украины им. Г.Е. Пухова, Киев, 2001.

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

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

Разработан программный аппарат для исследования структуры полного множества ЛФ, с помощью которого получены значительная часть вышеуказанных результатов, причем наиболее важным является оценка мощности и границ подмножеств приоритетов классической и альтернативных форм представления ЛФ, с учетом особенностей схемной реализации ЛФ в альтернативных ФП.

Выполнено исследование структуры полного множества ЛФ, как объединение подмножеств ЛФ, перспективных для классической и альтернативной реализации с целью оптимизации проектирования цифровых узлов и устройств. Разработан аппарат исследования структуры полного множества логических функций, проведена точная оценка мощности и границ подмножеств приоритетов классической и альтернативных форм представления ЛФ, в том числе с учетом особенностей схемной реализации ЛФ в альтернативных формах. Введены критерии оценки эффективности различных ФП и определены области эффективного использования альтернативных форм представления в проектировании элементов и устройств вычислительной техники

Рассмотрены базисные системы, как основа проектирования цифровых узлов и устройств, для выбора оптимальной записи ЛФ во всех рассматриваемых форм представления.

В работе исследованы существующие и предложены новые методы минимизации ЛФ: задача линейного программирования, где минимальное решение можно найти используя целевую функцию для АФП и систему ограничений; минимизации с учетом вектора поляризации; минимизации ЛФ на основе свойств приведенных коэффициентов; минимизация Шеннона позволяет провести расчет порожденных ЛФ и получить опорное решение. Все рассматриваемые метода программно реализованы в комплексе "REALIZ_M_F".

Разработаны методы априорного определения наиболее целесообразной ФП ЛФ в элементах и устройствах вычислительной техники. Проблема априорного определения принадлежности ЛФ из к тому или иному подмножеству приоритетов решается в стохастическом смысле на основе предложенного аппарата БГА используя таблицу умножения для векторов . В дальнейшем предложено исследовать надежности передачи по наследству признака принадлежности к i -ому подмножеству ФП.

Впервые введена оптимизированная форма представления ЛФ в качестве основы минимизации площади ПЛМ, как наиболее распространенного способа реализации сложных элементов и устройств вычислительной техники.

Разработан программный комплекс исследования структуры полного множества ЛФ, проведена оценка мощности и границ подмножеств приоритетов классической и альтернативных форм представления ЛФ, с учетом схемной реализации ЛФ в альтернативных ФП. и результаты исследования внедрены в учебный процесс в Черкасском институте управления. Основные идеи работы подтверждены экспериментально программными разработками и проведенными расчетами.

Полученные в работе результаты обосновывают пути дальнейшей оптимизации структуры элементов и устройств вычислительной техники на основе совместного использования классической и альтернативных форм представления в виде единой оптимизированной формы представления, что позволяет добиваться существенного сокращения сложности реализации. Экспериментальное подтверждение проведенных исследований выполнено в порядке совместного научно-технического сотрудничества с НПК "Фотоприлад" при разработке микросборки МГ16-3 специального применения (элемент системы управления комплекса "Буран-Э") и изменении микросхемы 556РТ5 для системы управления оптического зеркала вышеназванного комплекса. Стендовые испытания подтвердили достоверность теоретических положений, изложенных в работе.

Ключевые слова: элементы и устройства вычислительной техники, проектирование цифровых устройств, методы и средства синтеза, логические функции, формы представления, схемная реализация, программируемые логические матрицы.

Размещено на Allbest.ru

...