DOI: https://doi.org/10.15587/1729-4061.2020.206308

The algorithm for minimizing Boolean functions using a method of the optimal combination of the sequence of figurative transformations

Volodymyr Riznyk, Mykhailo Solomko, Petro Tadeyev, Vitalii Nazaruk, Liudmyla Zubyk, Volodymyr Voloshyn

Abstract


The reported study has established the possibility of improving the productivity of an algorithm for the minimization of Boolean functions using a method of the optimal combination of the sequence of logical operations applying different techniques for gluing the variables ‒ simple gluing and super-gluing.

The correspondence of intervals I(α, β) in the Boolean space ẞnhas been established, given by a pair of Boolean vectors α and β, such that α≼β, with a complete combinatorial system with the repeated 2-(n, b)-designs. The internal components of the interval I(α, β) correspond to the complete 2-(n, b)-design system while external ones are determined by calculating the number of zeros or unities in the columns of the truth table of the assigned logical function. This makes it possible to use the theory of I(α, β) intervals in the mathematical apparatus of 2-(n, b)-design combinatorial systems to minimize Boolean functions by the method of equivalent figurative transformations, in particular, to perform automated search for the 2-(n, b)-design systems in the structure of a truth table.

Experimental study has confirmed that the combinatorial 2-(n, b)-design system and the consistent alternation of logical operations of super-gluing the variables (if such an operation is possible) and the simple gluing of variables in the first truth table improves the efficiency of the process and the reliability of results from minimizing the Boolean functions. This simplifies algorithmizing the search for the 2-(n, b)-design system in the structure of a truth table of the assigned logical function, which would provide for the tool to further automate the search for the 2-(n, b)-design system. In comparison with analogs, it enables increasing the productivity of the Boolean function minimization process by 100–200 % by using an optimum alternation of operations of super gluing and simple gluing of variables by the method of equivalent figurative transformations.

There are reasons to argue about the possibility to improve the productivity of the Boolean function minimization process by the optimal combination of the sequences of the logical operations of super-gluing the variables and the simple gluing of variables by the method of equivalent figurative transformations

Keywords


Boolean function minimization; optimal combination of the sequence of figurative transformations; Mahoney map

References


Curtis, H. A. (1962). A new approach to the design of switching circuits. N.J.: Princeton, Toronto, 635.

Mayorov, S. A. (Ed.) (1972). Proektirovanie tsifrovyh vychislitel'nyh mashin. Moscow: Vysshaya shkola, 344.

Pospelov, D. A. (1974). Logicheskie metody analiza i sinteza shem. Moscow: Energiya, 368.

Zakrevskiy, A. D. (1981). Logicheskiy sintez kaskadnyh shem. Moscow: Nauka, 416.

Rytsar, B. E. (1997). Metod minimizatsii bulevyh funktsiy. Problemy upravleniya i informatiki, 2, 100–113.

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

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

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

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

Dan, R. (2010). Software for The Minimization of The Combinational Logic Functions. The Romanian Review Precision Mechanics, Optics & Mchatronics, 37, 95–99. Available at: https://pdfs.semanticscholar.org/b881/59ffd963e4cb44d513eba58230e56f1e5605.pdf

Huang, J. (2014). Programing implementation of the Quine-McCluskey method for minimization of Boolean expression. arXiv. Available at: https://arxiv.org/ftp/arxiv/papers/1410/1410.1059.pdf

Nosrati, M., Karimi, R. (2011). An Algorithm for Minimizing of Boolean Functions Based on Graph DS. World Applied Programming, 1 (3), 209–214.

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: https://doi.org/10.5120/1959-2621

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

Chen, Z., Ma, H., Zhang, Y. (2014). A Rapid Granular Method for Minimization of Boolean Functions. Lecture Notes in Computer Science, 577–585. doi: https://doi.org/10.1007/978-3-319-11740-9_53

Papakonstantinou, K. G., Papakonstantinou, G. (2018). A Nonlinear Integer Programming Approach for the Minimization of Boolean Expressions. Journal of Circuits, Systems and Computers, 27 (10), 1850163. doi: https://doi.org/10.1142/s0218126618501633

Kabalan, K. Y., El-Hajj, A., Fakhreddine, S., Smari, W. S. (1995). Computer tool for minimizing logic functions. Computer Applications in Engineering Education, 3 (1), 55–64. doi: https://doi.org/10.1002/cae.6180030108

Bulevy konstanty i vektory. Available at: https://studfile.net/preview/4243601/

Nazarova, I. A. (2012). Dyskretnyi analiz. Donetsk, 277. Available at: http://ea.donntu.edu.ua/bitstream/123456789/27328/1/%D0%9D%D0%9F_%D0%94%D0%90_%D0%A3%D0%9A%D0%A0%20%28%D0%9F%D0%BE%D0%BB%D0%BD%D0%B8%D0%B9%29.pdf

Samofalov, K. G., Romlinkevich, A. M., Valuyskiy, V. N., Kanevskiy, Yu. S, Pinevich, M. M. (1987). Prikladnaya teoriya tsifrovyh avtomatov. Kyiv, 375. Available at: http://stu.scask.ru/book_pta.php?id=62

Bonal, D. (2013). Karnaugh and Mahoney – Map Methods for Minimizing Boolean Expressions. Available at: http://davidbonal.com/karnaugh-and-mahoney-map-methods-for-minimizing-boolean-expressions/

Filippov, V. M., Manohina, T. V., Evdokimov, A. A., Zayats, D. S. (2016). Minimizatsiya funktsiy algebry logiki metodom nenapravlennogo grafa. Mezhdunarodniy zhurnal prikladnyh i fundamental'nyh issledovaniy, 8 (4), 509–511. Available at: https://applied-research.ru/ru/article/view?id=10112

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.


GOST Style Citations








Copyright (c) 2020 Volodymyr Riznyk, Mykhailo Solomko, Petro Tadeyev, Vitalii Nazaruk, Liudmyla Zubyk, Volodymyr Voloshyn

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

ISSN (print) 1729-3774, ISSN (on-line) 1729-4061