A General Comparison Of FFT Algorithms

. Introduction: The first major breakthrough in implementation of Fast Fourier Transform (FFT), algorithms was the Cooley-Tukey [1] algorithm developed in the mid-1960s, which reduced the complexity of a Discrete Fourier Transform from O(N2), to O(N·logN), At that time, this was a substantial saving for even the simplest of applications. Since then, a large number of FFT algorithms have been developed. The Cooley-Tukey algorithm became known as the Radix- 2 algorithm and was shortly followed by the Radix-3, Radix-4, andMixed Radix algorithms [8].

Further research led to the Fast Hartley Transform (FHT), [2,3,4] and the Split Radix (SRFFT), [5] algorithms. Recently, two new algorithms have emerged: the Quick Fourier Transform (QFT), [6] and the Decimation-In-Time-Frequency (DITF), algorithm [7]. In this paper we provide a comparison of several contemporary FFT algorithms. The criteria used are the operations count, memory usage and computation time. We chose the following algorithms for our analysis: Radix-2 (RAD2),, Radix-4 (RAD4),, SRFFT, FHT, QFT and DITF.

 

For full details refer attachment