Capítulo 7La DFT y la FFT

Todo lo anterior ha sido construir intuición. Este es el algoritmo real: dada nada más que una lista de números muestreados, calcula exactamente qué frecuencias hay en la señal — sin espiar cómo se construyó.

Diseña una señal (igual que en el Capítulo 5)

Arrastra para ajustar la amplitud de cada frecuencia

Espectro calculado solo a partir de las muestras (la salida de la DFT)

Señal / muestras |X_k| recuperado por la DFT

La fórmula

La Transformada Discreta de Fourier toma $N$ muestras $x_0, x_1, \dots, x_{N-1}$ y produce $N$ números complejos que describen el contenido de frecuencia de la señal:

Transformada Discreta de Fourier

$$ X_k = \sum_{n=0}^{N-1} x_n \, e^{-i 2\pi k n / N} \qquad k = 0, 1, \dots, N-1 $$

Cada $X_k$ responde una pregunta: "¿cuánto hay de la frecuencia $k$ (en ciclos por ventana de muestras) presente?" $|X_k|$ — la magnitud de ese número complejo — es exactamente la altura de barra que ves graficada arriba. Esta es la misma rotación $e^{-i\theta}$ de los círculos del Capítulo 4, solo que ejecutada una vez por cada frecuencia que quieres probar, en lugar de dibujada a lo largo del tiempo.

Nota que el espectro de arriba se enciende solo en las frecuencias que realmente ajustaste con los controles — todo lo demás se lee esencialmente cero. La DFT recuperó tu receta de frecuencias a partir de nada más que los valores de muestra sin procesar.

Por qué existe la FFT

Calculada directamente, la fórmula de arriba cuesta $O(N^2)$ multiplicaciones — por cada una de las $N$ frecuencias de salida, sumas sobre las $N$ muestras de entrada. La Transformada Rápida de Fourier (FFT) no es una fórmula distinta; es la misma DFT calculada de forma inteligente, dividiendo recursivamente la suma en muestras de índice par e impar y reutilizando trabajo entre ellas. Eso reduce el costo a $O(N \log N)$:

N (muestras)	DFT: N² ops	FFT: N·log₂N ops	Aceleración

Con $N$ pequeño la diferencia apenas importa. En los tamaños que usa el procesamiento real de audio, imágenes y señales de radio — millones de muestras — la FFT es la única razón por la que algo de esto corre en tiempo real.

El ciclo completo, en una frase: una señal se muestrea (Cap. 6) respetando el límite de Nyquist, la FFT convierte esas muestras en un espectro (este capítulo) usando la misma idea de fasor giratorio que los epiciclos (Cap. 4), ese espectro se edita o analiza en el dominio de la frecuencia (Cap. 5), y una transformada inversa — la misma fórmula ejecutada al revés — reconstruye una señal en el dominio del tiempo como una suma de ondas seno (Cap. 3). Ese ciclo completo es la transformada de Fourier.