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 2(n-2)(3n - 13) + 4n - 2 real multiplications and 2(n-2)(7n - 29) + 6n + 2 real additions for a real data N = 2(n) point DFT, comparable to the number of operations in the Split-Radix method, but with slightly fewer multiply and add operati ons in total. Because of the organization of multiplications as plane rotat ions in this DFT algorithm, it is possible to apply a pipelined CORDIC algo rithm 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.