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

Автор(и)

  • Volodymyr Riznyk Національний університет «Львівська політехніка» вул. С. Бандери, 12, м. Львов, Україна, 79013, Україна https://orcid.org/0000-0002-3880-4595
  • Mykhailo Solomko Національний університет водного господарства та природокористування вул. Соборна, 11, м. Рівне, Україна, 33028, Україна https://orcid.org/0000-0003-0168-5657
  • Petro Tadeyev Національний університет водного господарства та природокористування вул. Соборна, 11, м. Рівне, Україна, 33028, Україна https://orcid.org/0000-0002-2885-6674
  • Vitalii Nazaruk Національний університет водного господарства та природокористування вул. Соборна, 11, м. Рівне, Україна, 33028, Україна https://orcid.org/0000-0003-3705-5155
  • Liudmyla Zubyk Київський національний університет імені Тараса Шевченка вул. Володимирська, 60, м. Київ, Україна, 01033, Україна https://orcid.org/0000-0002-2087-5379
  • Volodymyr Voloshyn Національний університет водного господарства та природокористування вул. Соборна, 11, м. Рівне, Україна, 33028, Україна https://orcid.org/0000-0001-8108-0126

DOI:

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

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

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

Анотація

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

Встановлена відповідність інтервалів I(α, β) у булевому просторі ẞn, які задаються парою булевих векторів α і β, таких, що α≼β з повною комбінаторною системою з повторенням 2-(n, b)-блок-схем (англ. 2-(n, b)-designs). Внутрішні компоненти інтервалу I(α, β) відповідають повній системі 2-(n, b)-design, а зовнішні – визначаються розрахунком кількості нулів або одиниць у стовпчиках таблиці істинності заданої логічної функції. Це дозволяє використовувати теорію інтервалів I(α, β) у математичному апараті комбінаторних систем 2-(n, b)-design для проведення мінімізації булевих функцій методом рівносильних образних перетворень, зокрема здійснювати автоматизований пошук систем 2-(n, b)-design у структурі таблиці істинності.

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

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

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

Volodymyr Riznyk, Національний університет «Львівська політехніка» вул. С. Бандери, 12, м. Львов, Україна, 79013

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

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

Mykhailo Solomko, Національний університет водного господарства та природокористування вул. Соборна, 11, м. Рівне, Україна, 33028

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

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

Petro Tadeyev, Національний університет водного господарства та природокористування вул. Соборна, 11, м. Рівне, Україна, 33028

Кандидат фізико-математичних наук, доктор педагогічних наук, професор

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

Vitalii Nazaruk, Національний університет водного господарства та природокористування вул. Соборна, 11, м. Рівне, Україна, 33028

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

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

Liudmyla Zubyk, Київський національний університет імені Тараса Шевченка вул. Володимирська, 60, м. Київ, Україна, 01033

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

Кафедра програмних систем і технологій

Volodymyr Voloshyn, Національний університет водного господарства та природокористування вул. Соборна, 11, м. Рівне, Україна, 33028

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

Кафедра комп’ютерних технологій та економічної кібернетики

