An exact minimization algorithm for generalized Reed-Muller expressions

Author

Sasao, Tsutomu ; Dednath, D.

Author_Institution

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

fYear

1994

fDate

5-8 Dec 1994

Firstpage

460

Lastpage

465

Abstract

A generalized Reed-Muller expression (GRM) is obtained by negating some of the literals in a positive polarity Reed-Muller expression (PPRM). There are at most 2^n2(n-1) different GRMs for an n-variable function. A minimum GRM is one with the fewest products. This paper presents certain properties and an exact minimization algorithm for GRMs. The minimization algorithm uses binary decision diagrams. Up to five variables, all the representative functions of NP-equivalence classes were generated, and minimized. A table compares the number of products necessary to represent 5-variable functions for 7 classes of expressions: FPRMs, KROs, PSDRMs, PSD-KROs, GRMs, ESOPs, and SOPs. GRMs require, on the average, fewer products than sum-of-products expressions and have easily testable realizations

Keywords

decision theory; logic design; minimisation; AND-EXOR logic design; ESOP; FPRM; GRM; KRO; NP-equivalence classes; PSD-KRO; PSDRM; SOP; binary decision diagram; generalized Reed-Muller expression; minimization algorithm; n-variable function; positive polarity Reed-Muller expression; sum-of-products expression; Adders; Circuit testing; Computer science; Logic design; Logic functions; Logic testing; Minimization methods;

fLanguage

English

Publisher

ieee

Conference_Titel

Circuits and Systems, 1994. APCCAS '94., 1994 IEEE Asia-Pacific Conference on

Conference_Location

Taipei

Print_ISBN

0-7803-2440-4

Type

conf

DOI

10.1109/APCCAS.1994.514594

Filename

514594