An efficient multiplierless approximation of the fast Fourier transform using sum-of-powers-of-two (SOPOT) coefficients

摘要

This letter proposes a new multiplierless approximation of the discrete Fourier transform (DFT) called the multiplierless fast Fourier transform-like (ML-FFT) transformation. It makes use of a novel factorization to parameterize the twiddle factors in the conventional radix-2/sup n/ 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(N log/sub 2/ N) additions, where N = 2/sup m/ is the transform length. Design results show that the NM-FFT offers flexible tradeoff between arithmetic complexity and numerical accuracy in approximating the DFT.