La transformada de Fourier aparece con frecuencia en la física y las matemáticas, lo que se traduce en que también tenga muchos usos en la vida cotidiana.
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, cuando la señal de entrada está formada por una mezcla (es decir, una superposición) de distintas frecuencias, la transformada separa las frecuencias individuales y muestra sus intensidades relativas.
Esto hace que la transformada sea una herramienta principal en el procesamiento de señales (por ejemplo, filtrado, compresión, etc.) y en muchas aplicaciones de la ciencia de datos.
Por lo tanto, quizá se use mucho más de lo que uno imaginaría en un principio, lo que también la convierte en un ejemplo destacado 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.
Si bien 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 está fuera del alcance de este ejercicio, pero la transformada discreta directa (hacia el 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ₙ es una muestra individual.
Aunque es sumamente ú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 lograr con una estrategia de divide y vencerás que aprovecha ciertas 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 para las que sirve la transformada.
