Exact minimisation of large multiple output FPRM functions

The properties of the polarity for sum-of-products (SOP) expressions of Boolean functions are formally investigated. A transform matrix S is developed to convert SOP expressions from one polarity to another polarity. It is shown that the effect of SOP polarity is to reorder the on-set minterms of a Boolean function. Furthermore, the transform matrix P for fixed polarity Reed-Muller (FPRM) expressions for the conversion between two different polarities, based on the properties of SOP polarity, is achieved. Comparison of these two matrices shows that the Reed-Muller transform matrix P has a much more complex structure. Additionally, the best polarity of FPRM forms with the least on-set terms corresponds with the polarity of SOP forms with the best ‘order’ of the on-set minterms. Applying these algebraic properties of the transform matrix P, a fast algorithm is presented to obtain the best polarity of FPRM expressions for large multiple output Boolean functions. The computation time is independent of the number of outputs. The developed program is tested on common personal computers and the results for benchmark examples of up to 25 inputs and 29 outputs are presented.