Розробка мінімізації поліномної нормальної форми булевих функцій методом образних перетворень

Автор(и)

  • Михайло Тимофійович Соломко Національний університет водного господарства та природокористування , Україна https://orcid.org/0000-0003-0168-5657
  • Юлія Валеріївна Батишкіна Рівненський державний гуманітарний університет, Україна https://orcid.org/0000-0002-5390-9029
  • Наталія Леонідівна Хомюк Волинський національний університет імені Лесі Українки, Україна https://orcid.org/0000-0002-3277-8840
  • Яків Григорович Іващук Національний університет водного господарства та природокористування , Україна https://orcid.org/0000-0003-4899-9303
  • Наталія Вікторівна Шевцова Рівненський державний гуманітарний університет, Україна https://orcid.org/0000-0002-3401-5468

DOI:

https://doi.org/10.15587/1729-4061.2021.229786

Ключові слова:

мінімізація булевих функцій у базисі Ріда–Маллера, метод образних перетворень, сингулярна функція

Анотація

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

Поширення методу образних перетворень на процес спрощення функцій поліномного базису здійснено за допомогою розробленої алгебри у частині правил спрощення функцій у базисі Ріда–Маллера. Встановлено, що спрощення булевих функцій поліномного базису методом образних перетворень ґрунтується на блок-схемі з повторенням, якою є власне таблиця істинності заданої функції. Це є достатнім ресурсом для мінімізації функцій та дозволяє обходитись без допоміжних об’єктів, як то карти Карно, діаграми Вейча, куби та ін.

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

Експериментальними дослідженнями підтверджено, що метод образних перетворень, який використовує системи 2-(n, b)-design та 2-(n, x/b)-design у першій матриці, підвищує ефективність мінімізації булевих функцій. При цьому спрощується процедура пошуку мінімальної функції у базисі Ріда–Маллера. У порівнянні з аналогами це дає змогу підвищити продуктивність мінімізації булевих функцій на 100–200 %.

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

Біографії авторів

Михайло Тимофійович Соломко, Національний університет водного господарства та природокористування

Кандидат технічних наук, доцент

Кафедра обчислювальної техніки

Юлія Валеріївна Батишкіна, Рівненський державний гуманітарний університет

Кандидатка технічних наук, доцентка

Кафедра інформаційно-комунікаційних технологій та методики викладання інформатики

Наталія Леонідівна Хомюк, Волинський національний університет імені Лесі Українки

Кандидатка економічних наук

Кафедра міжнародних економічних відносин та управління проектами

Яків Григорович Іващук, Національний університет водного господарства та природокористування

Кандидат фізико-математичних наук

Кафедра вищої математики

Наталія Вікторівна Шевцова, Рівненський державний гуманітарний університет

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

Кафедра інформатики та прикладної математики

