Efficient algorithm to calculate Reed–Muller expansions over GF(4)
Susanto Rahardja, B.J. Falkowski · IEE Proceedings - Circuits Devices and Systems · 2001
A new algorithm to generate the full polarity matrix of fixed polarity Reed–Muller expansions over Galois fields of order 4, GF(4), has been developed. By using directly the truth vector of the original function, a recursive formula is developed to generate the whole polarity matrix. The algorithm uses the properties of the fixed polarity matrix to speed up the calculation and reduce the number of necessary multipliers and adders. The computational complexity of the algorithm is compared with other works. It is shown that, for practical hardware implementations of quaternary functions, the new algorithm is better than all other existing algorithms. The fast flow diagrams for computation of the whole or partial matrix are also presented.