DOI: https://doi.org/10.15587/2312-8372.2017.118336

Application of super-sticking algebraic operation of variables for Boolean functions minimization by combinatorial method

Volodymyr Riznyk, Mykhailo Solomko

Abstract


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.


Keywords


Boolean function; minimization method; minimization of a logical function; block-diagram with repetition; minterm; 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/Карта_Карно


GOST Style Citations


Quine–McCluskey algorithm [Electronic resource] // Wikipedia. – August 1, 2017 – Available at: \www/URL: https://en.wikipedia.org/wiki/Quine%E2%80%93McCluskey_algorithm

Riznyk, V. Minimization of Boolean functions by combinatorial method [Text] / V. Riznyk, M. Solomko // Technology Audit and Production Reserves. – 2017. – Vol. 4, No. 2 (36). – P. 49–64. doi:10.15587/2312-8372.2017.108532

Solairaju, A. Optimal Boolean Function Simplification through K-Map using Object-Oriented Algorithm [Text] / A. Solairaju, R. Periyasamy // International Journal of Computer Applications. – 2011. – Vol. 15, No. 7. – P. 28–32. doi:10.5120/1959-2621

Kumar, R. Cubical Representation and Minimization through Cubical Technique A Tabular Approach [Text] / R. Kumar, S. Rawat // International Journal of Applied Engineering Research. – 2016. – Vol. 11, No. 7. – P. 4822–4829. – Available at: \www/URL: https://www.ripublication.com/ijaer16/ijaerv11n7_27.pdf

Stergiou, S. A Fast and Efficient Heuristic ESOP Minimization Algorithm [Text] / S. Stergiou, K. Daskalakis, G. Papakonstantinou // Proceedins of the 14th ACM Great Lakes symposium on VLSI – GLSVLSI '04. – Boston, 2004. doi:10.1145/988952.988971

Dusa, A. Enhancing the Minimization of Boolean and Multivalue Output Functions WitheQMC [Text] / A. Dusa, A. Thiem // The Journal of Mathematical Sociology. – 2015. – Vol. 39, No. 2. – P. 92–108. doi:10.1080/0022250x.2014.897949

Voudouris, D. Exact ESCT minimization for functions of up to six input variables – PRELIMINARY VERSION [Electronic resource] / D. Voudouris, M. Sampson, G. Papakonstantinou. – 2005. – 17 p. – Available at: \www/URL: http://mule.cslab.ece.ntua.gr/xor/docs/xmin6.pdf

Valli, M. A State of Appraoches on Minimization of Boolean Functions [Text] / M. Valli, R. Periyasamy, J. Amudhavel // Journal of Advanced Research in Dynamical and Control Systems. – 2017. – No. 12. – P. 1322–1341. – Available at: \www/URL: http://www.jardcs.org/abstract.php?archiveid=1323#

Boyar, J. A New Combinational Logic Minimization Technique with Applications to Cryptology [Text] / J. Boyar, R. Peralta // Lecture Notes in Computer Science. – 2010. – P. 178–189. doi:10.1007/978-3-642-13193-6_16

Eungi, K. Derivations of Single Hypothetical Don't-Care Minterms Using the Quasi Quine-McCluskey Method [Text] / K. Eungi // Journal of the Korea Industrial Information Systems Research. – 2013. – Vol. 18, No. 1. – P. 25–35. doi:10.9723/jksiis.2013.18.1.025

Dubrova, E. Minimization of Multiple-Valued Functions in Post Algebra [Electronic resource] / E. Dubrova, Y. Jiang, R. Brayton. – 2001. – 5 p. Available at: \www/URL: https://pdfs.semanticscholar.org/e9fa/a422aad8b92c0448eb8d41425852717cb637.pdf

Anjuli, S. A. 2-Bit Magnitude Comparator Design Using Different Logic Styles [Text] / A. S. Anand // International Journal of Engineering Science Invention. – 2013. – Vol. 2, No. 1. – P. 13–24. – Available at: \www/URL: http://www.ijesi.org/papers/Vol(2)1%20(version%202)/C211324.pdf

Buniak, A. Elektronika ta mikroskhemotekhnika [Text] / A. Buniak. – Kyiv: Aston, 2001. – 382 p.

Rytsar, B. Ye. Minimization of logic functions system by konjuncterms parallel splittingmethod [Text] / B. Ye. Rytsar // Bulletin of the Lviv Polytechnic National University. Radio Electronics and Telecommunications. – 2013. – No. 766. – P. 18–27. – Available at: \www/URL: http://nbuv.gov.ua/UJRN/VNULPPT_2013_766_6

Rytsar, B. Ye. New minimization method of logical functions in polynomial set-theoretical format. 1. Generalized rules of conjuncterms simplification [Text] / B. Ye. Rytsar // Upravliaiushchie sistemy i mashiny. – 2015. – Vol. 2. – P. 39–57. – Available at: \www/URL: http://dspace.nbuv.gov.ua/handle/123456789/87194

Samofalov, K. G. Prikladnaia teoriia tsifrovyh avtomatov [Text] / K. G. Samofalov, A. M. Romlinkevich, V. N. Valuiskii, Yu. S. Kanevskii, M. M. Pinevich. – Kyiv: Vishcha shkola, 1987. – 375 p.

Plehanov, A. Simmetrichnye karty kak sredstvo minimizatsii bulevyh funktsii [Electronic resource] / A. Plehanov // Geektimes. – March 8, 2016. – Available at: \www/URL: https://geektimes.ru/post/272294/

Plehanov, A. Eshche raz o minimizatsii bulevyh funktsii [Electronic resource] / A. Plehanov // Habrahabr. – May 5, 2016. – Available at: \www/URL: https://habrahabr.ru/post/283030/

Triohmernaia karta Karno [Electronic resource] // Cyclowiki. – February 9, 2016. – Available at: \www/URL: http://cyclowiki.org/wiki/Трёхмерная_карта_Карно

Karta Karno [Electronic resource] // Wikipedia. – September 30, 2017. Available at: \www/URL: https://ru.wikipedia.org/wiki/Карта_Карно







Copyright (c) 2017 Volodymyr Riznyk, Mykhailo Solomko

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

ISSN (print) 2664-9969, ISSN (on-line) 2706-5448