50 Years of FFT Algorithms and Applications

Abstract

The fast Fourier transform (FFT) algorithm was developed by Cooley and Tukey in 1965. It could reduce the computational complexity of discrete Fourier transform significantly from \[O(N^2)\] to \[O(N\log _2 {N})\]. The invention of FFT is considered as a landmark development in the field of digital signal processing (DSP), since it could expedite the DSP algorithms significantly such that real-time digital signal processing could be possible. During the past 50 years, many researchers have contributed to the advancements in the FFT algorithm to make it faster and more efficient in order to match with the requirements of various applications. In this article, we present a brief overview of the key developments in FFT algorithms along with some popular applications in speech and image processing, signal analysis, and communication systems.