Fast fourier transform algorithms and applications

• Main Author: Chin, Natalyn Shi Hui
• Other Authors: Wu Guohua
• Format: Final Year Project
• Language: English
• Published: Nanyang Technological University 2023
• Subjects: Science::Mathematics; Science::Physics
• Online Access: https://hdl.handle.net/10356/172128
• Institution: Nanyang Technological University

The Discrete Fourier Transform (DFT) has many important applications such as in signal processing. However, direct computation of the DFT has a time complexity of O(N^2), where N is the number of sample points. In 1965, James Cooley and John Tukey introduced a fast algorithm to decrease the time complexity of calculating DFTs to O(NlogN). After that, there were many variations of the Cooley-Tukey algorithm, such as the Radix-2 FFT, Radix-3 FFT, and split-radix FFT. In 1968, Bluestein and introduced a FFT for computing the DFT for arbitrary N, including prime sizes. Rader also published a FFT algorithm to compute the DFT for prime N. This paper explains some cases of the Cooley-Tukey algorithm and algorithms that can be used for prime N. It also highlights the key applications of the FFT and how it can be implemented in a few platforms.