Посилання

  1. Curtis, H. A. (1962). A new approach to the design of switching circuits. N.J.: Princeton, Toronto, 635.
  2. Mayorov, S. A. (Ed.) (1972). Proektirovanie tsifrovyh vychislitel'nyh mashin. Moscow: Vysshaya shkola, 344.
  3. Pospelov, D. A. (1974). Logicheskie metody analiza i sinteza shem. Moscow: Energiya, 368.
  4. Zakrevskiy, A. D. (1981). Logicheskiy sintez kaskadnyh shem. Moscow: Nauka, 416.
  5. Rytsar, B. E. (1997). Metod minimizatsii bulevyh funktsiy. Problemy upravleniya i informatiki, 2, 100–113.
  6. 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
  7. Riznyk, V., Solomko, M. (2017). Minimization of Boolean functions by combinatorial method. Technology Audit and Production Reserves, 4 (2 (36)), 49–64. doi: https://doi.org/10.15587/2312-8372.2017.108532
  8. 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
  9. 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
  10. Dan, R. (2010). Software for The Minimization of The Combinational Logic Functions. The Romanian Review Precision Mechanics, Optics & Mchatronics, 37, 95–99. Available at: https://pdfs.semanticscholar.org/b881/59ffd963e4cb44d513eba58230e56f1e5605.pdf
  11. Huang, J. (2014). Programing implementation of the Quine-McCluskey method for minimization of Boolean expression. arXiv. Available at: https://arxiv.org/ftp/arxiv/papers/1410/1410.1059.pdf
  12. Nosrati, M., Karimi, R. (2011). An Algorithm for Minimizing of Boolean Functions Based on Graph DS. World Applied Programming, 1 (3), 209–214.
  13. Solairaju, A., Periyasamy, R. (2011). Optimal Boolean Function Simplification through K-Map using Object-Oriented Algorithm. International Journal of Computer Applications, 15 (7), 28–32. doi: https://doi.org/10.5120/1959-2621
  14. Boyar, J., Peralta, R. (2010). A New Combinational Logic Minimization Technique with Applications to Cryptology. Lecture Notes in Computer Science, 178–189. doi: https://doi.org/10.1007/978-3-642-13193-6_16
  15. Chen, Z., Ma, H., Zhang, Y. (2014). A Rapid Granular Method for Minimization of Boolean Functions. Lecture Notes in Computer Science, 577–585. doi: https://doi.org/10.1007/978-3-319-11740-9_53
  16. 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
  17. Kabalan, K. Y., El-Hajj, A., Fakhreddine, S., Smari, W. S. (1995). Computer tool for minimizing logic functions. Computer Applications in Engineering Education, 3 (1), 55–64. doi: https://doi.org/10.1002/cae.6180030108
  18. Bulevy konstanty i vektory. Available at: https://studfile.net/preview/4243601/
  19. Nazarova, I. A. (2012). Dyskretnyi analiz. Donetsk, 277. Available at: http://ea.donntu.edu.ua/bitstream/123456789/27328/1/%D0%9D%D0%9F_%D0%94%D0%90_%D0%A3%D0%9A%D0%A0%20%28%D0%9F%D0%BE%D0%BB%D0%BD%D0%B8%D0%B9%29.pdf
  20. Samofalov, K. G., Romlinkevich, A. M., Valuyskiy, V. N., Kanevskiy, Yu. S, Pinevich, M. M. (1987). Prikladnaya teoriya tsifrovyh avtomatov. Kyiv, 375. Available at: http://stu.scask.ru/book_pta.php?id=62
  21. Bonal, D. (2013). Karnaugh and Mahoney – Map Methods for Minimizing Boolean Expressions. Available at: http://davidbonal.com/karnaugh-and-mahoney-map-methods-for-minimizing-boolean-expressions/
  22. Filippov, V. M., Manohina, T. V., Evdokimov, A. A., Zayats, D. S. (2016). Minimizatsiya funktsiy algebry logiki metodom nenapravlennogo grafa. Mezhdunarodniy zhurnal prikladnyh i fundamental'nyh issledovaniy, 8 (4), 509–511. Available at: https://applied-research.ru/ru/article/view?id=10112
  23. Kumar, R., Rawat, S. (2016). Cubical Representation and Minimization through Cubical Technique A Tabular Approach. International Journal of Applied Engineering Research, 11 (7), 4822–4829.

##submission.downloads##

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

2020-06-30

Як цитувати

Riznyk, V., Solomko, M., Tadeyev, P., Nazaruk, V., Zubyk, L., & Voloshyn, V. (2020). Алгоритм мінімізації булевих функцій методом оптимального комбінування послідовності образних перетворень. Eastern-European Journal of Enterprise Technologies, 3(4 (105), 43–60. https://doi.org/10.15587/1729-4061.2020.206308

Номер

Том 3 № 4 (105) (2020): Математика та кібернетика - прикладні аспекти

Розділ

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

Ліцензія

Авторське право (c) 2020 Volodymyr Riznyk, Mykhailo Solomko, Petro Tadeyev, Vitalii Nazaruk, Liudmyla Zubyk, Volodymyr Voloshyn

Creative Commons License

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

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

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