Fast Fourier Transforms on Finite Groups as a Method in Synthesis for Regularity

摘要

FFT was defined as the algorithm for efficient calculation of the Discrete Fourier transform (DFT), however, it has been extended to computation of Fourier transforms on different groups in abstract harmonic analysis and also various Fourier-like transforms often met in computing. The algorithm has a very regular structure that is obvious from its flow-graph and the same applies to the related algorithms for computing the inverse transforms, i.e., reconstructing functions from their spectra. In this paper, we discuss the Fast Fourier transform (FFT) on finite groups as a useful method in synthesis for regularity. These algorithms 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.