The search functionality is under construction.
The search functionality is under construction.

An Efficient Method for Finding an Optimal Bi-Decomposition

Shigeru YAMASHITA, Hiroshi SAWADA, Akira NAGOYA

  • Full Text Views

    0

  • Cite this

Summary :

This paper presents a new efficient method for finding an "optimal" bi-decomposition form of a logic function. A bi-decomposition form of a logic function is the form: f(X) = α(g1(X1), g2(X2)). We call a bi-decomposition form optimal when the total number of variables in X1 and X2 is the smallest among all bi-decomposition forms of f. This meaning of optimal is adequate especially for the synthesis of LUT (Look-Up Table) networks where the number of function inputs is important for the implementation. In our method, we consider only two bi-decomposition forms; (g1 g2) and (g1 g2). We can easily find all the other types of bi-decomposition forms from the above two decomposition forms. Our method efficiently finds one of the existing optimal bi-decomposition forms based on a branch-and-bound algorithm. Moreover, our method can also decompose incompletely specified functions. Experimental results show that we can construct better networks by using optimal bi-decompositions than by using conventional decompositions.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E81-A No.12 pp.2529-2537
Publication Date
1998/12/25
Publicized
Online ISSN
DOI
Type of Manuscript
Special Section PAPER (Special Section on VLSI Design and CAD Algorithms)
Category
Logic Synthesis

Authors

Keyword