Посилання

  1. Rytsar, B. Ye. (2013). A Numeric Set-Theoretical Interpretation of Polynomial Zhegalkin. Upravlinnia systemamy i mashynamy, 1, 11–26. Available at: http://dspace.nbuv.gov.ua/handle/123456789/83125
  2. Sasao, T. (1999). Switching Theory for Logic Synthesis. Springer US, 362. doi: https://doi.org/10.1007/978-1-4615-5139-3
  3. Sasao, T. (1996). Representations of Logic Functions Using EXOR Operators. Representations of Discrete Functions, 29–54. doi: https://doi.org/10.1007/978-1-4613-1385-4_2
  4. Sasao, T. (1997). Easily testable realizations for generalized Reed-Muller expressions. IEEE Transactions on Computers, 46 (6), 709–716. doi: https://doi.org/10.1109/12.600830
  5. Zakrevskiy, A. D., Toporov, N. R. (2003). Polinomial'naya realizatsiya chastichnyh bulevyh funktsiy i sistem. Moscow: Editorial URSS, 200. Available at: https://www.libex.ru/detail/book14536.html
  6. Zakrevskiy, A. D., Pottosin, Yu. V., Cheremisinova, L. D. (2007). Logicheskie osnovy proektirovaniya diskretnyh ustroystv. Moscow: Fizmatlit, 592. Available at: https://www.libex.ru/detail/book852648.html
  7. Fujiwara, H. (1985). Logic testing and design for testability. Cambridge. doi: https://doi.org/10.7551/mitpress/4317.001.0001
  8. Faraj, K. (2011). Design Error Detection and Correction System based on Reed-Muller Matrix for Memory Protection. International Journal of Computer Applications, 34 (8), 42–48. Available at: https://research.ijcaonline.org/volume34/number8/pxc3875929.pdf
  9. Solomko, M. (2021). Developing an algorithm to minimize boolean functions for the visual-matrix form of the analytical method. Eastern-European Journal of Enterprise Technologies, 1 (4 (109)), 6–21. doi: https://doi.org/10.15587/1729-4061.2021.225325
  10. Rytsar, B. (2015). The Minimization Method of Boolean Functionns in Polynomial Set-theoretical Format. Conference: Proc. 24th Inter. Workshop, CS@P’2015. Rzeszow, 130–146. Available at: https://www.researchgate.net/publication/298158364_The_Minimization_Method_of_Boolean_Functionns_in_Polynomial_Set-theoretical_Format
  11. Sampson, M., Kalathas, M., Voudouris, D., Papakonstantinou, G. (2012). Exact ESOP expressions for incompletely specified functions. Integration, 45 (2), 197–204. doi: https://doi.org/10.1016/j.vlsi.2011.10.001
  12. Knysh, D., Dubrova, E. (2011). Rule-based optimization of AND-XOR expressions. Facta Universitatis - Series: Electronics and Energetics, 24 (3), 437–449. doi: https://doi.org/10.2298/fuee1103437k
  13. Bibilo, P. N., Lankevich, Y. Y. (2017). The Use of Zhegalkin Polynomials for Minimization of Multilevel Representations of Boolean Functions Based on Shannon Expansion. Programmnaya Ingeneria, 8 (8), 369–384. doi: https://doi.org/10.17587/prin.8.369-384
  14. Egorova, E. K., Cheburakhin, I. F. (2013). On the minimization of complexity and automation of efficient representation of boolean functions in classes of formulas and circuits. Journal of Computer and Systems Sciences International, 52 (4), 618–627. doi: https://doi.org/10.1134/s1064230713030064
  15. Frantseva, A. S. (2018). An Algorithm for Minimization of Boolean Functions in the Class of Toffoli Reversible Logic Circuits. The Bulletin of Irkutsk State University. Series Mathematics, 25, 144–158. doi: https://doi.org/10.26516/1997-7670.2018.25.144
  16. He, Z., Xiao, L., Huo, Z., Wang, T., Wang, X. (2019). Fast Minimization of Fixed Polarity Reed-Muller Expressions. IEEE Access, 7, 24843–24851. doi: https://doi.org/10.1109/access.2019.2899035
  17. Samofalov, K. G., Romlinkevich, A. M., Valuyskiy, V. N., Kanevskiy, Yu. S., Pinevich, M. M. (1987). Prikladnaya teoriya tsifrovyh avtomatov. Kyiv: Vischa shk. Golovnoe izd-vo, 375. Available at: http://stu.scask.ru/book_pta.php?id=62
  18. Rytsar, B. Ye. (2015). New minimization method of logical functions in polynomial set-theoretical format. 1. Generalized rules of conjuncterms simplification. Upravlyayuschie sistemy i mashiny, 2, 39–57. Available at: http://dspace.nbuv.gov.ua/handle/123456789/87194
  19. Riznyk, V., Solomko, M. (2017). Application of super-sticking algebraic operation of variables for Boolean functions minimization by combinatorial method. Technology Audit and Production Reserves, 6 (2 (38)), 60–76. doi: https://doi.org/10.15587/2312-8372.2017.118336
  20. Akinina, Ju. S., Podvalniy, S. L., Tyurin, S. V. (2016). The application of karnaugh maps for the polinomial transformation of boolean functions. Vestnik Voronezhskogo gosudarstvennogo tehnicheskogo universiteta, 12 (1), 4–7. Available at: https://cyberleninka.ru/article/n/primenenie-kart-karno-dlya-polinomialnogo-preobrazovaniya-bulevyh-funktsiy
  21. Rytsar, B. Ye. (2013). A Numeric Set-Theoretical Interpretation of Reed-Muller Expressions with Fixed and Mixed Polarity. Upravlyayuschie sistemy i mashiny, 3, 30–44. Available at: http://dspace.nbuv.gov.ua/handle/123456789/83164
  22. Tran, A. (1987). Graphical method for the conversion of minterms to Reed-Muller coefficients and the minimisation of exclusive-OR switching functions. IEE Proceedings E Computers and Digital Techniques, 134 (2), 93. doi: https://doi.org/10.1049/ip-e.1987.0016
  23. Rytsar, B. Ye. (2015). A New Method of Minimization of Logical Functions in the Polynomial Set-theoretical Format. 2. Minimization of Complete and Incomplete Functions. Upravlyayuschie sistemy i mashiny, 4, 9–20. Available at: http://dspace.nbuv.gov.ua/handle/123456789/87235
  24. Riznyk, V., Solomko, M. (2018). Research of 5-bit boolean functions minimization protocols by combinatorial method. Technology Audit and Production Reserves, 4 (2 (42)), 41–52. doi: https://doi.org/10.15587/2312-8372.2018.140351
  25. Riznyk, V., Solomko, M., Tadeyev, P., Nazaruk, V., Zubyk, L., Voloshyn, V. (2020). The algorithm for minimizing Boolean functions using a method of the optimal combination of the sequence of figurative transformations. Eastern-European Journal of Enterprise Technologies, 3 (4 (105)), 43–60. doi: https://doi.org/10.15587/1729-4061.2020.206308
  26. Solomko, M., Khomiuk, N., Ivashchuk, Y., Nazaruk, V., Reinska, V., Zubyk, L., Popova, A. (2020). Implementation of the method of image transformations for minimizing the Sheffer functions. Eastern-European Journal of Enterprise Technologies, 5 (4 (107)), 19–34. doi: https://doi.org/10.15587/1729-4061.2020.214899
  27. Mishchenko, A., Perkowski, M. (2001). Fast Heuristic Minimization of Exclusive-Sums-of-Products. Proc. Reed-Muller Inter. Workshop’01, 242–250. Available at: https://www.researchgate.net/publication/2367778_Fast_Heuristic_Minimization_of_Exclusive-Sums-of-Products

