Ficha de uso

Introducción

Multiplicar DFT es convolucionar circularmente

En la DTFT, multiplicar espectros equivale a convolucionar secuencias. En la DFT ocurre lo mismo, pero con la convolución circular de N puntos:

y[n] = (x ⊛ h)[n] = Σm=0N−1 x[m] h[((n − m))_N], 0 ≤ n < N ⟷ Y[k] = X[k] H[k].

Es la convolución de siempre, pero h se invierte y se desplaza módulo N: al girar, las muestras que salen por la derecha vuelven a entrar por la izquierda, como si las dos secuencias estuvieran dibujadas en una circunferencia.

Circular frente a lineal

Si x tiene L muestras y h tiene P, la convolución lineal x ∗ h tiene L + P − 1. La circular de N puntos es la lineal plegada con periodo N:

(x ⊛ h)[n] = Σ_r (x ∗ h)[n + rN], 0 ≤ n < N.

Es el aliasing temporal de la extensión periódica: Y[k] son N muestras de la DTFT de x ∗ h, y si N es menor que su longitud, las copias se solapan.

Por qué importa

Esta es la base del filtrado con la FFT: para calcular x ∗ h se rellenan las dos con ceros hasta N ≥ L + P − 1 (normalmente la siguiente potencia de 2), se multiplican sus FFT y se calcula la IFFT. Con secuencias largas es mucho más rápido que la suma directa. Si N = L, solo están mal las P − 1 primeras muestras, y esa idea da el método de solapamiento-almacenamiento.

Guía de uso

Ejercicios

1. Mirar la circunferencia. Con la rampa 1…5, el pulso de 4 y N = 8, recorre n de 0 a 7. ¿Cómo se mueve h[((n − k))_N]? ¿Coincide la circular con la lineal?

Solución Con n = 0, h invertido ocupa k = 0 y k = 5, 6, 7: las tres muestras que en la convolución lineal quedarían en k negativo aparecen por la derecha. Al aumentar n, el pulso gira hacia la derecha. Como N = 8 = L + P − 1, la circular coincide con la lineal: (1, 3, 6, 10, 14, 12, 9, 5).

2. Plegado. Con las mismas secuencias, baja N a 6 y luego a 5. ¿Qué sale? Calcúlalo sumando muestras de la lineal.

Solución Con N = 6, y_c[n] = y[n] + y[n + 6]: (1 + 9, 3 + 5, 6, 10, 14, 12) = (10, 8, 6, 10, 14, 12). Con N = 5, y_c[n] = y[n] + y[n + 5]: (1 + 12, 3 + 9, 6 + 5, 10, 14) = (13, 12, 11, 10, 14).

3. El ejercicio 8 c de la hoja: qué muestras se salvan. En el caso N = 5 = L, ¿qué muestras de la circular coinciden con la lineal? ¿Cuántas están mal, en general, cuando N = L?

Solución Las dos últimas, 10 y 14: las tres primeras reciben la cola de la lineal. Con N = L, la cola tiene P − 1 muestras y caen sobre las P − 1 primeras: n = 0, …, P − 2 son incorrectas y el resto, correctas. En la hoja, con L = 100 y M = 30, son correctas de n = 29 a 99.

4. El ejercicio 7 de la hoja, con una diferencia. Con la rampa 1…5 y h = (1, −1), calcula la convolución lineal y la circular con N = 5. ¿Qué N hace falta para que coincidan?

Solución La lineal es la diferencia x[n] − x[n − 1] = (1, 1, 1, 1, 1, −5). Con N = 5, la última muestra se suma a la primera: (−4, 1, 1, 1, 1). Hace falta N ≥ 5 + 2 − 1 = 6. En la hoja, con x = (1, 2, 3, 4) y h = (1, 1), la circular de 4 puntos da (5, 3, 5, 7) y hace falta N ≥ 5.

5. Una secuencia más larga que N. Pon x = pulso de 6, h = 1, 2, 1 y N = 4. ¿Qué secuencia de 4 puntos se usa como x? ¿Cuánto vale la suma de la salida circular? ¿Y la de la lineal?

Solución El pulso se pliega: (1 + 1, 1 + 1, 1, 1) = (2, 2, 1, 1). La suma de la salida es Σx·Σh = 6·4 = 24 en los dos casos, porque Y[0] = X[0]H[0] y el plegado no cambia la suma: es la DFT en k = 0.

Para profundizar

Relación con otros conceptos