La transformada de Fourier aparece con frecuencia en física y matemáticas, lo que hace que también tenga muchos usos cotidianos.
En resumen, la transformada de Fourier toma una señal de entrada, a menudo en el dominio del tiempo o del espacio, y la transforma al dominio de la frecuencia.
Y, más concretamente, con una señal de entrada compuesta por una mezcla (es decir, una superposición) de distintas frecuencias, la transformada separa las frecuencias individuales y muestra su fuerza relativa.
Esto convierte a la transformada en una herramienta fundamental en el procesamiento de señales (por ejemplo, filtrado, compresión, etc.) y en muchas aplicaciones de ciencia de datos.
Por lo tanto, quizá se use más de lo que uno imaginaría en un principio, lo que también la convierte en un ejemplo claro de dónde los números imaginarios se vuelven indispensables, teniendo en cuenta que la salida de la transformada de Fourier es, en general, un número complejo.
Aunque la transformada de Fourier tiene una formulación integral, nosotros somos digitales, así que nos interesa la versión discreta.
La deducción de la transformada queda fuera del alcance de este ejercicio, pero la transformada discreta directa (al dominio de la frecuencia) tiene la siguiente forma:
Xₖ = Σ xₙ * ℯ^(-2iπk * n/N)
Aquí, la suma recorre n, y N es el número de muestras, k es la frecuencia, i la unidad imaginaria y xₙ una muestra individual.
Aunque es extremadamente útil, la transformada de Fourier, implementada de forma ingenua, es un poco lenta (O(n²)).
La transformada rápida de Fourier (FFT) es un algoritmo que la acelera drásticamente.
Esto se suele conseguir mediante una estrategia de divide y vencerás que aprovecha algunas simetrías de la formulación y da como resultado una complejidad asintótica de O(Nlog(N)).
Esta aceleración mejora enormemente la practicidad y el rango de aplicaciones adecuadas para la transformada.
