Research of 5-bit boolean functions minimization protocols by combinatorial method

Authors

DOI:

https://doi.org/10.15587/2312-8372.2018.140351

Keywords:

minimization method, minimization of a logical function, block-scheme with repetition, protocols for minimization of Boolean functions

Abstract

The object of research is a combinatorial method of 5-bit Boolean functions minimization. One of the most problematic places for Boolean functions minimization is the complexity of the minimization algorithm and the guarantee of obtaining a minimal function.

Minimization protocols of the 5-bit Boolean functions are used in the course of the research, which are used when the structure of the truth table of a given function has a complete binary combinatorial system with repetition or an incomplete binary combinatorial system with repetition. The operational properties of the protocols for 5-bit Boolean functions minimization are based on the laws and axioms of the algebra of logic.

A reduction in the complexity of the process of 5-bit Boolean functions minimization by combinatorial method is obtained, increasing the probability of guaranteed 5-bit Boolean functions minimization. This is due to the fact that the proposed method of 5-bit Boolean functions minimization has a number of features to solve the problem of minimizing the logical function, in particular:

  • the mathematical apparatus of the block diagram with repetition makes it possible to obtain more information on the orthogonality, contiguity, uniqueness of truth table blocks;
  • equivalent transformations by graphic images in the form of two-dimensional matrices due to the greater information capacity can with effect replace the verbal procedures of algebraic transformations;
  • minimization protocols for 5-bit Boolean functions constitute a protocol library for the process of 5-bit Boolean functions minimization as standard procedures, so the use of a separate protocol for variables of 5-bit Boolean functions is reduced to carrying out one algebraic transformation.

Thanks to this, it is possible to obtain an optimal reduction in the number of variable functions without losing its functionality. The effectiveness of the application of minimization protocols for the 5-bit Boolean functions of the combinatorial method is demonstrated by examples of minimization of functions taken from the work of other authors for the purpose of comparison.

In comparison with similar known methods of Boolean functions minimization, this ensures:

  • less complexity of the process of 5-bit Boolean functions minimization;
  • an increase in the probability of guaranteed 5-bit Boolean functions minimization;
  • improvement of the algebraic method of Boolean function minimization due to the tabular organization of the combinatorial method, the introduction of the image-transformation apparatus and the minimization protocols.

Author Biographies

Volodymyr Riznyk, Lviv Polytechnic National University, 12, S. Bandery str., 11, Lviv, Ukraine, 79013

Doctor of Technical Sciences, Professor

Department of Control Aided Systems

Mykhailo Solomko, National University of Water and Environmental Engineering, 11, Soborna str., Rivne, Ukraine, 33028

PhD, Associate Professor

Department of Computer Engineering

References

  1. Riznyk, V., Solomko, M. (2017). Minimization of Boolean functions by combinatorial method. Technology Audit and Production Reserves, 4 (2 (36)), 49–64. doi: http://doi.org/10.15587/2312-8372.2017.108532
  2. 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: http://doi.org/10.15587/2312-8372.2017.118336
  3. Manojlovic, V. (2013). Minimization of Switching Functions using Quine-McCluskey Method. International Journal of Computer Applications, 82 (4), 12–16. doi: http://doi.org/10.5120/14103-2127
  4. Rytsar, B. (2015). The Minimization Method of Boolean Functionns in Polynomial Set-theoretical Format. At Rzeszow, 130–146. Available at: http://ceur-ws.org/Vol-1492/Paper_37.pdf
  5. Rathore, T. S. (2014). Minimal Realizations of Logic Functions Using Truth Table Method with Distributed Simplification. IETE Journal of Education, 55 (1), 26–32. doi: http://doi.org/10.1080/09747338.2014.921412
  6. Dan, R. (2010). Software for The Minimization of The Combinational Logic Functions. The Romanian Review Precision Mechanics, Optics & Mechatronics, 20 (37), 95–99. URL: https://www.researchgate.net/publication/268270733_Software_for_The_Minimization_of_The_Combinational_Logic_Functions_SOFTWARE_FOR_THE_MINIMIZATION_OF_THE_COMBINATIONAL_LOGIC_FUNCTIONS
  7. Zolfaghari, B., Sheidaeian, H. (2011). A New Case for Image Compression Using Logic Function Minimization. The International Journal of Multimedia & Its Applications, 3 (2), 45–62. doi: http://doi.org/10.5121/ijma.2011.3204
  8. Nosrati, M., Karimi, R., Nariri, M. (2012). Minimization of boolean functions using genetic algorithm. Anale. Seria Informatica, X fasc. 1, 73–77. Available at: http://anale-informatica.tibiscus.ro/download/lucrari/10-1-08-Nosrati.pdf
  9. Nosrati, M., Karimi, R. (2011). An Algorithm for Minimizing of Boolean Functions Based on Graph DS. World Applied Programming, 1 (3), 209–214.
  10. Bernasconi, A., Ciriani, V. (2003). Three-Level Logic Minimization Based on Function Regularities. IEEE Transactions on computer-aided design of integrated circuits and systems, 22 (8), 1005–1016. Available at: http://cs.ecs.baylor.edu/~maurer/CSI5346/ThreeLevelMin.pdf
  11. 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: http://doi.org/10.5120/1959-2621
  12. Mohana Ranga Rao, R. (2011). An Innovative procedure to minimize Boolean function. International journal of advanced engineering sciences and technologies, 3 (1), 12–14.
  13. Zakrevskiy, A. D., Pottosin, Yu. V., Cheremisinova, L. D. (2007). Logicheskie osnovy proektirovaniya diskretnykh ustroystv. Matematika. Prikladnaya matematika. Moscow: Fizmatlit, 592. Available at: https://www.twirpx.com/file/2197687/
  14. Ivanov, Yu. D., Zakharova, O. S. (2004). Algoritm sinteza infimumnykh diz"yuktivnykh normal'nykh form logicheskikh funktsiy. Trudy Odesskogo politekhnicheskogo universiteta, 2 (22), 1–7. Available at: http://pratsi.opu.ua/app/webroot/articles/1313074117.pdf
  15. Simplification and minimization of boolean functions. Available at: https://shubh977.files.wordpress.com/2017/02/chap4.pdf Last accessed: 15.07.2017
  16. Sudnitson, A. (2008). Diskretnaya matematika. Minimizatsiya bulevykh funktsiy. Primer iz knigi A. D. Zakrevskogo, 11. Available at: http://ati.ttu.ee/~alsu/DM%20_MinBF_2008_lecture.pdf Last accessed: 15.07.2017
  17. Martyniuk, O. M. (2008). Osnovy dyskretnoi matematyky. Konspekt lektsii. Odeskyi natsionalnyi politekhnichnyi universytet: Nauka i tekhnika, 300.

Downloads

Published

2018-04-24

How to Cite

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. https://doi.org/10.15587/2312-8372.2018.140351

Issue

Vol. 4 No. 2(42) (2018): Information and Control Systems

Section

Mathematical Modeling: Original Research

License

Copyright (c) 2018 Volodymyr Riznyk, Mykhailo Solomko

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.