Fast Fourier transform algorithms based on binary trees representation
Speaker(s) : Fahad Qureshi (Tampere University of Technology)
The Fast Fourier Transform (FFT) is a fundamentally important algorithm that reduces the cost of the Discrete Fourier Transform (DFT) from O(n2) to O (n log n) which is proposed by Cooley & Tukey in 1965. This talk presents a systematic method to generate the fast Fourier transform (FFT) algorithms based on binary tree representation. This representation in more general and it introduces number of new FFT algorithms. The binary tree has the advantage that it is simple and easy to understand. Besides, this allows for obtaining the exact twiddle factor values in FFT flow graph easily, which facilitates the design of FFT architecture. As a results, it opens new possibilities in the research of the FFT.
These FFT algorithms have identical butterfly operations and data flow but differ in the value of the rotations. Their analysis shows the impact on the power consumption, area, and the accuracy of the architecture.
Marc.Mezzarobba (at) nulllip6.fr