Логіковий синтез цифрових пристроїв на основі мінімізації булових функцій у поліномному форматі
Автор: Матвіїв Роман Мартинович
Кваліфікаційний рівень: магістр (ОНП)
Спеціальність: Телекомунікації та радіотехніка (освітньо-наукова програма)
Інститут: Інститут телекомунікацій, радіоелектроніки та електронної техніки
Форма навчання: денна
Навчальний рік: 2020-2021 н.р.
Мова захисту: українська
Анотація: Матвіїв Р.М., Рицар Б.Є. (керівник). Логіковий синтез цифрових пристроїв на основі мінімізації булових функцій у поліномному форматі. Магістерська кваліфікаційна робота. - Національний університет “Львівська політехніка”, Львів, 2021. Розширена анотація Проблема мінімізації логікових функцій, яка лежить в основі логікового синтезу цифрових пристроїв, вже давно актуальна, оскільки ефективно виконана процедура мінімізації функції або системи функцій значно зменшує необхідну кількість логікових елементів та з’єднань між ними, що дає змогу значно зменшити витрати на виробництво синтезованого цифрового пристрою або окремих мікросхем, включених у його склад. Ця робота присвячена мінімізації логікових функцій у поліномному форматі, що також відомий як ESOP-форма (Exclusive Sum of Product), і методу «рукостискання». Більшість методів в науково-технічній літературі [1-4] на цю тему, працюють з диз’юнктивним форматом (SOP-форма), незважаючи на те що ESOP забезпечує потенційно кращі результати мінімізації та є більш ефективною для реалізації з економічної точки зору [5-6]. Однак мінімізація форми ESOP набагато складніша, тому за останні кілька десятиліть, лише евристичні методи стали відносно широко поширеними. Крім того, всі методи мінімізації у формі ESOP можна віднести до декількох загальних недоліків: вони працюють лише за умови ідентичного рангу термів (терм - це математичний об’єкт логікової функції, над яким виконуються логікові операції), вони не використовуються при гемінґовій відстані більше двох, їх можна використовувати лише для конкретних типів логікових функцій та з обмеженням щодо кількості змінних [7-8]. Тому в цій роботі розглянуто відносно новий метод мінімізації без вищезгаданих недоліків. Цей метод заснований на трьох описаних теоремах і правилах розкладання (узагальнення теорем для довільних термінів) [9-12]. Щоб мінімізувати логікові функції, метод використовує процедуру "рукостискання" (звідси й назва методу), що є взаємним рухом двох термів один до одного для того, щоб зменшити гемінґову відстань між ними. Внаслідок цього утворюється менший, ніж набір із двох початкових термів функції, трансформований терм функції у форматі ESOP. Трансформовані терми можуть бути використані для спрощення логікової функції далі. Різні приклади надано для доведення ефективності методу та його здатності до мінімізації функцій, які не можуть бути мінімізовані у формі SOP. Для реалізації методу мінімізації логікових функцій у поліномному форматі на основі процедури "рукостискання", було використано мову програмування Python 3 для створення програми. Програма працює циклічно, під час однієї ітерації обчислюється початкова величина кошту реалізації, шукається пара термів з зазначеною гемінґовою відстанню, застосовується процедура "рукостискання" для пари і порівнюється кошт реалізації до процедури та після її проведення. Якщо є поліпшення, результат зберігається та подається як вхідні дані для наступної ітерації. Мінімізація вважається завершеною, коли у процесі "рукостискання" не існує поліпшення після перебору всіх можливих комбінацій. Для того, щоб переконатись у ефективності програми, було проведено ряд мінімізацій певних функцій. Програма успішно мінімізує функції, що використовуються у різних джерелах для ілюстрації переваг різних алгоритмів мінімізації. Результати показують, що засоби реалізації мінімізованих функцій не гірше, і часто навіть краще, ніж у вищезгаданих джерелах. Крім того, програма здатна мінімізувати "ланцюгові" функції, які можуть мати лише два рішення у SOP-формі, кожен з яких містить термін одного меншого рангу, ніж у початкових термів. Однак у формі ESOP програма вдалося звести до мінімуму таку "ланцюгову" функціою ще більше, було відзначено, що збільшення кількості термів у вхідній функції (тобто збільшення "ланцюга"), призводить до покращення результату. Програма виявилася здатною мінімізувати тестові функції, так звані бенчмарки (benchmarks). Логікові функції-бенчмарки - це функції з великою кількістю змінних, що використовуються для перевірки завершених алгоритмів мінімізації. Також були мінімізовані й інші функції та навіть системи функцій. Результати випробувань підтверджують гіпотезу, що концепція фіксованої відстані між двома термами, для якого розкладання стає неможливим після досягнення цієї відстані, є непрактичним, через що цю функцію не можна ефективно мінімізувати. Навпаки, кошт реалізації зазвичай покращується з зростанням глибини рукостискання (максимальна гемінґова відстань між двома термами), І наявність чи положення оптимального піку є індивідуальним для кожної функції. Програма має недоліки, головними з яких є: низька продуктивність для великих функцій і геометричне зростання часу розрахунку при збільшенні кількості змінних; нездатність мінімізувати неповні функції; відсутність інформації про статус виконання процедури під час роботи програми. Загалом, експериментальні результати показали, що алгоритм мінімізації, заснований на процедурі «рукостискання», підходить для мінімізації логікових функцій. Якщо змінити та вдосконалити програму та метод, отримаємо універсальний точний інструмент мінімізації функцій в поліномному форматі, що дозволить більш ефективно синтезувати будь-який пристрій у галузі цифрових обчислень. Ключові слова: логікова функція, мінімізація, терм, поліномний формат, процедура «рукостискання». Перелік використаних літературних джерел: 1. Shannon C.E. Symbolic analysis of relax and switching circuits // Trans. AIEE – 1938 – V.57 – P. 713-723 2. Quine W.V. The Problem of Simplifyinq Truth Functions // Amer. Math. Monthly. – 1952. – 59. – P. 521-531 3. Karnaugh M. The map method for synthesis of combinational logic circuits // Trans. AIEE, 1953. – Vol.72, №1. – P. 593-599 4. McCluskey E.J. Minimization of Boolean Functions // Bell System Technical Journal. – 1956. – 35. – P. 1417-1444 5. Besslish P.W. Efficient computer method for EXOR logic design // IEE Proc. Pt. E, vol. 130, 1983, pp. 203-206 6. Sasao T. Switching Theory for Logic Synthesis. Kluwer Academic Publ. – 1999. – 361 p. 7. Knysh D., Dubrova E. Rule-Based Optimization of AND-XOR Expressions // Facta Universitatis (Nis), Ser.: Elec. Energ., vol. 24, no. 3, December 2011, pp. 437-449. 8. Stergiou S., Daskalakis K., Papakonstantinou G. A Fast and Efficient Heuristic ESOP Minimization Algorithm // GLSVLSI’04. – Boston, Massachusetts, USA. – April 26-28 2004. 9. Rytsar B.Ye. New minimization method of logical functions in polynomial set-theoretical format. 1. Generalized rules of conjuncterms simplification // Control Systems and Computers – 2015 — № 2. — P. 39–57. 10. Rytsar B.Ye. A New Method of Minimization of Logical Functions in the Polynomial Set-theoretical Format. 2. Minimization of Complete and Incomplete Functions. // Control Systems and Computers – 2015 — № 4. — P. 9–20, 30. 11. Rytsar Ye.B. A New Method of the Logical Functions Minimization in the Polynomial Set-Theoretical Format. 3. Minimization of Function System. // Control Systems and Computers — 2015. — № 5 — С. 9–21. 12. Rytsar B.Ye., Belovolov А.O. A New Method of the Logical Functions Minimization in the Polynomial Set-Theoretical Format. «Handshaking» Procedure. // Control Systems and Computers — 2021. — № 1. — С. 3-14.