Inicio · Parte 13 — Teoría de la información, señales y series
coste DFT: O(n²) coste FFT: O(n log n)
n = 10⁶: 10¹² frente a 2·10⁷ operaciones
teorema de convolución: f * g = IFFT(FFT(f)·FFT(g))La transformada discreta de Fourier calculada de forma directa necesita n² operaciones complejas. Para un millón de muestras eso son 10¹² operaciones: horas o días. La FFT obtiene exactamente el mismo resultado en O(n log n), unas 2·10⁷ operaciones: una fracción de segundo.
El algoritmo, publicado por Cooley y Tukey en 1965 —aunque Gauss ya lo conocía en 1805—, explota que la transformada de una señal se puede construir a partir de las transformadas de sus muestras pares e impares. Aplicar esa descomposición recursivamente da el logaritmo. Es un divide y vencerás de manual.
Su impacto es difícil de exagerar. La FFT es lo que hace posible el audio digital, las telecomunicaciones modernas, la resonancia magnética, el análisis sísmico y la multiplicación rápida de polinomios y de enteros grandes. Está en la lista habitual de algoritmos más influyentes del siglo XX.
El teorema de convolución convierte esa velocidad en una herramienta general: convolucionar en el tiempo es multiplicar en frecuencia, así que para núcleos grandes es más rápido transformar, multiplicar punto a punto y volver, que convolucionar directamente. El punto de cruce está alrededor de núcleos de 50 a 100 elementos, y por eso las CNN con núcleos de 3×3 no usan FFT.
FFT y DFT sobre la misma señal de 256 muestras.
256 muestras con componentes en 10 Hz y 40 Hz
picos detectados: [10, 40]
frecuencias reales: [10, 40] coinciden ✓
FFT y DFT dan resultados idénticos ✓
Coste:
DFT: 256² = 65 536 operaciones
FFT: 256 · log₂ 256 = 256 · 8 = 2 048 operaciones
ganancia: 32×
Para n = 10⁶ la ganancia sería de 50 000×:
la diferencia entre imposible y instantáneo.FFT frente a DFT: mismo resultado, coste muy distinto.
python classes/part-13-teoria-de-la-informacion-senales-y-series/274-fft/lab.py
compmath run 274muestraspicos_detectadosfrecuencias_realescoincidenfft_y_dft_coincidenoperaciones_DFToperaciones_FFTfactor_de_ahorrorequisito_del_algoritmo_radix2{
"muestras": 256,
"picos_detectados": [
10,
40
],
"frecuencias_reales": [
10,
40
],
"coinciden": true,
"fft_y_dft_coinciden": true,
"operaciones_DFT": 65536
}Procesamiento de audio en tiempo real, telecomunicaciones, imagen médica, convoluciones rápidas y multiplicación de enteros grandes.
La función de pérdida de casi todo clasificador es entropía cruzada; el VAE optimiza un ELBO con un término KL; las CNN son convoluciones aprendidas.
10.1090/s0025-5718-1965-0178586-1 verificado en Crossref (2026-08-19).