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...
| Autor principal: | |
|---|---|
| Outros Autores: | |
| Formato: | Final Year Project (FYP) |
| Idioma: | English |
| Publicado em: |
Nanyang Technological University
2023
|
| Assuntos: | |
| Acesso em linha: | https://hdl.handle.net/10356/172128 |
| _version_ | 1826117014971744256 |
|---|---|
| author | Chin, Natalyn Shi Hui |
| author2 | Wu Guohua |
| author_facet | Wu Guohua Chin, Natalyn Shi Hui |
| author_sort | Chin, Natalyn Shi Hui |
| collection | NTU |
| description | 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. |
| first_indexed | 2024-10-01T04:20:50Z |
| format | Final Year Project (FYP) |
| id | ntu-10356/172128 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T04:20:50Z |
| publishDate | 2023 |
| publisher | Nanyang Technological University |
| record_format | dspace |
| spelling | ntu-10356/1721282023-11-27T15:35:53Z Fast fourier transform algorithms and applications Chin, Natalyn Shi Hui Wu Guohua School of Physical and Mathematical Sciences guohua@ntu.edu.sg Science::Mathematics Science::Physics 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. Bachelor of Science in Physics and Mathematical Sciences 2023-11-27T05:12:18Z 2023-11-27T05:12:18Z 2023 Final Year Project (FYP) Chin, N. S. H. (2023). Fast fourier transform algorithms and applications. Final Year Project (FYP), Nanyang Technological University, Singapore. https://hdl.handle.net/10356/172128 https://hdl.handle.net/10356/172128 en application/pdf Nanyang Technological University |
| spellingShingle | Science::Mathematics Science::Physics Chin, Natalyn Shi Hui Fast fourier transform algorithms and applications |
| title | Fast fourier transform algorithms and applications |
| title_full | Fast fourier transform algorithms and applications |
| title_fullStr | Fast fourier transform algorithms and applications |
| title_full_unstemmed | Fast fourier transform algorithms and applications |
| title_short | Fast fourier transform algorithms and applications |
| title_sort | fast fourier transform algorithms and applications |
| topic | Science::Mathematics Science::Physics |
| url | https://hdl.handle.net/10356/172128 |
| work_keys_str_mv | AT chinnatalynshihui fastfouriertransformalgorithmsandapplications |