derivadas.dev

Pablo Díaz Viñambres

MSc Informatics @ TUM

The Fast Fourier Transform

FFTsAnalysisPythonThesis


The topic I chose for my Mathematics BSc thesis was Fourier Transforms, a mathematical tool that has fascinated me for years and that I wanted to explore as deeply as possible. This work starts with a compilation of important results on LpL^p spaces, particularly L1L^1, where we first define the (continuous) Fourier Transform (FT). We later prove the Plancherel theorem for extension to L2L^2 and hint at multi-dimensional FT construction and properties.

Discrete Fourier transform visualization

During the second part of the work, we provide a solid mathematical framework for the Discrete FT (DFT). This DFT can be thought of as a sampling of a continuous FT, and can be defined neatly via roots of unity and Fourier matrices. With the DFT defined, we can start talking about Fast FT (FFT) algorithms for its efficient computation. First, we introduce the most common Cooley-Tukey algorithm, both in its Decimation-In-Time (DIT) and Decimation-In-Frequency (DIF) approaches, that use the common algorithmic idea of divide and conquer to reduce the complexity of computing an N-point DFT from O(N2)\mathcal{O}(N^2) to O(NlogN)\mathcal{O}(N \log N), for N=2dN = 2^d, that allows for very fast O(NlogN)\mathcal{O}(N\log N) convolutions on the frequency domain through the discrete convolution theorem. Other FFT algorithms exist, such as split-radix FFTs and Rader or Bluestein FFTs for prime NN.

JPEG quality versus compression example

To conclude the work, we review important applications on signal processing (low, high and band pass filters, spectral analysis of guitar chords) and image compression (the JPEG format). Overall, I learned a great deal and had a lot of fun writing this thesis. The work received a very high grade (9.8/10). I thank Lucía López Somoza for her great supervision!

Guitar harmonics visualized with FFT