GRMIN2 - A HEURISTIC SIMPLIFICATION ALGORITHM FOR GENERALIZED REED-MULLER EXPRESSIONS

A generalised Reed-Muller expression (GRM) is a class of AND-EXOR expr ession. In a GRM, each variable may appear both complemented and uncom plemented. Networks realised using GRMs are easily tested. The paper p resents GRMIN2, a heuristic simplification algorithm for GRMs of multi ple-output functions. GRMIN2 uses eight rules, and as the primary obje ctive, it reduces the number of products, and as the secondary objecti ve, it reduces the number of literals. GRMIN2 obtains a lower bound on the number of products in GRMs and often proves the minimality of the solutions. Experimental results show that in most cases GRMs require fewer products than conventional sum-of-products expressions. GRMIN2 o utperforms existing algorithms and for many functions it proved the mi nimalities of the solutions.