Reed-Muller tree-based minimisation of fixed polarity Reed-Muller expansions

A heuristic method for the determination of optimum or near-optimum fixed p olarity Reed-Muller (FPRM) representation of multiple output, completely sp ecified Boolean systems is presented. The Reed-Muller (RM) tree representat ion forms the conceptual framework for the method, which involves manipulat ions of arrays of cubes. A coding method that is well adapted to RM tree re presentation is presented. The minimisation method takes as input a disjoin t sum of cubes representation of the Boolean system. Using Karpovsky's comp lexity estimates as the basis for polarity selection, the method obtains th e FPRM expansion by generating in one run an optimum or near optimum Reed-M uller tree representation.