Método de superposición-adición

En el procesamiento de señales , el método de superposición-suma es una forma eficiente de evaluar la convolución discreta de una señal muy larga con un filtro de respuesta de impulso finito (FIR) :${\ Displaystyle x [n]}$${\ Displaystyle h [n]}$

donde h [ m ] = 0 para m fuera de la región [1, M ] . Este artículo utiliza notaciones abstractas comunes, como o en las que se entiende que las funciones deben pensarse en su totalidad, en lugar de en instantes específicos (ver Convolución # Notación ).${\ estilo de texto y (t) = x (t) * h (t),}$${\ textstyle y (t) = {\ mathcal {H}} \ {x (t) \},}$${\ textstyle t}$

El concepto es dividir el problema en múltiples convoluciones de h [ n ] con segmentos cortos de :${\ Displaystyle x [n]}$

donde la convolución lineal es cero fuera de la región [1, L + M - 1] . Y para cualquier parámetro ^[A] es equivalente a la convolución circular de N puntos de con en la región [1, N ] . La ventaja es que la convolución circular se puede calcular de manera más eficiente que la convolución lineal, de acuerdo con el teorema de convolución circular :${\ Displaystyle y_ {k} [n] \ \ triangleq \ x_ {k} [n] * h [n] \,}$${\ Displaystyle N \ geq L + M-1, \,}$${\ Displaystyle x_ {k} [n] \,}$${\ Displaystyle h [n] \,}$

Cuando el algoritmo FFT implementa DFT e IDFT, el pseudocódigo anterior requiere aproximadamente N (log ₂ (N) + 1) multiplicaciones complejas para FFT, producto de matrices e IFFT. ^[B] Cada iteración produce N-M + 1 muestras de salida, por lo que la cantidad de multiplicaciones complejas por muestra de salida es aproximadamente :

Por ejemplo, cuando M = 201 y N = 1024, la ecuación 3 es igual a 13,67, mientras que la evaluación directa de la ecuación 1 requeriría hasta 201 multiplicaciones complejas por muestra de salida, siendo el peor de los casos cuando tanto x como h tienen valores complejos. Tenga en cuenta también que para cualquier dado M , Eq.3 tiene un mínimo con respecto a N . La figura 2 es una gráfica de los valores de N que minimizan la ecuación 3 para un rango de longitudes de filtro (M).

Fig 1: Una secuencia de cinco gráficos representa un ciclo del algoritmo de convolución de superposición-suma. El primer gráfico es una secuencia larga de datos que se procesarán con un filtro FIR de paso bajo. El segundo gráfico es un segmento de los datos que se procesarán por partes. El tercer gráfico es el segmento filtrado, incluidos los transitorios de subida y bajada del filtro. El cuarto gráfico indica dónde se agregarán los nuevos datos con el resultado de los segmentos anteriores. El quinto gráfico es el flujo de salida actualizado. El filtro FIR es un boxcar de paso bajo con M = 16 muestras, la longitud de los segmentos es L = 100 muestras y la superposición es de 15 muestras.

Fig 2: Una gráfica de los valores de N (una potencia entera de 2) que minimiza la función de costo ${\ Displaystyle {\ tfrac {N \ left (\ log _ {2} N + 1 \ right)} {N-M + 1}}}$

Fig 3: Ganancia del método de superposición-suma en comparación con una sola circunvolución circular grande. Los ejes muestran valores de longitud de señal N _x y longitud de filtro N _h .