Parallel decomposition by reducing the value of the basic coefficient K as an alternative method minimization of Boolean functions

Steady improvement of microelectronics necessitates deeper understanding of existing methods for discrete structures synthesis, as well as development of new ones. Сombinational circuits of digital blocks are an important class of discrete structures, and Boolean functions are the mathematical models of their functioning. The purpose of this paper is to describe an alternative method of Boolean functions with a large number of arguments minimization. The method is implemented basing on the decomposition of Boolean functions through reducing the value of the basic factor K. Shannon’s decomposition of Boolean functions means Boolean functions decomposition into two summands with respect to some i-argument. The ratio between the number of arguments in informing and in the basic parts of each series member is determined by coefficient K. K is the number of arguments, which is part of the series member basis. The value of K is the criterion of minimizing of the logic equations of Boolean functions y=f(x1,x2,x3,…,xn). The basic factor K is optimal if its informing part value is equal to Qi=1 or Qi=0. Decomposition of Boolean functions does not always result in the minimal form of Boolean functions. It provides a consistent decomposition of Boolean functions, and arguments are essentially equal. Therefore a method of parallel decomposition is proposed in this article. This method is based on decomposition of Boolean functions by simultaneous changes in all the arguments of the basic factor K. Parallel decomposition process consists of two stages. In the first stage, the full list of all the basic parts -Φi with the optimal value of the basic factor K are determined. In the second stage on the basis of Φi complete list of answers is formed. The paper provides a detailed description of the parallel decomposition algorithm for the minimization. Parallelization of the minimization process accelerates the whole process. The software for the minimization of Boolean functions with a large number of arguments on the basis of the described algorithm has been developed. Parallelization process, which is offered for the longest stages of the minimization process makes it possible to obtain minimal forms of Boolean functions by utilizing multiprocessor systems in a relatively short period of time. This has a positive effect on the speed of the digital blocks logical design