Método overlap-save

Uma sequência de 4 gráficos representando um ciclo do algoritmo de convolução Overlap-save.

Overlap–save é o nome tradicional de uma maneira eficiente de avaliar a convolução discreta entre um sinal muito longo $x[n]$e um filtro de resposta ao impulso finito (FIR) $h[n]$:

$y[n]=x[n]*h[n]\triangleq \sum _{m=-\mathrm{\infty }}^{\mathrm{\infty }}h[m]\cdot x[n-m]=\sum _{m=1}^{M}h[m]\cdot x[n-m]$

onde h[m]=0 para m fora da região [1, M].

O conceito é calcular segmentos curtos de y[n] de um comprimento arbitrário L e concatenar os segmentos juntos. Considere um segmento que começa com n = kL + M, para qualquer inteiro k e defina:

$x_k[n]\triangleq \{\begin{array}{cc}x[n+kL]& 1\le n\le L+M-1\\ 0& \text{otherwise}.\end{array}$

$y_k[n]\triangleq x_k[n]*h[n]=\sum _{m=1}^{M}h[m]\cdot x_k[n-m].$

Então, para kL + M ≤ n ≤ kL + L + M - 1, e equivalente M ≤ n - kL ≤ L + M - 1, podemos escrever:

$y[n]=\sum _{m=1}^{M}h[m]\cdot x_k[n-kL-m]\triangleq y_k[n-kL].$

A tarefa é assim reduzida para calcular y_k[n], para M  ≤  n  ≤  L + M − 1.

Agora observe que se periodicamente estendermos x_k[n] com o período N  ≥  L + M − 1, de acordo com:

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

as convoluções $(x_{k,N})*h$e $x_k*h$são equivalentes na região M  ≤  n  ≤  L + M − 1. Assim, é suficiente calcular a convolução circular (ou cíclica) de N pontos de $x_k[n]$com $h[n]$na região[1, N]. A sub-região [M, L + M − 1] é anexada ao fluxo de saída e os outros valores são descartados.

A vantagem é que a convolução circular pode ser calculada de maneira muito eficiente como segue, de acordo com o teorema da convolução circular:

$y_k[n]={\text{DFT}}^{-1}(\text{DFT}(x_k[n])\cdot \text{DFT}(h[n])),$

onde:

• DFT e DFT − 1 referem-se à transformada discreta de Fourier e à transformada discreta de Fourier inversa, respectivamente, avaliadas sobre N pontos discretos, e
• N é habitualmente escolhido para ser um inteiro de potência-2, que otimiza a eficiência do algoritmo FFT.
• N otimizado está no intervalo [4M, 8M].
• Com convolução circular, o primeiro valor de saída é uma média ponderada das últimas amostras M-1 do segmento de entrada (e a primeira amostra do segmento). As próximas saídas M-2 são médias ponderadas do começo e do fim do segmento. O valor de saída Mth é o primeiro que combina apenas amostras do início do segmento.

Referências

Frerking, Marvin (1994). Digital Signal Processing in Communication Systems. New York: Van Nostrand Reinhold. ISBN 0442016166.