Розроблення та аналіз програмного забезпечення для реалізації методу мінімізації булових функцій на мові С/С++
Автор: Лалак Адріян Михайлович
Кваліфікаційний рівень: магістр (ОНП)
Спеціальність: Телекомунікації та радіотехніка (освітньо-наукова програма)
Інститут: Інститут інформаційно-комунікаційних технологій та електронної інженерії
Форма навчання: денна
Навчальний рік: 2024-2025 н.р.
Мова захисту: англійська
Анотація: Мінімізація булових функцій є важливою науково-технічною задачею, яка має практичне застосування при проєктуванні цифрових систем, оптимізації логічних схем та зменшенні апаратних затрат [1]. Серед існуючих методів мінімізації значну увагу привертають алгоритми, здатні ефективно працювати з функціями великої розмірності [2, 3]. У цій роботі досліджено та вдосконалено метод побітового розбиття зі склеюванням множини кон’юнктермів, а також розроблено його програмну реалізацію на мові C/C++. У першому розділі проведено комплексний аналіз існуючих методів мінімізації булових функцій, включно з класичними підходи Квайна-МакКласкі та сучасними алгоритмами, такими як Еспрессо. Розглянуто їх переваги, недоліки та обмеження при роботі з функціями великої розмірності [4]. Проаналізовано теоретичні основи методу побітового розбиття, який відрізняється від традиційних підходів можливістю ефективного пошуку простих імплікант без попарного порівняння всіх кон’юнктермів [5]. У другому розділі досліджено структуру методу побітового розбиття та його обчислювальну складність. Знайдено, що асимптотична складність алгоритму для практичних задач мінімізації булових функцій може бути оцінена як O(N log N), що значно краще, ніж експоненційна складність класичних методів [6]. Запропоновано вдосконалення методу, яке полягає у заміні способу зберігання та обробки кон’юнктермів із використанням структур даних та адресної арифметики. Такий підхід дає змогу зменшити обсяг даних, що переміщуються при операціях розбиття та сортування, уникнути дублювання даних та ефективно розподіляти пам’ять. Третій розділ присвячено вдосконаленню методу побітового розбиття та його програмній реалізації на мові C/C++. Розроблено програму генерації множини мінтермів булової функції для створення тестових наборів даних з різними характеристиками для ефективного тестування алгоритмів мінімізації. Детально описано структури даних для подання кон’юнктермів, алгоритми розбиття вектора кон’юнктермів за старшим бітом, пошуку склеювань та формування множини простих кон’юнктермів. Значну увагу зосереджено на оптимізації методу з використанням адресної арифметики, яка забезпечує підвищення ефективності при роботі з функціями великої розмірності. У четвертому розділі проведено тестування та аналіз результатів роботи розроблених програмних реалізацій. Створено тестові набори даних для булових функцій різної складності та виконано порівняльний аналіз базової та вдосконаленої версій алгоритму. Результати тестування підтвердили коректність роботи програм та переваги модифікованого методу, який демонструє значне прискорення для функцій з великою кількістю змінних. В економічному розділі виконано розрахунок витрат на розробку програмного забезпечення та оцінку його економічної ефективності, що підтверджує доцільність впровадження розробленого методу. Теоретичні оцінки та експериментальні результати показують, що для функцій з великою кількістю змінних (>20) вдосконалений алгоритм забезпечує значне підвищення ефективності порівняно з базовою версією. Розроблене програмне забезпечення може бути використане для мінімізації булових функцій у процесі проєктування цифрових схем, оптимізації логічних виразів при розробці компіляторів та в інших галузях, де виникає потреба у мінімізації булових функцій. Об’єкт дослідження: методи мінімізації булових функцій та їхня програмна реалізація. Предмет дослідження: метод побітового розбиття зі склеюванням множини кон’юнктермів та його програмна реалізація на мові С/С++. Мета роботи: розробка та аналіз програмного забезпечення для реалізації методу мінімізації булових функцій побітовим розбиттям, а також його вдосконалення для підвищення ефективності при роботі з функціями великої розмірності. Сфера досліджень: дискретна математика, булова алгебра, проєктування цифрових пристроїв, алгоритми оптимізації. Ключові слова: булові функції, мінімізація, метод побітового розбиття, кон’юнктерми, адресна арифметика, програмна реалізація, C/C++ Перелік джерел посилання 1. Рицар Б. Є. Мінімізація системи логікових функцій методом паралельного розчеплення кон’юнктермів. Вісник Національного університету "Львівська політехніка". Радіоелектроніка та телекомунікації. 2013. № 766. С. 18-27. 2. Brayton R. K., Sangiovanni-Vincentelli A. L. Algorithms for multiple-level combinational logic optimization. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. 1990. Vol. 9, No. 6. P. 897-908. 3. Vu H.-G., Bui N.-D., Nguyen A.-T., Le T. Performance Evaluation of Quine- McCluskey Method on Multi-core CPU. 8th NAFOSTED Conference on Information and Computer Science. 2021. P. 60-64. 4. Мінзюк В. "Метод мінімізації булевих функцій для проєктування цифрових комбінаційних схем", Інфокомунікаційні технології та електронна інженерія. – Львів, 2023. – Вип. 3, № 1. – С. 146-152. 5. Рудель Р. Метод ESPRESSO для мінімізації булових функцій. Комп’ютерні системи та мережеві технології. 2018. № 5. С. 83-92. 6. Borodzhieva A., Stoev I., Mutkov V. FPGA Implementation of Boolean Functions Using Decoders and Logic Gates. IEEE 25th International Symposium for Design and Technology in Electronic Packaging. 2019. P. 164- 167.