Fixed Polarity Linearly Independent Expansions for the Representation of Quaternary Functions
Cicilia C. Lozano, Bogdan J. Falkowski and Tadeusz Luba
A polynomial expansion based on a fixed polarity quaternary linearly independent (FPQLI) transform is presented. The FPQLI transforms built from six recursive basic transforms whose structures are directly derived from some linearly independent transforms over Galois Field(2) (GF(2)). For certain polarities the FPQLI transform for n-variable quaternary functions directly corresponds to the binary fixed polarity Reed-Muller (FPRM) transforms for 2n-variable binary functions. Due to the way the FPQLI transform for n >1 is constructed, the transform is inherently recursive and has a regular structure. Recursive equations, fast flow graph, and underlying basis functions for the transform are given. In addition, relations between different FPQLI spectral coefficient vectors are shown and applied to reduce the computational cost of obtaining the optimal FPQLI expansion. Experimental results of the FPQLI transform have been obtained for a set of quaternary test files. The results show that for the test files, the average number of nonzero spectral coefficients of optimal FPQLI transform is 39.05% smaller than the number for optimal FPRM over GF(4).
Keywords: Linearly independent transforms, Quaternary switching functions, Multiple-valued logic, Spectral techniques, Transforms over GF(4), Fast transform, Discrete transforms.