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

Автор(и)

  • Михайло Тимофійович Соломко Національний університет водного господарства та природокористування, Україна https://orcid.org/0000-0003-0168-5657
  • Микола Степанович Антонюк Рівненський державний гуманітарний університет, Україна https://orcid.org/0000-0002-6888-6392
  • Ігор Станіславович Войтович Рівненський державний гуманітарний університет, Україна https://orcid.org/0000-0003-2813-5225
  • Юлія Вікторівна Ульяновська Університет митної справи та фінансів, Україна https://orcid.org/0000-0001-5945-5251
  • Наталія Степанівна Павлова Рівненський державний гуманітарний університет, Україна https://orcid.org/0000-0002-7817-6781
  • В’ячеслав В’ячеславович Білецький Рівненський державний гуманітарний університет, Україна https://orcid.org/0000-0003-2734-7306

DOI:

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

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

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

Анотація

Проведеними дослідженнями встановлена можливість збільшення ефективності методу образних перетворень для мінімізації частково визначених булевих функцій. Метод дає змогу без втрати функціональності зменшити складність процедури мінімізації, порівняно з перебором бінарних довизначень частково визначених булевих функцій. Інтерпретація результату полягає у тому, що системи 2-(n, b)-design, 2-(n, x/b)-design є відображенням логічних операцій. Тому виявлення таких комбінаторних систем у таблиці істинності логічних функцій безпосередньо і однозначно встановлює локацію логічних операцій для рівносильних перетворень булевих виразів. Це, у свою чергу, імплікує алгоритм спрощення булевих функцій, у тому числі й частково визначених булевих функцій. Таким чином метод образних перетворень спрощує та пришвидшує процедуру мінімізації частково визначених булевих функцій, порівняно з аналогами. Це вказує та те, що візуально-матрична форма аналітичного методу, все ще має перспективу нарощувати свої апаратні можливості, зокрема й стосовно мінімізації частково визначених булевих функцій.

Експериментально підтверджено, що метод образних перетворень підвищує ефективність мінімізації частково визначених булевих функцій, порівняно з аналогами на 100–200 %.

Є підстави стверджувати про можливість збільшення ефективності мінімізації частково визначених булевих функцій в основному та поліномному базисах зазначеним методом. Ефективність методу, зокрема, забезпечується проведенням всіх операцій узагальненого склеювання змінних для тупикових диз’юнктивних нормальних форм (ДНФ) з наступним застосуванням імплікантних таблиць; оптимальним комбінуванням послідовності логічних операцій склеювання змінних

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

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

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

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

Микола Степанович Антонюк, Рівненський державний гуманітарний університет

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

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

Ігор Станіславович Войтович, Рівненський державний гуманітарний університет

Доктор педагогічних наук, професор

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

Юлія Вікторівна Ульяновська, Університет митної справи та фінансів

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

Кафедра комп’ютерних наук та інженерії програмного забезпечення

Наталія Степанівна Павлова, Рівненський державний гуманітарний університет

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

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

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

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

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

