Fast fourier transform algorithms and applications
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 com...
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Final Year Project |
| Language: | English |
| Published: |
Nanyang Technological University
2023
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/172128 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Nanyang Technological University |
| Language: | English |
| Summary: | 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. |
|---|