Index method of minimization of boolean functions
Abstract
The paper presents a new method of minimization that implements the Boolean function in classical minimal form of representation by means of a directed selection of possible ways of minimization according to the criteria of a necessary and sufficient condition – the index method. This method is a continuation of evolutionary development of methods of minimization by reducing the value of the basis coefficient K: the method of minimization by parts, the method of parallel decomposition by reducing K, the matrix method of parallel decomposition. The evolution of methods by reducing the value of the basis coefficient K is a thorough study of the structure and structural organization of a set of Boolean functions, a detailed analysis of the strengths and weaknesses of already existing previous variants of the methods, the identification of critical places that significantly slow down the minimization process, and the search for alternative ways of accelerating the minimization process. The index method is developed based on the use of a new way of recording individual Boolean functions in the form of indexes of significant rows of the truth table. Thanks to this form of recording, it has been possible both to realize the strengths of the previous methods and significantly improve the weak stages of the previous methods, which in general gives a big gain in the time of minimization. The advantage of the method is two-stage minimization of the process, which makes it possible not to use the directed sorting criterion directly. When forming a complete list of elements, the elements of the final answer are immediately obtained without specifying intermediate results. Structural elements of the method – a complete set of possible elements of the final answer for Boolean functions, containing one number of arguments for the value of the basic coefficient K=1...n, are formed even before the beginning of the execution of the method. and are used as a table value. When implementing the method, only units without zeros are processed in the columns of the truth table, which reduces the number of processing objects. The method is implemented by two-level column processing – checking necessary and sufficient conditions. The machine implementation of the method uses parallelization of the minimization process. All this significantly reduces the minimization time – the main value that distinguishes this method from others. The developed method of minimization is one of the constituent parts of the creation of the software code, which is the basis of the development of a fractal computer. The main feature of a fractal computer is the presence of fractal (non-smooth) functions in its software code, which will radically expand its capabilities in certain areas of computing. To date, none of modern computers uses these functions in the program code
Keywords
method of minimization of Boolean functions; matrix method of parallel decomposition; resulting lines of Boolean function; parallelization of minimization process; basic coefficient K; fractal computer
References
[1] E. McCluskey, "Minimization of Boolean functions", The Bell System Technical Journal, vol. 35, pp. 1417-1444, Nov. 1956.
[2] W. Quine, "The problem of simplifying truth functions", American Mathematical Monthly, vol. 59, pp. 521-531, 1952.
[3] C. E. Shannon, "A mathematical theory of communication", Bell System Technical Journal, vol. 27, pp. 379-423, 623-656, 1948.
[4] Yu. A. Kochkaryev, N. M. Panteleeva, N. L. Kazarinova, and S. A. Shakun, Classical and alternative minimal forms of logical functions: Reference catalog. Cherkasy: Cherkasy Institute of Management, 1999 [in Ukrainian].
[5] O. P. Pinko, "Minimization of CNF of partially monotone Boolean functions", Dopovidi Natsionalnoi akademii nauk Ukrainy, no. 3, pp. 18-21, 2019 [in Ukrainian].
[6] V. Riznyk, and M. Solomko, "Research of 5-bit boolean functions minimization protocols by combinatorian method", Technology Audit and Production Reserves, vol. 4, iss. 2 (42), pp. 41-52, 2018.
[7]
I. P. Chukhrov, "On the minimization of Boolean functions for additive complexity measures", Journal of Applied and Industrial Mathematics, vol. 13, pp. 418-435, 2019.
[8] V. Riznyk, and M. Solomko, "Minimization of Boolean functions by combinatorial method", Technology Audit and Production Reserves, vol. 4, no. 2 (36), pp. 49-64, 2017.
[9] I. P. Chukhrov, "On the complexity of minimizing quasicyclic Boolean functions", Diskretn. Anal. Issled., Open 25 (3), pp. 126-151, 2018 [J. Appl. Indust. Math., vol. 12, pp. 426-441, 2018].
[10] Yu. A. Kochkarev, S. V. Burmistrov, and S. F. Aksyonov, "Minimization of Boolean functions by parts", Radioelektronni ta kompiuterni systemy, no. 4, pp. 110-116, 2012 [in Ukrainian].
[11] Yu. A. Kochkarev, S. V. Burmistrov, and S. F. Aksyonov, "Minimization of partially defined Boolean functions in the orthogonal form of representation", Prykladna radioelektronika, vol. 12, no. 3, pp. 413-420, 2013 [in Ukrainian].
[12] Yu. A. Kochkarev, V. N. Rudnytskyi, and S. V. Burmistrov, Minimization of systems of fully defined Boolean functions in the orthogonal form of representation. Heuristic algorithms and distributed computing in applied problems: Coll. monograph, Prof. Melnikov (Ed.), iss. 2. Vinnitsa, Kharkiv, 2013, pp. 87-100 [in Ukrainian].
[13] S. V. Burmistrov, "Parallel decomposition as the main method of minimizing Boolean functions in the orthogonal form of representation", Visnyk Cherkaskoho derzhavnoho tekhnolohichnoho universytetu, no. 2, pp. 67-73, 2014 [in Ukrainian].
[14] S. V. Burmistrov, and E. N. Panasco, "Parallel decomposition by reducing the value of the basic coefficient K as an alternative method of minimizing Boolean functions", Visnyk Pryazovskoho derzhavnoho tekhnichnoho universytetu. Seriia: Tekhnichni nauky, no. 1, pp. 189-195, 2015 [in Ukrainian].
[15] S. V. Burmistrov, and O. B. Piven, "The matrix method of parallel decomposition as a generalized method of minimization in the orthogonal form of representation", Nauka i tekhnika Povitrianykh Syl Zbroinykh Syl Ukrainy, no. 4 (21), pp. 151-157, 2015 [in Ukrainian].