liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Fast Fourier transform: Derivation, implementation and application of the Cooley-Tukey fast Fourier transform
Linköping University, Department of Mathematics, Applied Mathematics. Linköping University, Faculty of Science & Engineering.
Linköping University, Department of Mathematics, Applied Mathematics. Linköping University, Faculty of Science & Engineering.
Linköping University, Department of Mathematics, Applied Mathematics. Linköping University, Faculty of Science & Engineering.
Linköping University, Department of Mathematics, Applied Mathematics. Linköping University, Faculty of Science & Engineering.
Show others and affiliations
2025 (English)Independent thesis Basic level (degree of Bachelor), 13 HE creditsStudent thesisAlternative title
Snabb Fouriertransform : Härledning, implementation och applikation av Cooley-Tukeys algoritm för snabb Fouriertransform (Swedish)
Abstract [en]

The fast Fourier transform (FFT) is an algorithm which transforms sampled data from state-space to Fourier-space. By approximating the continuos Fourier transform we first derive a naive discrete Fourier transform (DFT). This naive implementation transforms samples via a matrix product, and has a time complexity of $\mathcal{O}(n^2)$. The complexity can be lowered to $\mathcal{O}(n\log n)$ when the number of samples is a power of two, or padded to one. To do this, we decompose the DFT matrix into $\log_2 n$ products which can be calculated in linear time.

We compare the DFT and FFT algorithms and confirm that the asymptotic time complexity conforms with the theoretical result. We also compare recursive, iterative and multithreaded FFT variants and find that they performed similarly. The choice of programming language, however, has a big impact on performance. Finally, we compare our implementations to the state-of-the-art FFT library FFTW.

Two applications of the DFT are explored. The first, to numerically calculate matrix-vector products with circulant and Toeplitz matrices. The second, to filter coastline data.

The FFT algorithm, while theoretically complex, has relatively simple implementations that perform well compared to a naive DFT. An area that could be improved in our implementation is the handling of signal sizes that are not powers of two. However this is not a trivial problem to solve. Still, the algorithm can be used effectively in a wide range of applications.

Place, publisher, year, edition, pages
2025. , p. 29
Keywords [en]
FFT, DFT, Cooley-Tukey, Fourier transform
National Category
Computational Mathematics
Identifiers
URN: urn:nbn:se:liu:diva-214587ISRN: LiTH-MAT-EX--2025/08--SEOAI: oai:DiVA.org:liu-214587DiVA, id: diva2:1966827
Subject / course
Computational Mathematics
Presentation
2025-05-28, S27, C-huset, Campus Valla, Linköpings universitet, Linköping, 13:15 (Swedish)
Supervisors
Examiners
Available from: 2025-06-11 Created: 2025-06-10 Last updated: 2025-06-11Bibliographically approved

Open Access in DiVA

fulltext(411 kB)321 downloads
File information
File name FULLTEXT01.pdfFile size 411 kBChecksum SHA-512
517bf9e85de7f8cf83c8d7ed1194b31f85c8a87494b60b2cef8bd35f812121c17d2428e620c0cdcb657ce15d43d3a89fd1c141afb4528ca26c2f0f277d6d4158
Type fulltextMimetype application/pdf

By organisation
Applied MathematicsFaculty of Science & Engineering
Computational Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 323 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 428 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf