Transformada rápida de Fourier (FFT)

Nivel AvanzadoDificultad ★★★★★Aplicación⌖ Ver en el mapa

¿Qué es?

Calcula la DFT de $N$ puntos en $O(N\log N)$ en vez de $O(N^2)$ partiéndola recursivamente en muestras pares e impares (Cooley–Tukey, 1965, anticipado por Gauss). Uno de los algoritmos más importantes del siglo XX.

Fórmulas

$X_k = E_k + e^{-2\pi i k/N}\,O_k, \qquad X_{k + N/2} = E_k - e^{-2\pi i k/N}\,O_k$
la mariposa: dos DFT de la mitad de tamaño dan la completa: $T(N) = 2T(N/2) + O(N) = O(N\log N)$

¿Por qué importa?

Los espectrogramas, los efectos de audio, las radios OFDM, la convolución rápida, la multiplicación de polinomios y de enteros grandes y la resonancia magnética funcionan con FFT.

Las matemáticas que hay detrás

Números complejos★★★★★fundamental
La FFT se basa en las simetrías de las raíces $N$ -ésimas de la unidad $e^{-2\pi i k/N}$ .
Transformada de Fourier★★★★★fundamental
La FFT calcula la DFT en $O(N\log N)$ en vez de $O(N^2)$ .

Esta página tiene lo esencial. Un desarrollo más completo (intuición, definición formal, ejemplo resuelto) está en camino.