The search functionality is under construction.

The search functionality is under construction.

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*) = α(*g*_{1}(*X*^{1}), *g*_{2}(*X*^{2})). We call a bi-decomposition form optimal when the total number of variables in *X*^{1} and *X*^{2} 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; (*g*_{1} *g*_{2}) and (*g*_{1} *g*_{2}). 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

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

Copy

Shigeru YAMASHITA, Hiroshi SAWADA, Akira NAGOYA, "An Efficient Method for Finding an Optimal Bi-Decomposition" in IEICE TRANSACTIONS on Fundamentals,
vol. E81-A, no. 12, pp. 2529-2537, December 1998, doi: .

Abstract: 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*) = α(*g*_{1}(*X*^{1}), *g*_{2}(*X*^{2})). We call a bi-decomposition form optimal when the total number of variables in *X*^{1} and *X*^{2} 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; (*g*_{1} *g*_{2}) and (*g*_{1} *g*_{2}). 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.

URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e81-a_12_2529/_p

Copy

@ARTICLE{e81-a_12_2529,

author={Shigeru YAMASHITA, Hiroshi SAWADA, Akira NAGOYA, },

journal={IEICE TRANSACTIONS on Fundamentals},

title={An Efficient Method for Finding an Optimal Bi-Decomposition},

year={1998},

volume={E81-A},

number={12},

pages={2529-2537},

abstract={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*) = α(*g*_{1}(*X*^{1}), *g*_{2}(*X*^{2})). We call a bi-decomposition form optimal when the total number of variables in *X*^{1} and *X*^{2} 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; (*g*_{1} *g*_{2}) and (*g*_{1} *g*_{2}). 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.

keywords={},

doi={},

ISSN={},

month={December},}

Copy

TY - JOUR

TI - An Efficient Method for Finding an Optimal Bi-Decomposition

T2 - IEICE TRANSACTIONS on Fundamentals

SP - 2529

EP - 2537

AU - Shigeru YAMASHITA

AU - Hiroshi SAWADA

AU - Akira NAGOYA

PY - 1998

DO -

JO - IEICE TRANSACTIONS on Fundamentals

SN -

VL - E81-A

IS - 12

JA - IEICE TRANSACTIONS on Fundamentals

Y1 - December 1998

AB - 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*) = α(*g*_{1}(*X*^{1}), *g*_{2}(*X*^{2})). We call a bi-decomposition form optimal when the total number of variables in *X*^{1} and *X*^{2} 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; (*g*_{1} *g*_{2}) and (*g*_{1} *g*_{2}). 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.

ER -