##submission.downloads##

Опубліковано

2021-04-30

Як цитувати

Соломко, М. Т., Батишкіна, Ю. В., Хомюк, Н. Л., Іващук, Я. Г., & Шевцова, Н. В. (2021). Розробка мінімізації поліномної нормальної форми булевих функцій методом образних перетворень. Eastern-European Journal of Enterprise Technologies, 2(4 (110), 22–37. https://doi.org/10.15587/1729-4061.2021.229786

Номер

Том 2 № 4 (110) (2021): Математика та кібернетика - прикладні аспекти

Розділ

Математика та кібернетика - прикладні аспекти

Ліцензія

Авторське право (c) 2021 Mykhailo Solomko, Iuliia Batyshkina, Nataliia Khomiuk, Yakiv Ivashchuk, Natalia Shevtsova

Creative Commons License

Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.

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

Ліцензійний договір – це документ, в якому автор гарантує, що володіє усіма авторськими правами на твір (рукопис, статтю, тощо).
Автори, підписуючи Ліцензійний договір з ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР», мають усі права на подальше використання свого твору за умови посилання на наше видання, в якому твір опублікований. Відповідно до умов Ліцензійного договору, Видавець ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР» не забирає ваші авторські права та отримує від авторів дозвіл на використання та розповсюдження публікації через світові наукові ресурси (власні електронні ресурси, наукометричні бази даних, репозитарії, бібліотеки тощо).
За відсутності підписаного Ліцензійного договору або за відсутністю вказаних в цьому договорі ідентифікаторів, що дають змогу ідентифікувати особу автора, редакція не має права працювати з рукописом.
Важливо пам’ятати, що існує і інший тип угоди між авторами та видавцями – коли авторські права передаються від авторів до видавця. В такому разі автори втрачають права власності на свій твір та не можуть його використовувати в будь-який спосіб.