Ficha de uso

Introducción

El coste de la DFT directa

Calcular X[k] = Σ x[n] W_Nkn para las N frecuencias exige N productos complejos por cada una: N² en total. Con N = 1024 son más de un millón. La FFT (transformada rápida de Fourier) es un conjunto de algoritmos que calculan exactamente la misma DFT con del orden de N log₂ N operaciones, aprovechando que W_Nkn solo toma N valores distintos y es periódica y simétrica.

Diezmado en el tiempo

Si N es par, se separan las muestras pares, f[m] = x[2m], y las impares, g[m] = x[2m + 1]. Como W_N² = WN/2,

X[k] = F[k] + W_Nk G[k], X[k + N/2] = F[k] − W_Nk G[k], k = 0, …, N/2 − 1,

donde F y G son DFT de N/2 puntos. La DFT de N puntos se reduce a dos de N/2 más N/2 productos por los factores de giro W_Nk. Cada par de ecuaciones es una mariposa: dos entradas a y b, dos salidas a + Wb y a − Wb, y un solo producto complejo.

Repetir hasta el final

Si N = 2ν, cada DFT de N/2 se vuelve a partir, hasta llegar a DFT de 2 puntos, que son solo una suma y una resta. Quedan ν = log₂N etapas de N/2 mariposas:

(N/2) log₂N productos complejos,

frente a N². Con N = 1024, 5120 frente a 1 048 576. Muchos de esos productos son triviales (por ±1 o ±j).

El orden de bits invertido

Al separar pares e impares una y otra vez, la entrada acaba en un orden extraño: la posición i contiene x[n] con n igual a i escrito en binario al revés. Con N = 8, el orden es 0, 4, 2, 6, 1, 5, 3, 7. La salida sale en orden natural. Ordenar la entrada así permite hacer todo el cálculo en el sitio, sobre el mismo vector.

Otras variantes

El diezmado en frecuencia separa la salida en k pares e impares y deja el orden invertido en la salida. Hay algoritmos en base 4, de base mixta para N que no son potencia de 2 y otros, pero todos tienen un coste del orden de N log N. Los programas de cálculo (fft de NumPy o de Matlab) eligen el mejor según N.

Guía de uso

Ejercicios

1. Bits invertidos. Con la rampa n, lee la primera columna. ¿En qué orden están las muestras? Explica por qué x[3] ocupa la posición 6.

Solución 0, 4, 2, 6, 1, 5, 3, 7. 3 en binario con 3 bits es 011 y, al revés, 110, que es 6. Las posiciones 0 a 3 tienen las muestras pares y las 4 a 7, las impares, y dentro de cada mitad se repite la separación.

2. Una constante. Con la entrada constante, anota los valores de cada etapa. ¿Qué hacen las mariposas?

Solución Etapa 1: (2, 0, 2, 0, 2, 0, 2, 0); etapa 2: (4, 0, 0, 0, 4, 0, 0, 0); etapa 3: X = (8, 0, 0, 0, 0, 0, 0, 0). Cada mariposa suma y resta: las sumas acumulan la componente continua y las restas se anulan.

3. Un impulso desplazado. Con δ[n − 1], sigue el valor 1 por el grafo. ¿Por qué la salida es X[k] = W₈k?

Solución x[1] está en la posición 4. En las etapas 1 y 2 solo se suma o se resta sin factores de giro no triviales y llega a las posiciones 4 a 7 con valor 1. En la etapa 3, cada mariposa multiplica por W₈j y da W₈j y −W₈j = W₈j + 4. Es la propiedad del desplazamiento: módulo 1 y fase lineal.

4. El ejercicio 15 de la hoja, en grande. Con el coseno cos(2πn/8), ¿qué vale X[k]? Mira la etapa 2: ¿qué DFT de 4 puntos son las dos mitades?

Solución X[1] = X[7] = 4 y el resto, cero. La mitad de arriba es la DFT de 4 puntos de las muestras pares, cos(πm/2) = (1, 0, −1, 0): (0, 2, 0, 2). La de abajo es la de las impares, (0,71; −0,71; −0,71; 0,71): (0; 1,41 + 1,41j; 0; 1,41 − 1,41j). La etapa 3 las combina con W₈k. En la hoja, con N = 4, el mismo procedimiento da (8, −3 − 3j, 2, −3 + 3j) para x = (1, 3, 4, 0).

5. El ejercicio 14 de la hoja: cuánto se gana. ¿Cuántos productos no triviales hay en la FFT de 8 puntos? A un nanosegundo por producto, ¿cuánto tarda una DFT de 4096 puntos directamente y con la FFT?

Solución De los 12 productos, solo los de W₈¹ y W₈³ de la etapa 3 no son triviales: 2 productos, frente a 64 de la DFT directa. Con N = 4096: N² = 1,68·10⁷ productos, 16,8 ms, frente a (N/2)·12 = 24 576, 24,6 µs, unas 680 veces menos.

Para profundizar

Relación con otros conceptos