Método de superposición y guardado

En el procesamiento de señales , el método overlap-save es el nombre tradicional para una forma eficiente de evaluar la convolución discreta entre una señal muy larga.${\displaystyle x[n]}$y un filtro de respuesta de impulso finito (FIR).${\displaystyle h[n]}$:

donde h [ m ] = 0 para m fuera de la región [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 calcular segmentos cortos de y [ n ] de longitud arbitraria L y concatenarlos. Esto requiere segmentos de entrada más largos que se superpongan al siguiente. Los datos superpuestos se "guardan" y se utilizan una segunda vez. ^{[ 1 ]} Primero describimos este proceso con una convolución convencional para cada segmento de salida. Luego describimos cómo reemplazar esa convolución con un método más eficiente.

Consideremos un segmento que comienza en n = kL  + M , para cualquier entero k , y definamos : 

${\displaystyle x_{k}[n]\ \triangleq {\begin{cases}x[n+kL],&1\leq n\leq L+M-1\\0,&{\textrm {en otro caso}}.\end{cases}}}$

${\displaystyle y_{k}[n]\ \triangleq \ x_{k}[n]*h[n]=\sum _{m=1}^{M}h[m]\cdot x_{k}[nm].}$

Entonces, para${\displaystyle kL+M+1\leq n\leq kL+L+M}$y de forma equivalente${\displaystyle M+1\leq n-kL\leq L+M}$, podemos escribir:

${\displaystyle y[n]=\sum _{m=1}^{M}h[m]\cdot x_{k}[n-kL-m]\ \ \triangleq \ \ y_{k}[n-kL].}$

Con la sustitución${\displaystyle j=n-kL}$La tarea se reduce a calcular${\displaystyle y_{k}[j]}$para${\displaystyle M+1\leq j\leq L+M}$Estos pasos se ilustran en las tres primeras trazas de la Figura 1, excepto que la porción deseada de la salida (tercera traza) corresponde ^a 1  ≤ j ≤ L. ^{[ B} ]   

Si extendemos periódicamente x _k [ n ] con un período N  ≥ L + M − 1, según :     

${\displaystyle x_{k,N}[n]\ \triangleq \ \sum _{\ell =-\infty }^{\infty }x_{k}[n-\ell N],}$

las convoluciones ${\displaystyle (x_{k,N})*h\,}$ y ${\displaystyle x_{k}*h\,}$ son equivalentes en la región${\displaystyle M+1\leq n\leq L+M}$Por lo tanto, basta con calcular la convolución circular (o cíclica) de N puntos de${\displaystyle x_{k}[n]\,}$con${\displaystyle h[n]\,}$ en la región [1, N ]. La subregión [ M + 1, L + M ] se agrega al flujo de salida y los demás valores se descartan . La ventaja es que la convolución circular se puede calcular de manera más eficiente que la convolución lineal, según el teorema de convolución circular :      

dónde :

• DFT _N e IDFT _N se refieren a la transformada discreta de Fourier y su inversa, evaluadas sobre N puntos discretos, y
• Habitualmente, L se elige de forma que N = L+M-1 sea una potencia entera de 2, y las transformadas se implementan con el algoritmo FFT , para mayor eficiencia.
• Los efectos de borde inicial y final de la convolución circular se superponen y se suman, ^{[ C ]} y posteriormente se descartan. ^{[ D ]}

( Algoritmo de superposición y ahorro para convolución lineal ) h = Respuesta_impulso_FIR M = longitud(h) superposición = M − 1 N = 8 × superposición (ver la siguiente sección para una mejor opción) step_size = N − overlap H = DFT(h, N) posición = 0 mientras posición + N ≤ longitud(x) yt = IDFT(DFT(x(posición+(1:N))) × H) y(posición+(1:tamaño_paso)) = yt(M : N) (descartar M−1 valores de y) 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. ^{[ E ]} 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 ambas${\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-ahorro 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)}$.

Superposición-descarte ^{[ 2 ]} y Superposición-desechamiento ^{[ 3 ]} son ​​etiquetas menos comunes para el mismo método descrito aquí. Sin embargo, estas etiquetas son en realidad mejores (que superposición-guardado ) para distinguir de superposición-adición , porque ambos métodos "guardan", pero solo uno descarta. "Guardar" simplemente se refiere al hecho de que se necesitan M  −  1 muestras de entrada (o salida) del segmento k para procesar el segmento k + 1.

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

• Dra. Deepa Kundur, Superposición Añadir y Superposición Guardar , Universidad de Toronto