derivadas.dev

Pablo Díaz Viñambres

MSc Informatics @ TUM

La Transformada Rápida de Fourier

FFTsAnalysisPythonTrabajos


El tema que escogí para mi TFG de Matemáticas fue la Transformada de Fourier, una herramienta matemática que me fascina desde hace años y que quería estudiar a fondo. Este trabajo comienza con una recopilación de resultados importantes sobre espacios LpL^p, en particular L1L^1, donde definimos por primera vez la Transformada de Fourier (FT) continua. Después demostramos el teorema de Plancherel para su extensión a L2L^2 y apuntamos la construcción y propiedades de la FT multidimensional.

Discrete Fourier transform visualization

En la segunda parte del trabajo, desarrollamos un marco matemático sólido para la Transformada Discreta de Fourier (DFT). Esta DFT puede entenderse como un muestreo de una FT continua, y se define de forma limpia mediante raíces de la unidad y matrices de Fourier. Una vez definida la DFT, podemos introducir algoritmos de Tranformada Rápida de Fourier (FFT) para su cálculo. Primero presentamos el conocido algoritmo Cooley-Tukey, tanto en su variante Decimation-In-Time (DIT) como Decimation-In-Frequency (DIF), que aplican la idea de divide y vencerás para reducir la complejidad del cálculo de una DFT de NN puntos desde O(N2)\mathcal{O}(N^2) a O(NlogN)\mathcal{O}(N \log N), para N=2dN = 2^d. Esto permite realizar convoluciones muy rápidas O(NlogN)\mathcal{O}(N\log N) en el dominio de la frecuencia mediante el discrete convolution theorem. También existen otros algoritmos FFT, como split-radix FFT y Rader o Bluestein FFT para NN primo.

JPEG quality versus compression example

Para cerrar el trabajo, repasamos aplicaciones importantes en procesamiento de señales (filtros low-pass, high-pass y band-pass, análisis espectral de acordes de guitarra) y compresión de imágenes (formato JPEG). El trabajo obtuvo una nota sobresaliente (9.8/10). En conjunto, aprendí muchísimo y disfruté mucho escribiendo esta tesis. Muchas gracias a Lucía López Somoza por su excelente supervisión!

Guitar harmonics visualized with FFT