Método overlap-save
Overlap–save é o nome tradicional de uma maneira eficiente de avaliar a convolução discreta entre um sinal muito longo e um filtro de resposta ao impulso finito (FIR) :
![{\textstyle x[n]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/298900271d430cdc218444544f75fc47ba51654d)
![{\textstyle h[n]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1c36d61d1249fb227d93ff6e0abb8a15903c1971)
![{\displaystyle y[n]=x[n]*h[n]\triangleq \sum _{m=-\infty }^{\infty }h[m]\cdot x[n-m]=\sum _{m=1}^{M}h[m]\cdot x[n-m]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/41b8418edd0e4d7996962c641178870d5c518ea4)
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:
![{\displaystyle x_{k}[n]\ \triangleq {\begin{cases}x[n+kL]&1\leq n\leq L+M-1\\0&{\textrm {otherwise}}.\end{cases}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4579b71aafc7c9dfa9ec94b727ea93cab0b50723)
![{\displaystyle y_{k}[n]\ \triangleq \ x_{k}[n]*h[n]=\sum _{m=1}^{M}h[m]\cdot x_{k}[n-m].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8fd9d2fd0bbbfdd29588f4269fa83eb6a5c6bb78)
Então, para kL + M ≤ n ≤ kL + L + M - 1, e equivalente M ≤ n - kL ≤ L + M - 1, podemos escrever:
![{\displaystyle y[n]=\sum _{m=1}^{M}h[m]\cdot x_{k}[n-kL-m]\ \ \triangleq \ \ y_{k}[n-kL].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a7c079ad24edca1c7175376f25063e1a0b6e3c26)
A tarefa é assim reduzida para calcular yk[n], para M ≤ n ≤ L + M − 1.
Agora observe que se periodicamente estendermos xk[n] com o período N ≥ L + M − 1, de acordo com:
![{\displaystyle x_{k,N}[n]\ \triangleq \ \sum _{\ell =-\infty }^{\infty }x_{k}[n-\ell N],}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5d47dd2d227e66f4bfcefd7e64a245876fb0f04e)
as convoluções e 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 com 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.
![{\displaystyle x_{k}[n]\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dc9d9200977fc896075d42002a94bfb133d0dd0a)
![{\displaystyle h[n]\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/657f337326ef0221b43c4ae709e54fe608a6a527)
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:
![{\displaystyle y_{k}[n]=\scriptstyle {\text{DFT}}^{-1}\displaystyle (\ \scriptstyle {\text{DFT}}\displaystyle (x_{k}[n])\cdot \scriptstyle {\text{DFT}}\displaystyle (h[n])\ ),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7a07179396e1465e2eee6dc59fa2fd027480c2e3)
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
editarFrerking, Marvin (1994). Digital Signal Processing in Communication Systems. New York: Van Nostrand Reinhold. ISBN 0442016166.