FFT — Transformada Rápida de Fourier explicada de forma simple

La FFT, o transformada rápida de Fourier, es una forma rápida de calcular la transformada discreta de Fourier (DFT). Si partes de muestras espaciadas uniformemente, la DFT te dice cuánto de cada patrón de frecuencia discreto aparece en esas muestras.

El punto importante es que la FFT no cambia el resultado. Da los mismos valores de la DFT que la fórmula directa, pero llega a ellos con mucho menos trabajo repetido.

La FFT en una frase

La FFT es un algoritmo más rápido para obtener los mismos números en el dominio de la frecuencia que la DFT ya define.

Qué mide la DFT

Supón que tienes muestras $x_0, x_1, \dots, x_{N-1}$. La DFT produce números $X_0, X_1, \dots, X_{N-1}$ definidos por

$$X_k = \sum_{n=0}^{N-1} x_n e^{-i 2 \pi kn / N}$$

Cada $X_k$ mide con qué intensidad los datos coinciden con un patrón de frecuencia discreto.

Si las muestras están espaciadas uniformemente con una frecuencia de muestreo $f_s$, entonces los bins de frecuencia adyacentes están separados por

$$\frac{f_s}{N}$$

Esa condición importa. Sin una frecuencia de muestreo conocida, sigues teniendo bins de la DFT, pero no puedes etiquetarlos como frecuencias físicas, como hercios.

Por qué la FFT es más rápida

Una FFT es una familia de algoritmos para calcular la DFT de manera eficiente. El truco principal es reutilizar estructura en los factores exponenciales complejos en lugar de volver a calcular desde cero sumas casi idénticas.

La versión más fácil de visualizar es la FFT radix-2. Funciona de forma más natural cuando $N$ es una potencia de $2$, y divide una transformada de longitud $N$ en dos transformadas de longitud $N/2$ antes de combinar los resultados.

En la DFT directa, la cantidad de operaciones aritméticas crece del orden de $N^2$. En métodos FFT comunes, baja aproximadamente a $N \log N$.

Esa diferencia es la razón por la que las FFT importan en la práctica. Para entradas pequeñas, ambos métodos pueden parecer aceptables. Para entradas grandes, la FFT es muchísimo más rápida.

Cómo la FFT divide el trabajo

En lugar de comparar directamente cada muestra con cada patrón de frecuencia, la FFT divide el problema en transformadas más pequeñas y luego las recombina con factores de fase.

Una división estándar es:

1. Pon las muestras de índice par en una lista.
2. Pon las muestras de índice impar en otra lista.
3. Calcula transformadas más pequeñas sobre esas listas.
4. Combina las dos mitades.

Eso es divide y vencerás aplicado al análisis de frecuencias.

Ejemplo de FFT de 4 puntos

Toma la señal de 4 puntos

$$x = [1, 0, 1, 0]$$

Este patrón alterna entre $1$ y $0$, así que esperamos cierta estructura de frecuencia en lugar de un resultado completamente plano.

Divídela en índices pares e impares:

$$x_{\text{even}} = [1, 1], \qquad x_{\text{odd}} = [0, 0]$$

La DFT de 2 puntos de la parte par es

$$E = [2, 0]$$

y la DFT de 2 puntos de la parte impar es

$$O = [0, 0]$$

Para una FFT de 4 puntos, el paso de combinación es

$$X_k = E_k + W_4^k O_k, \qquad X_{k+2} = E_k - W_4^k O_k, \qquad k = 0,1$$

donde

$$W_4 = e^{-i 2 \pi / 4}$$

Como $O_k = 0$, la combinación es especialmente simple:

$$X = [2, 0, 2, 0]$$

Ahora interpreta el resultado.

$X_0 = 2$ es el término de frecuencia cero, así que refleja el valor medio no nulo de las muestras. El valor no nulo en $X_2$ captura la parte alternante del patrón en este caso de 4 puntos. Si primero restas la media, el término $X_0$ desaparece y el componente alternante destaca con más claridad.

Este ejemplo es pequeño, pero la idea escala: resuelve transformadas más pequeñas y luego combínalas en lugar de reconstruir toda la suma cada vez.

Errores comunes con la FFT

Tratar la FFT y la DFT como resultados distintos

No lo son. La FFT es un método más rápido para calcular la DFT.

Leer los bins como frecuencias físicas demasiado pronto

Las posiciones de los bins solo se convierten en frecuencias físicas cuando se conoce el espaciado entre muestras. Si la frecuencia de muestreo es $f_s$, entonces la separación entre bins es $f_s/N$ para muestras espaciadas uniformemente.

Suponer que el zero-padding añade información nueva

El zero-padding puede hacer que un espectro se vea más suave porque muestrea la transformada subyacente con mayor detalle, pero no añade nuevos datos medidos.

Ignorar la preparación de la señal

Quitar la media, aplicar ventanas y elegir cuidadosamente el muestreo puede importar mucho. Si se ignoran esas condiciones, la salida de la FFT puede seguir siendo matemáticamente correcta para las muestras dadas, pero engañosa al interpretarla.

Dónde se usa la FFT

La FFT aparece en cualquier situación en la que necesites información rápida en el dominio de la frecuencia a partir de datos muestreados. Algunos ejemplos comunes son el análisis espectral, el filtrado, el procesamiento de imágenes, el análisis de vibraciones, la resolución numérica de ecuaciones diferenciales y los cálculos rápidos de polinomios o convoluciones.

La razón es práctica: muchas operaciones se vuelven más fáciles o más rápidas después de pasar del dominio de las muestras al dominio de la frecuencia.

Prueba un caso similar

Toma $8$ muestras espaciadas uniformemente de una onda seno a lo largo de un período completo y calcula la DFT con una calculadora o un script. Luego añade un desplazamiento constante y compara la nueva salida. El valor más grande en $X_0$ es una forma simple de ver qué separa la FFT.