New methods to find optimal non-disjoint bi-decompositions

Shigeru Yamashita, Hiroshi Sawada, Akira Nagoya

Research output: Contribution to conferencePaperpeer-review

17 Citations (Scopus)


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 = α(g1(X1), g2(X2)) where the total number of variables in X1 and X2 is the smallest among all bi-decomposition forms of f. We consider two methods; one's decomposition form is (g1·g2) and the other's is (g1⊕g2). 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.

Original languageEnglish
Number of pages10
Publication statusPublished - Dec 1 1998
Externally publishedYes
EventProceedings of the 1998 3rd Conference of the Asia and South Pacific Design Automation (ASP-DAC '98) - Yokohama, Jpn
Duration: Feb 10 1998Feb 13 1998


OtherProceedings of the 1998 3rd Conference of the Asia and South Pacific Design Automation (ASP-DAC '98)
CityYokohama, Jpn

ASJC Scopus subject areas

  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering


Dive into the research topics of 'New methods to find optimal non-disjoint bi-decompositions'. Together they form a unique fingerprint.

Cite this