An efficient method for finding an optimal bi-decomposition

This paper presents a new efficient method for finding an "optimal" hi-deco mposition form of a logic function. A bi-decomposition form of a logic func tion is the form: f(X) = alpha(g(1)(X-1),g(2)(X-2)). We call a bi-decomposi tion form optimal when the total number of variables in X1 and X2 is the sm allest among all bi-decomposition forms of f. This meaning of optimal is ad equate especially for the synthesis of LUT (Look-Up Table) networks where t he number of function inputs is important for the implementation. In our me thod, we consider only two bi-decomposition forms; (g(1) . g(2)) and (g(1) circle plus g(2)). We can easily find all the other types of bi-decompositi on forms from the above two decomposition forms. Our method efficiently fin ds one of the existing optimal bi-decomposition forms based on a branch-and -bound algorithm. Moreover, our method can also decompose incompletely spec ified functions. Experimental results show that we can construct better net works by using optimal bi-decompositions than by using conventional decompo sitions.