Проектування цифрових пристроїв на комбінаційних схемах середнього рівня інтеграції (на прикладі MUX)
Автор: Лоїк Віталій Анатолійович
Кваліфікаційний рівень: магістр (ОНП)
Спеціальність: Телекомунікації та радіотехніка (освітньо-наукова програма)
Інститут: Інститут телекомунікацій, радіоелектроніки та електронної техніки
Форма навчання: денна
Навчальний рік: 2020-2021 н.р.
Мова захисту: українська
Анотація: Лоїк В.А., Рицар Б.Є. (керівник). «Проектування цифрових пристроїв на комбінаційних схемах середнього рівня інтеграції (на прикладі MUX)». Магістерська робота. - Національний університет "Львівська політехніка", Львів, 2021. Розширена анотація У даній магістерській роботі подано метод декомпозиції булових функцій у теоретико-множинному форматі для подальшої реалізації їх на мультиплексорах, складено алгоритм виконання декомпозиції та розроблено комп’ютерну програму на основі цього алгоритму, в загальному, у цій роботі: • Проаналізовано відомі на цей час методи декомпозиції булових функцій. • Розроблено новий метод q-розбиття кон’юнктермів для декомпозиції повних функцій у числовому форматі. • Підтверджено працездатність цього методу експериментальним шляхом. • Підраховано відносний кошт реалізації комбінаційних схем, отриманих за допомогою цього методу. • Розроблено методику застосування цього методу для декомпозиції системи повних функцій. • Перевірено працездатність цього методу декомпонування систем повних функцій. • Адаптовано метод q-розбиття кон’юнктермів для декомпозиції неповних булових функцій. • Перевірено працездатність цього методу для виконання декомпозиції неповних функцій експериментальним шляхом. • Розроблено алгоритм виконання декомпозиції методом q-розбиття кон’юнктермів для повних та неповних функцій. • Розроблено комп’ютерну програму на основі цього алгоритму для декомпозиції булових функцій. • Проведено розрахунок економічної доцільності застосування розробленої програми. В першому розділі розглянуто особливості проектування комбінаційних мереж на базі цифрових пристроїв середнього рівня інтеграції (у даній роботі в якості таких пристроїв розглядаються мультиплексори). Проаналізовано відомі на сьогодні методи для виконання декомпозиції булових функцій, їх переваги та недоліки. На прикладі показано виконання декомпозиції булової функції методом розкладу Шеннона на s змінних. В другому розділі запропоновано новий підхід до декомпозиції булових функцій у теоретико-множинному форматі подання. На прикладі показано декомпозицію повної булової функції методом q-розбиття кон’юнктермів, проведено синтез комбінаційної мережі у базисі мультиплексорів для оптимального результату функційної декомпозиції, отриманої у даному прикладі та перевірено працездатність даної схеми у програмі симуляторі цифрових схем. На прикладі порівняно декомпозицію булової функції новим методом та аналітичним методом розбиття Шеннона на s змінних для подальшої реалізації її на мультиплексорі, на основі цього прикладу зроблено висновки щодо переваг методу декомпозиції булових функції методом q-розбиття кон’юнктермів. Виконано приклад декомпозиції систем повних булових функцій цим методом, показано реалізацію отриманих результатів декомпозиції на мультиплексорах та простих логікових елементах, також, для кожного прикладу було складено принципову електричну схему на основі оптимального результату декомпозиції та перевірено правильність її роботи шляхом симуляції її роботи за допомогою програмного забезпечення Multimedia Logic. В третьому розділі описано основні поняття, які стосуються неповних булових функцій. Описано покроковий алгоритм виконання декомпозиції неповних булових функцій методом q-розбиття кон’юнктермів. Показано застосування методу q-розбиття кон’юнктермів для декомпозиції неповних булових функцій у теоретико-множинному форматі подання на практиці. Виконано приклад декомпозиції неповної булової функцій цим методом та спроектовано принципову електричну схему на основі оптимального варіанту результату декомпозиції. В четвертому розділі подано особливості написання програми для автоматизованого виконання декомпозиції повних та неповних булових функцій методом q-розбиття кон’юнктермів, а саме: вибір мови програмування, допоміжних бібліотек та фреймворків. Подано основні переваги та обґрунтування вибору основних інструментів для написання програми декомпозиції повних та неповних булових функцій на основі методу q-розбиття кон’юнктермів. Описано основні моменти роботи даної програми, алгоритм, на основі якого вона написана, функціонування основних вузлів та функцій, які відповідають за, безпосередньо, декомпозицію булових функцій та роботу програми загалом. Продемонстровано графічний інтерфейс, правила користування цією програмою, структури та вигляд вхідних даних, які отримуються від користувача та вихідних даних, як от результат функційної декомпозиції, повідомлення про помилки у використанні програми чи при виконанні необхідних автоматизованих обчислень самою програмою для декомпозиції повних та неповних булових функцій. У п’ятому розділі виконано обчислення для встановлення собівартості НДР, планового прибутку від результатів виконаної магістерської кваліфікаційної роботи та було проведено оцінку наукової та науково-технічної результативності даної науково-дослідної роботи. Для кожного розділу та магістерської кваліфікаційної роботи загалом були зроблені необхідні висновки. Ключові слова: цифрові пристрої, булова функція, функція, розбиття, декомпозиція, мультиплексор, мінімізація, логікові елементи, q-розбиття, кон’юнктерм, мінтерм, літерал, композиція, кошт реалізації, комбінаційна схема, середній рівень інтеграції, програма, електрична схема, симуляція, метод Шеннона, евристичні методи, аналітичні методи, теоретико-множинна форма, аналітичний вираз, аналітична функція, повна функція, неповна функція, система функцій. Список літератури 1. Поттосин Ю.В. Эвристический метод алгебраической декомпозиции частичных булевых функций. Информатика. 2020;17(3):44-53. https://doi.org/10.37661/1816-0301-2020-17-3-44-53 2. Шалыто А.А. Мультиплексорный метод реализации булевых функций схемами из произвольных логических элементов. "Известия РАН. Теория и системы управления". 2003. №1. с. 105–109. 3. Shannon, Claude E., The Synthesis of Two-Terminal Switching Circuits, Bell System Technical Journal 1949; 28: 59–98p. 4. Рицар Б.Є. Декомпозиція бульових функцій методом q?розбиття. 1 // УСиМ. – 1999. – №6. – С. 29-42; 2 // УСиМ. – 2000. – №1. – С. 56-65. 5. Кметь А.Б., Рицар Б.Є. До класифікації декомпозицій логікових функцій // УСиМ. – 2003. – №6. – С. 34-56. 6. Mishchenko A., SteinbachB., Perkowsk i M . An algorithm for bi-decomposition of logic functions / Proc. of DAC 2001, June 18–22, Las Vegas. — ?. 103–108. 7. Scholl C . Functional decomposition with application to FPGA synthesis. — Boston; Dordrecht; London: Kluwer Academic Publishers, 2001. — 263 p. 8. Sasao T . A new expansion of symmetric functions and their application to non-disjoint functional decompositions for LUT type FPGAs / Proc. of International Workshop on Logic Synthesis, June 2001, Lake Tahoe, California, May, 2000. — P. 105–110. 9. Sasao T., Butler J. T. On bi-decompositions of logic functions / Proc. ACM/IEEE Internation Workshop on Logic Synthesis, Takoe City, California, May, 1997. — P. 264–300.