Developing an algorithm to minimize boolean functions for the visual-matrix form of the analytical method

Authors

DOI:

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

Keywords:

Boolean function minimization, visual-matrix form of analytical method, binary matrix

Abstract

This research has established the possibility of improving the effectiveness of the visual-matrix form of the analytical Boolean function minimization method by identifying reserves in a more complex algorithm for the operations of logical absorption and super-gluing the variables in terms of logical functions.

An improvement in the efficiency of the Boolean function minimization procedure was also established, due to selecting, according to the predefined criteria, the optimal stack of logical operations for the first and second binary matrices of Boolean functions. When combining a sequence of logical operations using different techniques for gluing variables such as simple gluing and super-gluing, there are a small number of cases when function minimization is more effective if an operation of simply gluing the variables is first applied to the first matrix. Thus, a short analysis is required for the primary application of operations in the first binary matrix. That ensures the proper minimization efficiency regarding the earlier unaccounted-for variants for simplifying the Boolean functions by the visual-matrix form of the analytical method. For a series of cases, the choice of the optimal stack is also necessary for the second binary matrix.

The experimental study has confirmed that the visual-matrix form of the analytical method, whose special feature is the use of 2-(n, b)-design and 2-(n, x/b)-design systems in the first matrix, improves the process efficiency, as well as the reliability of the result of Boolean function minimization. This simplifies the procedure of searching for a minimal function. Compared to analogs, that makes it possible to improve the productivity of the Boolean function minimization process by 100‒200 %.

There is reason to assert the possibility of improving the efficiency of the Boolean function minimization process by the visual-matrix form of the analytical method, through the use of more complex logical operations of absorbing and super-gluing the variables. Also, by optimally combining the sequence of logical operations of super-gluing the variables and simply gluing the variables, based on the selection, according to the established criteria, of the stack of logical operations in the first binary matrix of the assigned function

Author Biography

Mykhailo Solomko, National University of Water and Environmental Engineering

PhD, Associate Professor

Department of Computer Engineering

References

  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

Downloads

Published

2021-02-26

How to Cite

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. https://doi.org/10.15587/1729-4061.2021.225325

Issue

Vol. 1 No. 4 (109) (2021): Mathematics and Cybernetics - applied aspects

Section

Mathematics and Cybernetics - applied aspects

License

Copyright (c) 2021 Михаил Тимофеевич Соломко

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

The consolidation and conditions for the transfer of copyright (identification of authorship) is carried out in the License Agreement. In particular, the authors reserve the right to the authorship of their manuscript and transfer the first publication of this work to the journal under the terms of the Creative Commons CC BY license. At the same time, they have the right to conclude on their own additional agreements concerning the non-exclusive distribution of the work in the form in which it was published by this journal, but provided that the link to the first publication of the article in this journal is preserved.

A license agreement is a document in which the author warrants that he/she owns all copyright for the work (manuscript, article, etc.).
The authors, signing the License Agreement with TECHNOLOGY CENTER PC, have all rights to the further use of their work, provided that they link to our edition in which the work was published.
According to the terms of the License Agreement, the Publisher TECHNOLOGY CENTER PC does not take away your copyrights and receives permission from the authors to use and dissemination of the publication through the world's scientific resources (own electronic resources, scientometric databases, repositories, libraries, etc.).
In the absence of a signed License Agreement or in the absence of this agreement of identifiers allowing to identify the identity of the author, the editors have no right to work with the manuscript.
It is important to remember that there is another type of agreement between authors and publishers – when copyright is transferred from the authors to the publisher. In this case, the authors lose ownership of their work and may not use it in any way.