An exact minimization algorithm for generalized Reed-Muller expressions

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/sup 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.