Evaluation of m-valued fixed polarity generalizations of Reed-Muller canonical form
E. Dubriva · 2003
This paper compares the complexity of three different fixed polarity generalizations of Reed-Muller canonical form to multiple-valued logic. The Galois field-based expansion introduced by D.H. Green and I.S. Taylor (1974), the Reed-Muller-Fourier form of R.S. Stankovic and C. Moraga (1998), and the expansion over addition modulo m, minimum and the set of all literal operators introduced by the author and Muzio. An algorithm for computing the minimal canonical forms for these generalizations is implemented and applied to a set of encoded 4-valued benchmark functions, 3- and 4-valued adders and multipliers. The experimental results show that, for the benchmark functions, the Reed-Muller-Fourier form and our expansion yield a comparable number of products on average. They have 40% less products on average than the expansion of Green and Taylor. The Reed-Muller-Fourier form gives a compact representation for adders, while our expansion seems to be suitable for multipliers.