GENERALIZED REED-MULLER EXPRESSIONS - COMPLEXITY AND AN EXACT MINIMIZATION ALGORITHM

A generalized Reed-Muller expression (GRM) is obtained by negating som e of the literals in a positive polarity Reed-Muller expression (PPRM) . There are at most 2(n2n-I) different GRMs for an n-variable function . A minimum GRM is one with the fewest products. This paper presents c ertain properties and an exact minimization algorithm for GRMs. The mi nimization algorithm uses binary decision diagrams. Up to five variabl es, all the representative functions of NP-equivalence classes were ge nerated and minimized. Tables compare the number of products necessary to represent four- and five-variable functions for four classes of ex pressions: PPRMs, FPRMs, GRMs and SOPs. GRMs require, on the average, fewer products than sum-of-products expressions (SOPs), and have easil y testable realizations.