New methods to find optimal non-disjoint bi-decompositions
Shigeru Yamashita, Hiroshi Sawada, Akihiro Nagoya · 2002
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=/spl alpha/(g/sub 1/(X/sup 1/),g/sub 2/(X/sup 2/)) where the total number of variables in X/sup 1/ and X/sup 2/ is the smallest among all bi-decomposition forms of f. We consider two methods; one's decomposition form is (g/sub 1//spl middot/g/sub 2/) and the other's is (g/sub 1//spl oplus/g/sub 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.