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

Автор(и)

  • Михайло Тимофійович Соломко Національний університет водного господарства та природокористування, Україна https://orcid.org/0000-0003-0168-5657

DOI:

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

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

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

Анотація

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

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

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

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

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

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

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

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

Посилання

  1. Nalimov, V. V. (1993). V poiskah inyh smyslov. Moscow: Izdatel'skaya gruppa «Progres», 280. Available at: https://platona.net/load/knigi_po_filosofii/filosofija_poznanija/nalimov_v_poiskakh_inykh_smyslov/45-1-0-566
  2. Glushkov, V. M. (1986). Kibernetika. Voprosy teorii i praktiki. Moscow: Nauka, 488. Available at: http://www.pseudology.org/science/Glushkov_Kibernetika._Voprosue_teorii_i_practiki.pdf
  3. Zakrevsky, A. D. (1960). Visual-matrix method for minimization of boolean functions. Avtomatika i Telemekhanika, 21 (3), 369–373. Available at: http://www.mathnet.ru/links/fcef8cd452ff8b3804279fce2157d772/at12511.pdf
  4. Plehl', O.; Yurasov, A. N. (Ed.) (1959). Elektromehanicheskaya kommutatsiya i kommutatsionnye apparaty. (Kontaktnye shemy i apparaty). Vvedenie v teoriyu i raschet. Moscow; Leningrad: Gosenergoizdat, 288. Available at: https://catalogue.nure.ua/document=101624
  5. Svoboda, A. (1956). Utilization of graphical-mechanical aids for the analysis and synthesis of contact circuits. Symposium on information processing machines. Prague: Czechoslovak Academy of Sciences, Research Institute of Mathematical Machines. 9–22.
  6. Karnaugh, M. (1953). The map method for synthesis of combinational logic circuits. Transactions of the American Institute of Electrical Engineers, 72, 593–598.
  7. Donets, S. (2015). Sources of implicit informativity of image. Filolohichni nauky, 21, 107–112. Available at: http://dspace.pnpu.edu.ua/handle/123456789/6095
  8. 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
  9. 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
  10. 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
  11. Kondratenko, N. R. (2010). Kompiuternyi praktykum z matematychnoi lohiky. Vinnytsia: VNTU, 117. Available at: https://www.twirpx.com/file/993689/
  12. 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
  13. Başçiftçi, F., Akar, H. (2020). Smart minterm ordering and accumulation approach for insignificant function minimization. Ain Shams Engineering Journal. doi: https://doi.org/10.1016/j.asej.2020.04.003
  14. Bernasconi, A., Ciriani, V., Villa, T. (2020). Exploiting Symmetrization and D-reducibility for Approximate Logic Synthesis. IEEE Transactions on Computers, 1–1. doi: https://doi.org/10.1109/tc.2020.3043476
  15. Young, M. H., Muroga, S. (1985). Minimal covering problem and PLA minimization. International Journal of Computer & Information Sciences, 14 (6), 337–364. doi: https://doi.org/10.1007/bf00991179
  16. Huang, J. (2014). Programing implementation of the Quine-McCluskey method for minimization of Boolean expression. arXiv.org. Available at: https://arxiv.org/ftp/arxiv/papers/1410/1410.1059.pdf
  17. El-Bakry, H. M., Mastorakis, N. (2009). A fast computerized method for automatic simplification of boolean functions. Proceedings of the 9th WSEAS International Conference on SYSTEMS THEORY AND SCIENTIFIC COMPUTATION (ISTASC '09), 99–107. Available at: https://www.researchgate.net/profile/Hazem_El-Bakry/publication/228877182_A_fast_computerized_method_for_automatic_simplification_of_boolean_functions/links/553fa8230cf29680de9bf997/A-fast-computerized-method-for-automatic-simplification-of-boolean-functions.pdf
  18. Duşa, A., Thiem, A. (2015). Enhancing the Minimization of Boolean and Multivalue Output Functions WitheQMC. The Journal of Mathematical Sociology, 39 (2), 92–108. doi: https://doi.org/10.1080/0022250x.2014.897949
  19. Dusa, A. (2019). Consistency Cubes: a fast, efficient method for exact Boolean minimization. The R Journal, 10 (2), 357. doi: https://doi.org/10.32614/rj-2018-080
  20. Rudell, R. L. (1989). Logic synthesis for VLSI design. Electronics Research Laboratory. Available at: http://www.cs.columbia.edu/~cs6861/handouts/rudell-PhD-thesis.pdf
  21. Senchukov, V., Denysova, T. (2020). v-minimization of Boolean functions by a distance matrix and reduction to the problem of mathematical programming. Open Information and Computer Integrated Technologies, 88, 123–133. doi: https://doi.org/10.32620/oikit.2020.88.10
  22. Rytsar, B. Ye. (2013). Minimization of logic functions system by konjuncterms parallel splitting method. Visnyk Natsionalnoho universytetu "Lvivska politekhnika". Radioelektronika ta telekomunikatsiyi, 766, 18–27. Available at: http://nbuv.gov.ua/UJRN/VNULPPT_2013_766_6
  23. Pospelov, D. A. (1974). Logicheskie metody analiza i sinteza skhem. Moscow: «Energiya», 368. Available at: http://urss.ru/cgi-bin/db.pl?lang=Ru&blang=ru&page=Book&id=25326
  24. Shestakov, V. I. (Ed.) (1954). Sintez elektronnyh vychislitel'nyh i upravlyayushchih shem. Moscow, 358.
  25. Metody minimizatsii funktsiy algebry logiki. Material iz Natsional'noy biblioteki im. N. E. Baumana. Available at: https://ru.bmstu.wiki/Методы_минимизации_функций_алгебры_логики
  26. Logic Friday 1.1.4. Available at: https://www.softpedia.com/get/Others/Home-Education/Logic-Friday.shtml
  27. Minimizator evristicheskoy logiki espresso. Available at: https://ru.qaz.wiki/wiki/Espresso_heuristic_logic_minimizer
  28. Boolean functions' minimisation software based on the Quine-McCluskey method. Available at: http://www.seattlerobotics.org/encoder/200106/qmccmin.htm
  29. JQM Java Quine McCluskey. Available at: https://sourceforge.net/projects/jqm-java-quine-mccluskey/
  30. Kumar, V. D. A., Amuthan, S. G. (2016). Static structure simplification of boolean function for “n” variables - a novel approach. ICTACT Journal on Microelectronics, 1 (4), 160–167. doi: https://doi.org/10.21917/ijme.2016.0024
  31. Web service Python. Available at: https://trinket.io/python/fbbf7518b8
  32. 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
  33. 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

##submission.downloads##

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

2021-02-26

Як цитувати

Соломко, М. Т. (2021). Розробка алгоритму мінімізації булевих функцій для візуально-матричної форми аналітичного методу. Eastern-European Journal of Enterprise Technologies, 1(4 (109), 6–21. https://doi.org/10.15587/1729-4061.2021.225325

Номер

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

Розділ

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

Ліцензія

Авторське право (c) 2021 Михаил Тимофеевич Соломко

Creative Commons License

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

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

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