Посилання

  1. Savel'ev, A. Ya. (1987). Prikladnaya teoriya cifrovyh avtomatov. Moscow: Vysshaya shkola, 272. Available at: https://vdoc.pub/documents/-4o35jbu52gg0
  2. Prihozhiy, A. A. (2013). Chastichno opredelyonnye logicheskie sistemy i algoritmy. Minsk: BNTU, 343. Available at: https://rep.bntu.by/handle/data/37237
  3. Papakonstantinou, K. G., Papakonstantinou, G. (2018). A Nonlinear Integer Programming Approach for the Minimization of Boolean Expressions. Journal of Circuits, Systems and Computers, 27 (10), 1850163. doi: https://doi.org/10.1142/s0218126618501633
  4. Fišer, P., Hlavičcka, J. (2000). Efficient minimization method for Incompletely defined Boolean functions. Conference: 4th Int. Workshop on Boolean Problems (IWSBP). Available at: https://www.researchgate.net/publication/260987269_Efficient_minimization_method_for_incompletely_defined_Boolean_functions
  5. Dimopoulos, A. C., Pavlatos, C., Papakonstantinou, G. (2022). Multi‐output, multi‐level, multi‐gate design using non‐linear programming. International Journal of Circuit Theory and Applications, 50 (8), 2960–2968. doi: https://doi.org/10.1002/cta.3300
  6. Scholl, C., Melchior, S., Hotz, G., Molitor, P. (1997). Minimizing ROBDD sizes of incompletely specified Boolean functions by exploiting strong symmetries. Proceedings European Design and Test Conference. ED & TC 97. doi: https://doi.org/10.1109/edtc.1997.582364
  7. Rytsar, B. (2015). The Minimization Method of Boolean Functions 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
  8. Costamagna, A., De Micheli, G. (2023). Accuracy recovery: A decomposition procedure for the synthesis of partially-specified Boolean functions. Integration, 89, 248–260. doi: https://doi.org/10.1016/j.vlsi.2022.12.008
  9. Boroumand, S., Bouganis, C.-S., Constantinides, G. A. (2021). Learning Boolean Circuits from Examples for Approximate Logic Synthesis. Proceedings of the 26th Asia and South Pacific Design Automation Conference. doi: https://doi.org/10.1145/3394885.3431559
  10. 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
  11. 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
  12. Minimizatsiya nepovnistiu vyznachenykh lohichnykh funktsiy. Available at: https://studfile.net/preview/14499737/page:17/
  13. 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
  14. Pottosin, Yu. V. (2021). Minimization of Boolean functions in the class of orthogonal disjunctive normal forms. Informatics, 18 (2), 33–47. doi: https://doi.org/10.37661/1816-0301-2021-18-2-33-47
  15. Zakrevskij, A. D., Toropov, N. R., Romanov, V. I. (2010). DNF-implementation of partial boolean functions of many variables. Informatics, 1 (25), 102–111. Available at: https://inf.grid.by/jour/article/view/461/419
  16. Solomko, M., Batyshkina, I., Khomiuk, N., Ivashchuk, Y., Shevtsova, N. (2021). Developing the minimization of a polynomial normal form of boolean functions by the method of figurative transformations. Eastern-European Journal of Enterprise Technologies, 2 (4 (110)), 22–37. doi: https://doi.org/10.15587/1729-4061.2021.229786
  17. Riznyk, V., Solomko, M. (2018). Minimization of conjunctive normal forms of boolean functions by combinatorial method. Technology Audit and Production Reserves, 5 (2 (43)), 42–55. doi: https://doi.org/10.15587/2312-8372.2018.146312
  18. Sdvizhkov, O. A. (2012). Diskretnaya matematika i matematicheskie metody ekonomiki s primeneniem VBA Ehcel. Moscow: DMK, 212. Available at: https://www.studmed.ru/sdvizhkov-o-a-diskretnaya-matematika-i-matematicheskie-metody-ekonomiki-s-primeneniem-vba-excel_9edfd48c895.html
  19. Huang, J. (2014). Programing implementation of the Quine-McCluskey method for minimization of Boolean expression. arXiv. doi: https://doi.org/10.48550/arXiv.1410.1059
  20. Matematychna lohika ta dyskretna matematyka (2020). Kremenchuk, 61. Available at: http://document.kdu.edu.ua/metod/2020_2182.pdf
  21. Novytskyi, I. V., Us, S. A. (2013). Dyskretna matematyka v prykladakh i zadachakh. Dnipropetrovsk, 89. Available at: https://sau.nmu.org.ua/ua/osvita/metod/Discrete_Math(Novitskiy_Us_NMU_SAU).pdf
  22. 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. УСиМ, 4, 9–30. Available at: http://dspace.nbuv.gov.ua/handle/123456789/87235
  23. Solomko, M., Batyshkina, I., Voitovych, I., Zubyk, L., Babych, S., Muzychuk, K. (2020). Devising a method of figurative transformations for minimizing boolean functions in the implicative basis. Eastern-European Journal of Enterprise Technologies, 6 (4 (108)), 32–47. doi: https://doi.org/10.15587/1729-4061.2020.220094
  24. Solomko, M., Tadeyev, P., Zubyk, L., Babych, S., Mala, Y., Voitovych, O. (2021). Implementation of the method of figurative transformations to minimizing symmetric Boolean functions. Eastern-European Journal of Enterprise Technologies, 4 (4 (112)), 23–39. doi: https://doi.org/10.15587/1729-4061.2021.239149
  25. Zakrevskiy, A. D. (1981). Logicheskiy sintez kaskadnyh shem. Moscow, 414.
  26. Chu, Z., Pan, H. (2023). Survey on Exact Logic Synthesis Based on Boolean SATisfiability. Journal of Electronics & Information Technology, 45 (1), 14–23. doi: https://doi.org/10.11999/JEIT220391
  27. Yong-Xin, X. (1987). Xiao map for minimization of boolean expression. International Journal of Electronics, 63 (3), 353–358. doi: https://doi.org/10.1080/00207218708939138
  28. Osuagwu, C. C., Anyanwu, C. D., Agada, J. O. (1989). Fast Minimization on the Xiao Map Using Row Group Structure Rules. Nigerian Journal of Technology, 13 (1), 51–61. Available at: https://www.ajol.info/index.php/njt/article/view/123260
Впровадження методу образних перетворень для мінімізації частково визначених булевих функцій

##submission.downloads##

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

2023-02-28

Як цитувати

Соломко, М. Т., Антонюк, М. С., Войтович, І. С., Ульяновська, Ю. В., Павлова, Н. С., & Білецький, В. В. (2023). Впровадження методу образних перетворень для мінімізації частково визначених булевих функцій. Eastern-European Journal of Enterprise Technologies, 1(4 (121), 6–25. https://doi.org/10.15587/1729-4061.2023.273293

Номер

Том 1 № 4 (121) (2023): Математика та кібернетика - прикладні аспекти

Розділ

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

Ліцензія

Авторське право (c) 2023 Mykhailo Solomko, Mykola Antoniuk, Ihor Voitovych, Yuliia Ulianovska, Nataliia Pavlova, Viacheslav Biletskyi

Creative Commons License

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

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

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