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

Abstract

This paper proposes a new multiplier-less approximation of the 1-D Discrete Fourier Transform (DFT) called the multiplier-less Fast Fourier Transform-like (ML-FFT) transformation. It parameterizes the twiddle factors in conventional radix-2n 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(Nlog2N) additions, where N = 2m 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 2-D FFT is also obtained.