New methods to find optimal non-disjoint bi-decompositions

Shigeru Yamashita; Hiroshi Sawada; Akira Nagoya

New methods to find optimal non-disjoint bi-decompositions

Shigeru Yamashita, Hiroshi Sawada, Akira Nagoya

Research output: Contribution to conference › Paper › peer-review

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 = α(g₁(X¹), g₂(X²)) where the total number of variables in X¹ and X² is the smallest among all bi-decomposition forms of f. We consider two methods; one's decomposition form is (g₁·g₂) and the other's is (g₁⊕g₂). 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 language	English
Pages	59-68
Number of pages	10
Publication status	Published - Dec 1 1998
Externally published	Yes
Event	Proceedings of the 1998 3rd Conference of the Asia and South Pacific Design Automation (ASP-DAC '98) - Yokohama, Jpn Duration: Feb 10 1998 → Feb 13 1998

Other

Other	Proceedings of the 1998 3rd Conference of the Asia and South Pacific Design Automation (ASP-DAC '98)
City	Yokohama, Jpn
Period	2/10/98 → 2/13/98

ASJC Scopus subject areas

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

Cite this

@conference{71f749b969254f22a5e5e1fcf5ded5c1,

title = "New methods to find optimal non-disjoint bi-decompositions",

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 = α(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.",

author = "Shigeru Yamashita and Hiroshi Sawada and Akira Nagoya",

year = "1998",

month = dec,

day = "1",

language = "English",

pages = "59--68",

note = "Proceedings of the 1998 3rd Conference of the Asia and South Pacific Design Automation (ASP-DAC '98) ; Conference date: 10-02-1998 Through 13-02-1998",

}

TY - CONF

T1 - New methods to find optimal non-disjoint bi-decompositions

AU - Yamashita, Shigeru

AU - Sawada, Hiroshi

AU - Nagoya, Akira

PY - 1998/12/1

Y1 - 1998/12/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0032218703&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0032218703&partnerID=8YFLogxK

M3 - Paper

AN - SCOPUS:0032218703

SP - 59

EP - 68

T2 - Proceedings of the 1998 3rd Conference of the Asia and South Pacific Design Automation (ASP-DAC '98)

Y2 - 10 February 1998 through 13 February 1998

ER -

New methods to find optimal non-disjoint bi-decompositions

Abstract

Other

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this