An optimization of AND-OR-EXOR three-level networks

Author

Debnath, Debatosh ; Sasao, Tsutomu

Author_Institution

Dept. of Comput. Sci. & Electron., Kyushu Inst. of Technol., Iizuka, Japan

fYear

1997

fDate

28-31 Jan 1997

Firstpage

545

Lastpage

550

Abstract

Presents a design method for AND-OR-EXOR three-level networks, where a single two-input EXOR gate is used. The network realizes an exclusive-OR of two sum-of-products expressions (EX-SOP), where the two sum-of-products expressions (SOPs) cannot share products. The problem is to minimize the total number of products in the two SOPs. We introduced the μ-equivalence of logic functions to develop minimization algorithms for EX-SOPs with up to five variables. We minimized all the representative functions of NP-equivalence classes for up to five variables and found that five-variable functions require up to nine products in minimum EX-SOPs. For n-variable functions, minimum EX-SOPs require at most 9·2^n-5 (n⩾6) products. This upper bound is smaller than 2^n-1, the upper bound for conventional SOPs

Keywords

circuit optimisation; computational complexity; functions; logic design; logic gates; minimisation of switching nets; μ-equivalence; 5-variable functions; AND-OR-EXOR 3-level network optimization; NP-equivalence classes; complexity; coordinate representation; design method; exclusive-OR; logic functions; logic minimization; minimum EX-SOPs; product number minimization algorithms; representative functions; spectral method; sum-of-products expressions; two-input EXOR gate; upper bound; Arithmetic; Circuits; Computer science; Design methodology; Instruments; Logic design; Logic functions; Minimization methods; Programmable logic arrays; Upper bound;

fLanguage

English

Publisher

ieee

Conference_Titel

Design Automation Conference, 1997. Proceedings of the ASP-DAC '97 Asia and South Pacific

Conference_Location

Chiba

Print_ISBN

0-7803-3662-3

Type

conf

DOI

10.1109/ASPDAC.1997.600332

Filename

600332