A MUL TlPLIER-LESS I-D AND 2-D FAST FOURIER TRANSFORM-LIKE TRANSFORMATION USING SUM-OF-POWERS-OF­

This paper proposes a new mult iplier -less appro ximation of the I-D Discrete Fourier Transform (DFD called the multiplier­ less Fast Fourier Transform-like (ML-FFD transformation. It para meteri zes the twiddle factors in conventional radix- 2" or split-radix FFT algorithms as certain rotation-like matrices and approximates the associated parameters the sum-of­ powers-of-two (SOPOD or canonical signed digits (CSD) representations. The ML-FFT converges to the OFT when the number of SOPOT terms used increases and has an arithmetic complexity of O(Nlog, N) addi tions, where N = 2m is the transform length. Oesign results show that the ML-FFT offers flexible tradeoff between arithmetic complexity and numerical accuracy in approximating the DFT. Using the polyno mial transformation, similar multiplier-less approximation of 2-D FFT is also obtain ed.