New methods to find optimal non-disjoint bi-decompositions

This paper presents new efficient methods to find "optimal bi-decomposition" forms of logic functions. An "optimal bi-decomposition" form of f(X) is f = alpha(g(1)(X-1),g(2)(X-2)) where the total number of variables in X-1 and X-2 is the smallest among all bi-decomposition forms of f. We consider two methods; one's decomposition form is (g(1).g(2)) and the other's is (g(1)+g(2)). The proposed methods can find one of the existing "optimal" decomposition forms efficiently based on the Branch-and-Bound algorithm. These methods can decompose incompletely specified functions. Preliminary experimental results show that the proposed methods can construct networks with fewer levels than conventional methods.