A New Fast Discrete Fourier Transform

This paper presents a new fast Discrete Fourier Transform (DFT) algorithm. By rewriting the DFT, a new algorithm is obtained that uses 2n−2(3n−13)+4n−2 real multiplications and 2n−2(7n−29)+6n+2 real additions for a real data N=2n point DFT, comparable to the number of operations in the Split-Radix method, but with slightly fewer multiply and add operations in total. Because of the organization of multiplications as plane rotations in this DFT algorithm, it is possible to apply a pipelined CORDIC algorithm in a hardware implementation of a long-point DFT, e.g., at a 100 MHz input rate, a 1024-point transform can be realized with a 200 MHz clocking of a single CORDIC pipeline.