Parallel decomposition of a system of partial boolean functions

The problem of Boolean functions decomposition is to represent a given system of Boolean functions as a superposition of simpler Boolean functions. In fact, the implementation of a system of Boolean functions by logical unites, or the synthesis of a combinational circuit, is reduced to decomposition, in which the obtained superposition includes functions implemented by logical unites. The decomposition problem is considered in the following statement. Given a system of partial (incompletely specified) Boolean functions in the vector form, f(x) = (fi(x),fi(x), ...,fn(x)), where the components of the vector x = (xi, x2, ..., xn) are Boolean variables forming a set X. A superposition fx) < 9(gi(zi), g2(Z2), ..gk(zk)) must be found, where the components of the vector Zi, i = i, 2, ..k, are the variable in the set Zi сX and < denotes the realization relation, i.e., the values of the components of the vector function ф coincide with the values of the components of f everywhere they are specified. At that, the cardinality |Zi|, i = i, 2, k, must be restricted by a given value p, and k must be minimum and less than n. An approach to solving the problem that does not demand the sets Zi, Z2, Zk to be given is described. The approach uses the interval representation of a system of partial Boolean functions, i.e., in the form of a pair of ternary matrices, X, F, of dimension l x n and l x m, respectively. The columns of the matrix X correspond to the values xi, x2, ..., xn, and the columns of the matrix Fto the functionsfi(x),fi(x), ...,fn(x). A row of X gives an interval of Boolean space, and the corresponding row of F the function values at this interval. The symbol "-" in the i-th row and j-th column of F means that the i-th interval is not used to specify the function f(x). The rows of X and F have common numeration. The graphs Gx = (V, Ex) and Gf = (V, Ef) are considered, where V is the set of common numbers of rows of the matrices X and F, and Ex and Ef are the sets of pairs of orthogonal rows of the matrices X and F, respectively. A system of Boolean functions is given with matrices X and F correctly if Ef с Ex, i.e., Gf is a spanned subgraph of Gx. Every edge in Ex is assigned with the variables from the setХ = {xi, x2, ..., xn}, according to which the corresponding rows ofX are orthogonal. A complete bipartite subgraph (biclique) of Gx is assigned with the set of variables in X taken one by one from each edge of the biclique. A biclique is called admissible if the number of variables assigned to it is at most p, and it contains at least one edge in Ef. Let Bi, B2, ..., Bk be bicliques covering the set Ef. Any biclique Bi can be given by a pair of vertex sets (V/, Vi"). Every function gi(Zi) of the required superposition is specified by matrices Xi and Fi. The matrix Xi is the minor of X formed by the columns corresponding to the variables assigned to the biclique Bi. The matrix Fi consists of one column, where the element with number corresponding to the vertex in Vi'is 0, and the element with number corresponding to the vertex in Vi"is i (or vice versa). The element that does not correspond to any vertex in Vi'or in Vi "is "-". The vector function ф is given by matrices U and Ф. The matrix U consists of the columns that are the one-column matrices Fi, F2, Fk, and the matrix Ф coincide with F. Two methods for the considered problem are presented. The first method obtains an exact solution, i.e., the minimal number of blocks in a structural implementation of the given system of functions is ensured. This method is reduced to that first all maximal admissible bicliques are found in graph Gx, and then a shortest cover with them of the edges in Ef is obtained. The second method is heuristic one, it does not guarantee the minimal solution, but it allows solving the problem much faster in comparison with the first one. This method forms bicliques successively, that constitute a cover of the edges of graph Gf finally. The exact method can serve as a basis for developing other, heuristic methods, more applicable for practical tasks. The second method from the described ones is one of them. Moreover, the exact method can be used as an etalon for estimating the quality of solutions obtained by heuristic methods. The quality of the solution must be understood as its closeness to the optimal solution and simplicity of the obtained functions.

Keywords

Authors

References