A multiplier-less 1-D and 2-D fast Fourier transform-like transformation using sum-of-powers-of-two (SOPOT) coefficients

This paper proposes a new multiplier-less approximation of the 1D discrete Fourier transform (DFT) called the multiplierless fast Fourier transform-like (ML-FFT) transformation. It parameterizes the twiddle factors in conventional radix-2ⁿ or split-radix FFT algorithms as certain rotation-like matrices and approximates the associated parameters using the sum-of-powers-of-two (SOPOT) or canonical signed digits (CSD) representations. The ML-FFT converges to the DFT when the number of SOPOT terms used increases and has an arithmetic complexity of O(Nlog₂ N) additions, where N=2^m is the transform length. Design results show that the ML-FFT offers flexible tradeoff between arithmetic complexity and numerical accuracy in approximating the DFT. Using the polynomial transformation, similar multiplier-less approximation of 2D FFT is also obtained.