METHOD FOR MINIMIZATION OF BOOLEAN FUNCTIONS WITH A LARGE NUMBER OF VARIABLES BASED ON DIRECTED ENUMERATION
DOI:
https://doi.org/10.24025/2306-4412.1.2023.274914Keywords:
method of minimization, Boolean functions, set of function values, directed enumerationAbstract
The development of computer technology directly depends on the development of methods for synthesizing components of digital computer technology, therefore the automation of the process is observed in the development of microcircuits. Boolean algebra is widely used for the synthesis of circuit models, and one of the problems in this case is the dependence of the complexity of implementing a given circuit on the number of variables of the Boolean function that implements it. Based on this, it can be argued that the increase in the number of variables in the functions that require minimization requires the search for new or improvement of existing methods of minimization of Boolean functions, which will be easy to use, descriptive and have the ability to automate the implementation of the minimization process. The task of developing effective methods of minimization of Boolean functions for simulation of circuits with linear and polynomial dependence of simulation speed on the number of variables of the implemented Boolean function remains relevant. The object of research is the process of minimization of Boolean functions, which are used in the construction of circuits of digital automata. The purpose of this work is practical implementation of the method of minimization of Boolean functions based on directed enumeration when increasing the number of variables. The objective considered in this work is to develop and implement the method of minimization of Boolean functions, which will help to minimize Boolean functions based on directed enumeration, the bitness of which exceeds ten variables, as well as to increase the efficiency of search when bonding implicants with a large uncertainty in the sets of functions. Since all existing methods of minimization face the problem of cumbersome calculations when the number of variables increases, the method of directed enumeration, which is quite effective in the case of large uncertainty in the sets, has been chosen for the study. Based on the calculations, it has been determined that this method of minimization of Boolean functions is efficient and easy to use. Its main advantage is the possibility of implementation by means of computer technology, and directed enumeration as the basis can reduce the requirements for hardware and software resources of automated design systems.
References
V. H. Babenko, "A method of increasing the speed of information protection systems based on the use of specialized logical functions", Ph. D. thesis: 05.13.21, Cherkasy, 2009 [in Ukrainian].
IT journal of articles. [Online]. Available: https://www.tutorialspoint.com/automata_theory/dfa_minimization.htm [in Ukrainian].
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].
Yu. A. Kochkarev, I. I. Osipenkova, and E. N. Panasko, "Ortogonal forms of presentation of Boolean functions in device blocks", Visnyk Cherkaskogo derzhavnogo tekhnolohichnogo universytetu, special issue, pp. 39-42, 2009.
V. F. Senchukov, and T. V. Denysova, "Minimization of Boolean functions by numbers of argument value sets", Otkrytyie informatsionnyie i kompiuternyie integrirovannyie tekhnologiyi: sci. papers, Kharkiv: Nats. aerokosm. un-t "KhAI", iss. 83, pp. 156-167, 2019 [in Ukrainian].
V. F. Senchukov, and T. V. Denysova, "vminimization of Boolean functions by distance matrix and reduction to a mathematical programming problem", Vidkryti informatsiini ta kompiuterni intehrovani tekhnolohii: coll. of sci. papers, Kharkiv: Nats. aerokosm. un-t "KhAI", iss. 88, pp. 123-133, 2020 [in Ukrainian]. doi: 10.32620/oikit.2020.88.10.
Kh. Faraj, "Design error detection and correction system based on Reed-Muller matrix for memory protection", Inter. J. of Computer Applications (0975-8887), vol. 34, no. 8, pp. 42-55, Nov., 2011. [Online]. Available: https://www.ijcaonline.org/archives/volume34/number8/4123-5929. doi: 10.5120/4123-5929.
M. T. Solomko, "Minimization of Boolean functions in polynomial and mixed bases by the method of image transformations", in Twenty-third Int. Sci. and Pract. Seminar Combinatorial Configurations and Their Applications, Zaporizhzhia-Kropyvnytskyi, May 13-15, 2021, pp. 168-174. [Online]. Available: https://zp.edu.ua/uploads/dept_s&r/2021/conf/1.4/Petrenyuk_ISPS-23-proc.pdf [in Ukrainian].
V. Riznyk, and M. Solomko, "Research of 5-bit Boolean functions minimization protocols by combinatorial method", Technology Audit and Production Reserves, vol. 4 (2 (42)), pp. 41-52, 2018. [Online]. Available: https://doi.org/10.15587/2312-8372.2018.140351
Yu. A. Kochkarev, S. V. Burmistrov, and S. F. Aksenov, "Minimization of partially defined Boolean functions in an orthogonal form of representation", Prikladnaya radioelektronika, vol. 12, no. 3, pp. 423-430, 2013. [Online]. Available: http://nbuv.gov.ua/UJRN/Prre_2013_12_3_8 [in Russian].
Yu. A. Kochkarev, S. V. Burmistrov, and S. F. Aksenov, "Minimization of Boolean functions by parts", Radioelektronni i kompiuterni systemy, no. 4, pp. 110-115, 2012. [Online]. Available: http://nbuv.gov.ua/UJRN/recs_2012_4_18 [in Russian].
S. V. Burmistrov, "Parallel decomposition as the main method of minimizing Boolean functions in an orthogonal form of representation", Visnyk Cherkaskogo derzhavnogo tekhnolohichnogo universytetu, no. 2, pp. 67-73, 2014 [in Ukrainian].
S. V. Burmistrov, O. M. Panasco, and N. V. Kovalska, "A matrix method of parallel decomposition for the minimization of symmetric Boolean functions in the form of an extended polynomial", Visnyk Cherkaskogo derzhavnogo tekhnolohichnogo universytetu, no. 1, pp. 130-135, 2018. [Online]. Available: https://doi.org/10.24025/2306-4412.1.2018.162604 [in Ukrainian].
T. V. Myronyuk, S. V. Sysoenko, V. G. Babenko et al., Information Protection Based on Information-Driven Permutation Operations: monograph, Cherkasy State Technol. Univ. Cherkasy, Ukraine: publisher Ye. I. Hordienko, 2021, pp. 103-164 [in Ukrainian]. ISBN 978-966-97302-2-0.
S. G. Semenov, and I. V. Myronets, "Improvement of the method of minimization of Boolean functions under the condition of information redundancy", Systemy upravlinnia, navihatsii ta zviazku, iss. 3 (35), pp. 92-99, Poltava: PNTU, 2015 [in Ukrainian].
Downloads
Published
How to Cite
Issue
Section
URN
License
Copyright (c) 2023 Антон Андрійович Сисоєнко, Світлана Володимирівна Сисоєнко
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
The authors who publish in this journal agree to the following terms:The authors reserve the right to authorship of their work and give the journal the right to first publish this work under the terms of the Creative Commons Attribution License CC BY-NC, which allows other persons to freely distribute published work with a mandatory reference to authors of the original work and the first publication of the work in this journal.
Authors have the right to conclude separate additional agreements for the non-exclusive distribution of the paper in the form in which it was published by this journal (for example, posting work in electronic repository or publishing as part of a monograph), provided that the link to the first publication in this journal is maintained.
The journal policy allows and encourages authors to post on the Internet (for example, in repositories of institutions or on personal websites) the manuscript of work, both before the submission of this manuscript to the editorial staff, and during its editorial work, as it contributes to the emergence of productive scientific discussion and positively affects the efficiency and dynamics of published work citation (see The Effect of Open Access).
