Una familia de algoritmos que calcula la transformada discreta de Fourier (DFT) de una secuencia de forma eficiente al explotar simetrías, periodicidades y la factorización recursiva de la matriz DFT para reducir la complejidad aritmética de O(N^2) a O(N log N) en casos comunes.

Principio

Usar factorización divide-y-vencerás (descomposiciones radix, operaciones en mariposa) y simetrías de exponentes complejos para reutilizar resultados intermedios (factores twiddle) y minimizar cálculos redundantes en la DFT.

Demostración

Cálculo del espectro de frecuencias de una señal muestreada uniformemente de longitud N=2^k con una implementación radix-2 de la FFT que realiza O(N log N) operaciones complejas, permitiendo análisis espectral en tiempo real.

Aplicación incorrecta

Aplicar una FFT estándar a datos muestreados no uniformemente sin remuestreo o a secuencias con amplio rango dinámico numérico sin escalado, provocando aliasing o errores de redondeo severos y estimaciones espectrales engañosas.

Consecuencia

Permite convolución rápida mediante multiplicación en el dominio de la frecuencia, estimación espectral en tiempo real y procesamiento de señales e imágenes a gran escala que sería inviable con una DFT ingenua.

Inversión

Evaluación directa de la transformada discreta de Fourier sumando N^2 exponenciales complejas (DFT ingenua), que es sencilla conceptualmente pero computacionalmente impráctica para grandes N.

Límite

Supone datos muestreados uniformemente y normalmente requiere longitudes factorizables (potencias de dos para implementaciones radix óptimas); la estabilidad numérica depende de detalles de implementación y del escalado de los datos; existen algoritmos especializados (NFFT) para muestreo no uniforme.

Tensión semántica

Tensión con transformadas especializadas (wavelets, transformada de Fourier de ventana corta, NFFT): la FFT es óptima para análisis frecuencial global con muestreo uniforme, pero puede ser menos eficaz cuando se precisa resolución local tiempo-frecuencia o el muestreo es no uniforme.

Síntesis

Clase de algoritmos que transforma secuencias muestreadas uniformemente en coeficientes frecuenciales mediante la reutilización recursiva de la estructura DFT, sacrificando estructura algorítmica para lograr grandes ahorros computacionales.