Method for Construction of Recursive Algorithms for Reed-Muller-Fourier Polarity Matrices Calculation
Dragan Jankovic and Rolf Dreschler
It has been shown that representation of some classes of MV functions by means of Reed-Muller-Fourier (RMF) expressions has several advantages in comparison to Galois Field (GF) representations [13]. Optimisation of RMF-expressions is possible by using different polarities for variables. But so far, no algorithms have been presented for the minimization of RMFs – neither optimal nor heuristic approaches. A straightforward approach – as for GF-expressions – for optimisation of RMF-expressions would be to calculate all possible fixed polarity RMF-expressions (FPRMFE) and select the expression with the minimum number of nonzero coefficients. The coefficients of all FPRMFE can be represented as a RMF polarity matrix corresponding to the GF-polarity matrices used in optimisation of GF-expressions. In this paper, we present a method to construct recursive matrix algorithms for the RMF polarity matrices calculation. As an example of application of the proposed method, we present efficient recursive algorithms for the construction of the RMF polarity matrix for a given n-variable quaternary function. The efficiency of the algorithms is estimated through the number of calculations required to compute the polarity matrix. In these algorithms, polarities for variable used in optimisation of GF-expressions are considered. Unlike GF-expression optimisation, for RMF-expression optimisation an extended set of variable polarities can be used. The proposed method, by a slight modification of its first step, can also be applied for the generation of a recursive algorithm for the construction of the extended RMF polarity matrix.