Método de superposición y 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.${\displaystyle x[n]}$con un filtro de respuesta de impulso finito (FIR)${\displaystyle h[n]}$:

dónde${\displaystyle h[m]=0}$para${\displaystyle m}$fuera de la región${\displaystyle [1,M].}$ 

Este artículo utiliza notaciones abstractas comunes, como${\textstyle y(t)=x(t)*h(t),}$o${\textstyle y(t)={\mathcal {H}}\{x(t)\},}$en el que se entiende que las funciones deben pensarse en su totalidad, en lugar de en instantes específicos.${\textstyle t}$(véase Convolución#Notación ).

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

${\displaystyle x_{k}[n]\ \triangleq \ {\begin{cases}x[n+kL],&n=1,2,\ldots ,L\\0,&{\text{en otro caso}},\end{cases}}}$

dónde${\displaystyle L}$es una longitud de segmento arbitraria. Entonces :

${\displaystyle x[n]=\sum _{k}x_{k}[n-kL],\,}$

y${\displaystyle y[n]}$se puede escribir como una suma de convoluciones cortas : ^{[ 1 ]}

${\displaystyle {\begin{aligned}y[n]=\left(\sum _{k}x_{k}[n-kL]\right)*h[n]&=\sum _{k}\left(x_{k}[n-kL]*h[n]\right)\\&=\sum _{k}y_{k}[n-kL],\end{aligned}}}$

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

dónde :

• DFT _N e IDFT _N se refieren a la transformada discreta de Fourier y su inversa, evaluadas sobre${\displaystyle N}$puntos discretos y
• ${\displaystyle L}$se elige habitualmente de tal manera que${\displaystyle N=L+M-1}$es una potencia entera de 2, y las transformaciones se implementan con el algoritmo FFT , para mayor eficiencia.

A continuación se presenta una representación en pseudocódigo del algoritmo :

( Algoritmo de superposición y suma para convolución lineal ) h = filtro FIR M = longitud(h) Nx = longitud(x) N = 8 × 2^techo( log2(M) ) (8 veces la potencia de dos más pequeña mayor que la longitud del filtro M. Consulte la siguiente sección para una opción ligeramente mejor). step_size = N - (M-1) (L en el texto anterior) H = DFT(h, N) posición = 0 y(1 : Nx + M-1) = 0 mientras posición + tamaño_paso ≤ Nx hacer y(posición+(1:N)) = y(posición+(1:N)) + IDFT(DFT(x(posición+(1:tamaño_paso)), N) × H) posición = posición + tamaño_de_paso fin

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

Por ejemplo, cuando${\displaystyle M=201}$y${\displaystyle N=1024,}$La ecuación 3 es igual a${\displaystyle 13.67,}$mientras que la evaluación directa de la ecuación 1 requeriría hasta${\displaystyle 201}$multiplicaciones complejas por muestra de salida, siendo el peor caso cuando ambos${\displaystyle x}$y${\displaystyle h}$son de valor complejo. Tenga en cuenta también que para cualquier dado${\displaystyle M,}$La ecuación 3 tiene un mínimo con respecto a${\displaystyle N.}$ La figura 2 es un gráfico de los valores de${\displaystyle N}$que minimizan la ecuación 3 para un rango de longitudes de filtro (${\displaystyle M}$).

En lugar de la ecuación 1 , también podemos considerar aplicar la ecuación 2 a una secuencia larga de longitud${\displaystyle N_{x}}$muestras. El número total de multiplicaciones complejas sería:

${\displaystyle N_{x}\cdot (\log _{2}(N_{x})+1).}$

En comparación, el número de multiplicaciones complejas requeridas por el algoritmo en pseudocódigo es:

${\displaystyle N_{x}\cdot (\log _{2}(N)+1)\cdot {\frac {N}{N-M+1}}.}$

Por lo tanto, el costo del método de superposición-adición se escala casi como${\displaystyle O\left(N_{x}\log _{2}N\right)}$mientras que el costo de una sola convolución circular grande es casi${\displaystyle O\left(N_{x}\log _{2}N_{x}\right)}$En la Figura 3, generada mediante simulación con MATLAB , se comparan ambos métodos . Las curvas de nivel representan la relación constante entre los tiempos de ejecución de cada método. Cuando el método de superposición y suma es más rápido, la relación supera 1, llegando incluso a valores de hasta 3.

• Método de superposición y guardado
• Convolución circular#Ejemplo

• Oppenheim, Alan V.; Schafer, Ronald W. (1975). Procesamiento digital de señales . Englewood Cliffs, NJ: Prentice-Hall. ISBN 0-13-214635-5.
• Hayes, M. Horace (1999). Procesamiento digital de señales . Serie Schaum's Outline. Nueva York: McGraw Hill. ISBN 0-07-027389-8.
• Senobari, Nader Shakibay; Funning, Gareth J.; Keogh, Eamonn; Zhu, Yan; Yeh, Chin-Chia Michael; Zimmerman, Zachary; Mueen, Abdullah (2019). "Correlación cruzada supereficaz (SEC-C): un código de filtrado adaptado rápido adecuado para ordenadores de sobremesa" (PDF) . Seismological Research Letters . 90 (1): 322–334 . doi : 10.1785/0220180122 . ISSN 0895-0695 .