New Methods to Find Optimal Non-Disjoint Bi-Decompositions

Shigeru Yamashita, Hiroshi Sawada, Akira Nagoya

Abstract

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.
BibTeX
@inproceedings{yamashita1998new,
  author = {Shigeru Yamashita and Hiroshi Sawada and Akira Nagoya},
  title = {{New Methods to Find Optimal Non-Disjoint Bi-Decompositions}},
  booktitle = {ASP-DAC},
  year = {1998},
  doi = {10.1109/aspdac.1998.669399},
}

Loading related content...

Figure