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

donde para fuera de la región   Este artículo utiliza notaciones abstractas comunes, como o en las que se entiende que las funciones deben considerarse en su totalidad, en lugar de en instantes específicos (ver Convolución#Notación ). ${\displaystyle h[m]=0}$${\estilo de visualización m}$${\estilo de visualización [1,M].}$${\textstyle 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 con segmentos cortos de :${\displaystyle h[n]}$${\displaystyle x[n]}$

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

donde es una longitud de segmento arbitraria. Entonces :${\estilo de visualización L}$

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

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

${\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 es cero fuera de la región Y para cualquier parámetro ^[A] es equivalente a la convolución circular de punto dentro de la regió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]\ \triánguloq \ x_{k}[n]*h[n]\,}$${\displaystyle [1,L+M-1].}$${\displaystyle N\geq L+M-1,\,}$${\displaystyle N}$${\displaystyle x_{k}[n]\,}$${\displaystyle h[n]\,}$${\displaystyle [1,N].}$

dónde :

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

El siguiente es un pseudocódigo del algoritmo :

( Algoritmo de superposición y adición para convolución lineal )
h = filtro FIR
M = longitud(h)
Nx = longitud(x)
N = 8 × 2^ceiling( log2(M) )      (8 veces la potencia más pequeña de dos 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_de_paso ≤ Nx hacer
    y(posición+(1:N)) = y(posición+(1:N)) + IDFT(DFT(x(posición+(1:tamaño_de_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 la cantidad de multiplicaciones complejas por muestra de salida es aproximadamente :

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

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

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

Comparativamente, el número de multiplicaciones complejas requeridas por el algoritmo de 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 escala casi igual que el costo de una sola convolución circular grande es casi . Los dos métodos también se comparan en la Figura 3, creada mediante simulación de Matlab. Los contornos son líneas de proporción constante de los tiempos que lleva realizar ambos métodos. Cuando el método de superposición-adición es más rápido, la proporción supera 1 y se ven proporciones tan altas como 3. ${\displaystyle O\left(N_{x}\log _{2}N\right)}$${\displaystyle O\left(N_{x}\log _{2}N_{x}\right)}$

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

• Oppenheim, Alan V.; Schafer, Ronald W. (1975). Procesamiento de señales digitales . Englewood Cliffs, Nueva Jersey: Prentice-Hall. ISBN 0-13-214635-5.
• Hayes, M. Horace (1999). Procesamiento de señales digitales . 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 supereficiente (SEC-C): un código de filtrado rápido y adaptado adecuado para computadoras de escritorio" (PDF) . Seismological Research Letters . 90 (1): 322–334. doi :10.1785/0220180122. ISSN  0895-0695.