Low-complexity synthesis of incompletely specified multiple-output mod-2 sums

A new method for (quasi) minimisation of incompletely specified multiple-output mod-2 sum expressions is presented. It uses a new low-complexity algorithm for the Reed-Muller transform (RMT). Heuristically choosing a (quasi-)optimal polarity of the transform, its coefficients are combined so as to form a locally disjoint RM coefficient cover. Inverse RMT yields a (quasi)minimal exclusive-OR sum of products. To exploit common product terms, multiple-output functions are combined to form a single-output hyperfunction. ´don´t cares´ are (quasi-)optimally allotted during the procedure. Since throughout the algorithm only cubes are to be handled, the method is fast and requires only moderate storage. It compares favourably with other algorithms both in the average number of products required and in its computational complexity. The program HEALEX can handle functions of hundreds of variables on an AT personal computer.