Multiple-valued logic networks with regular structure obtained from fast Fourier transforms on finite groups

Abstract

In this paper, we discuss the Fast Fourier transform (FFT) on finite groups as a useful method in synthesis for regularity. FFT is the algorithm for efficient calculation of the Discrete Fourier transform (DFT) and has been extended to computation of various Fourier-like transforms. The algorithm has a very regular structure that can be easily mapped to technology by replacing nodes in the corresponding flow-graphs by circuit modules performing the operations in the flow-graphs. In this way, networks with highly regular structure for implementing functions from their spectra are derived. Fourier transforms on non-Abelian groups offer additional advantages for reducing the required hardware due to matrix-valued spectral coefficients and the way how such coefficients are used in reconstructing the functions. Methods for optimization of spectral representations of functions on finite groups may be applied to improve networks with regular structure.