Application of super-sticking algebraic operation of variables for Boolean functions minimization by combinatorial method
DOI:
https://doi.org/10.15587/2312-8372.2017.118336Keywords:
Boolean function, minimization method, minimization of a logical function, block-diagram with repetition, minterm, super-sticking of variablesAbstract
The simplification of the problem of Boolean function minimization by a combinatorial method is a new procedure for the algebra of logic – super-sticking of variables. This procedure is performed if there is a complete binary combinatorial system with repetition or an incomplete binary combinatorial system with repetition in the truth table structure.
The procedure for reducing the total perfect disjunctive normal form (PDNF) of the logical function gives unity. And since the complete PDNF uniquely determines the complete binary combinatorial system with repetition and vice versa, this gives grounds to delete all the blocks of the complete binary combinatorial system from the truth table, whose structure allows to carry out the rules of super-sticking of variables.
The efficiency of the algebraic operation of supers-sticking of variables greatly simplifies the algorithm for Boolean function minimization and allows manual minimization of functions with a number of variables up to 10.
The complexity of the algorithm for finding the minimal function by a combinatorial method is O(n) and is linear for n<7. With an increase in the number of variables from n=6 to 8, the growth dynamics of the number of transformations is characterized by the law O(n2), followed by the growth of O(f(n)) with the increase in the Boolean function capacity according to the polynomial law.
The introduction of an algebraic operation of super-sticking of variables to the problem of Boolean function minimization is more advantageous in comparison with analogs in the following factors:
– lower cost of development and implementation, since a significant proportion of functions are minimized by functions with a number of variables of no more than 16, and therefore, in general, the need for automation of the process of minimizing the function decreases;
– increase in manual minimization of 4–10 bit functions, facilitates control and study of the algorithm for minimizing the logic function.
The combinatorial method of Boolean functions minimization can find practical application in the design of electronic computer systems, because:
– minimization of the DNF function is one of the multiextremal logic-combinatorial problems, the solution of which is, in particular, the combinatorial device of the block-diagram with repetition;
– extends the capabilities of the algorithm for Boolean functions minimization for their application in information technology;
– improves the algebraic method of Boolean function minimization due to the tabular organization of the method, the introduction of the shaped transformation apparatus and the rules of super-sticking of variables.
References
- Quine–McCluskey algorithm. (2017, August 1). Wikipedia. Available at: https://en.wikipedia.org/wiki/Quine%E2%80%93McCluskey_algorithm
- Riznyk, V., Solomko, M. (2017). Minimization of Boolean functions by combinatorial method. Technology Audit and Production Reserves, 4 (2 (36)), 49–64. doi:10.15587/2312-8372.2017.108532
- 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:10.5120/1959-2621
- 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. Available at: https://www.ripublication.com/ijaer16/ijaerv11n7_27.pdf
- Stergiou, S., Daskalakis, K., Papakonstantinou, G. (2004). A Fast and Efficient Heuristic ESOP Minimization Algorithm. Proceedins of the 14th ACM Great Lakes symposium on VLSI – GLSVLSI '04. Boston. doi:10.1145/988952.988971
- Dusa, A., Thiem, A. (2015). Enhancing the Minimization of Boolean and Multivalue Output Functions WitheQMC. The Journal of Mathematical Sociology, 39 (2), 92–108. doi:10.1080/0022250x.2014.897949
- Voudouris, D., Sampson, M., Papakonstantinou, G. (2005). Exact ESCT minimization for functions of up to six input variables – PRELIMINARY VERSION, 17. Available at: http://mule.cslab.ece.ntua.gr/xor/docs/xmin6.pdf
- Valli, M., Periyasamy, R., Amudhavel, J. (2017). A State of Appraoches on Minimization of Boolean Functions. Journal of Advanced Research in Dynamical and Control Systems, 12, 1322–1341. Available at: http://www.jardcs.org/abstract.php?archiveid=1323#
- Boyar, J., Peralta, R. (2010). A New Combinational Logic Minimization Technique with Applications to Cryptology. Lecture Notes in Computer Science, 178–189. doi:10.1007/978-3-642-13193-6_16
- Eungi, K. (2013). Derivations of Single Hypothetical Don't-Care Minterms Using the Quasi Quine-McCluskey Method. Journal of the Korea Industrial Information Systems Research, 18 (1), 25–35. doi: 10.9723/jksiis.2013.18.1.025
- Dubrova, E., Jiang, Y., Brayton, R. (2001). Minimization of Multiple-Valued Functions in Post Algebra, 5. Available at: https://pdfs.semanticscholar.org/e9fa/a422aad8b92c0448eb8d41425852717cb637.pdf
- Anjuli, S. A. (2013). 2-Bit Magnitude Comparator Design Using Different Logic Styles. International Journal of Engineering Science Invention, 2 (1), 13–24. Available at: http://www.ijesi.org/papers/Vol(2)1%20(version%202)/C211324.pdf
- Buniak, A. (2001). Elektronika ta mikroskhemotekhnika. Kyiv: Aston, 382.
- Rytsar, B. Ye. (2013). Minimization of logic functions system by konjuncterms parallel splittingmethod. Bulletin of the Lviv Polytechnic National University. Radio Electronics and Telecommunications, 766, 18–27. Available at: http://nbuv.gov.ua/UJRN/VNULPPT_2013_766_6
- Rytsar, B. Ye. (2015). New minimization method of logical functions in polynomial set-theoretical format. 1. Generalized rules of conjuncterms simplification. Upravliaiushchie sistemy i mashiny, 2, 39–57. Available at: http://dspace.nbuv.gov.ua/handle/123456789/87194
- Samofalov, K. G., Romlinkevich, A. M., Valuiskii, V. N., Kanevskii, Yu. S., Pinevich, M. M. (1987). Prikladnaia teoriia tsifrovyh avtomatov. Kyiv: Vishcha shkola, 375.
- Plehanov, A. (2016, March 8). Simmetrichnye karty kak sredstvo minimizatsii bulevyh funktsii. Geektimes. Available at: https://geektimes.ru/post/272294/
- Plehanov, A. (2016, May 5). Eshche raz o minimizatsii bulevyh funktsii. Habrahabr. Available at: https://habrahabr.ru/post/283030/
- Triohmernaia karta Karno. (2016, February 9). Cyclowiki. Available at: http://cyclowiki.org/wiki/Трёхмерная_карта_Карно
- Karta Karno. (2017, September 30). Wikipedia. Available at: https://ru.wikipedia.org/wiki/Карта_Карно
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2017 Volodymyr Riznyk, Mykhailo Solomko
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.
