Transformada discreta de Fourier y FFT

Fijamos N entero positivo y las muestras x[0],…, x[N−1], reales o complejas. La DFT cambia de base en ese espacio de dimensión N; no adivina muestras fuera del bloque. La nueva base usa oscilaciones que completan un número entero de vueltas en N posiciones. Un coeficiente indica cuánto aporta una dirección y con qué fase.

Su módulo es uno: multiplica girando, sin aumentar por sí mismo el módulo de una muestra.

La cancelación de esos giros separa oscilaciones distintas. Los signos real e imaginario forman parte de los datos, no son errores que haya que eliminar antes de mirar el resultado.

La directa no divide entre N; la inversa sí. Una convención distinta puede repartir los factores, pero hay que cambiar ambas fórmulas de forma compatible.

X[0] es la suma de las muestras, porque todos sus pesos son uno. La media es X[0]/N. Para cada otro k, escribimos primero sus pesos y después multiplicamos cada muestra por su peso antes de sumar. Esto evita confundir el signo del giro con el signo de la muestra.

Al sustituir la directa en la inversa aparece Σₖ₌₀ᴺ⁻¹exp(2πik(n−m)/N). Si n=m módulo N, cada término vale uno y la suma es N. Si no, es una geométrica finita de razón q≠1 con qᴺ=1: su suma (1−qᴺ)/(1−q) es cero. Aquí |q|=1 no causa un problema porque la suma es finita.

Así solo sobrevive x[m] con m=n dentro del bloque, multiplicada por N. El factor 1/N la recupera. La demostración sirve para cualquier vector de N datos. Si prolongamos la fórmula de reconstrucción a otros índices enteros, repite cada N muestras: esa es la extensión periódica de la representación, no una prueba de que el fenómeno medido se repitiera físicamente.

Si la frecuencia de muestreo es fₛ, el índice k representa kfₛ/N Hz. Frecuencias separadas por fₛ generan las mismas muestras, así los índices altos suelen mostrarse como (k−N)fₛ/N.

Esto describe las coordenadas del bloque; evitar aliasing en la señal continua requiere hipótesis de muestreo adicionales.

Para datos reales, X[N−k]=conj(X[k]) con índices módulo N. Cero y Nyquist, si existe, son reales. Un coseno real de amplitud A situado exactamente en un índice interior reparte amplitud entre dos coeficientes de módulo NA/2. Para mostrar amplitud unilateral se usa 2|X[k]|/N solo en esas frecuencias interiores; cero y Nyquist no se duplican.

Para N par, separamos x[2m] y x[2m+1]. Sus DFT de longitud N/2 son E[k] y O[k].

La misma multiplicación sirve para las dos salidas: es la mariposa.

Si N es potencia de dos repetimos la separación hasta bloques de un dato. La FFT no define un espectro diferente: calcula exactamente la DFT de antes en aritmética exacta. Existen otras descomposiciones para otros tamaños; no tener potencia de dos no hace que la DFT deje de existir.

La suma directa usa N contribuciones para cada una de N salidas: orden N². En radix dos hay log₂N niveles con N/2 mariposas por nivel, así el orden es Nlog₂N. Una mariposa contiene operaciones complejas; contar mariposas no equivale a contar exactamente instrucciones de una máquina.

En un ordenador, las rutas de cálculo pueden acumular redondeo de maneras distintas. Un resultado muy pequeño cercano a cero se compara con una tolerancia ligada a escala y precisión; tampoco se borra sin criterio cualquier coeficiente pequeño que pudiera ser una señal real. La factorización de N, memoria y biblioteca influyen en tiempo real.

El espaciado Δf=fₛ/N indica las frecuencias donde se evalúa el espectro del bloque. Observar más muestras al mismo fₛ alarga el registro y puede aportar información para separar tonos. Añadir ceros al bloque existente evalúa su espectro en más puntos, pero no mide nueva señal: no mejora por sí solo la capacidad física de distinguir dos frecuencias cercanas.

Si una oscilación no completa vueltas enteras en el bloque, sus extremos no encajan al repetir la representación y suele repartir energía entre varios índices: fuga espectral. Las ventanas cambian ese reparto, las anchuras y las amplitudes. Suavizar extremos tiene un coste y requiere correcciones adecuadas si queremos estimar amplitudes; la DFT sigue siendo exacta para el vector que recibe.

La inversa del producto X[k]H[k] de dos DFT de longitud N es y[n]=Σₘ₌₀ᴺ⁻¹x[m]h[(n−m) mod N]. La resta de índices vuelve al bloque por el módulo. Si queríamos convolución lineal, sus posiciones más allá del bloque se añadirán a otras, no desaparecerán.

Para listas de longitudes L y M, el último índice lineal posible es L+M−2, así hacen falta al menos L+M−1 casillas. Rellenar ambas entradas hasta una longitud N suficiente permite usar la multiplicación espectral sin solapamiento circular. Ese límite es independiente de que N sea potencia de dos.

Se demuestra usando la misma ortogonalidad que la inversa. La media X[0]/N, la simetría conjugada para datos reales y la reconstrucción completa aportan controles adicionales. Una comprobación de módulos no detecta todos los errores de fase.

Estas pruebas verifican que representamos bien el vector entregado. No demuestran que la medición evitara aliasing ni que una ventana corta separe cualquier par de tonos. Antes de interpretar un gráfico se conservan frecuencia de muestreo, cantidad de datos realmente medidos, ventana, relleno, unidades y normalización.