GRMIN2: A heuristic simplification algorithm for generalised Reed–Muller expressions

Abstract

A generalised Reed–Muller expression (GRM) is a class of AND-EXOR expression. In a GRM, each variable may appear both complemented and uncomplemented. Networks realised using GRMs are easily tested. The paper presents GRMIN2, a heuristic simplification algorithm for GRMs of multiple-output functions. GRMIN2 uses eight rules, and as the primary objective, it reduces the number of products, and as the secondary objective, 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 outperforms existing algorithms and for many functions it proved the minimalities of the solutions.