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) : 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: Então, para kL + M ≤ n ≤ kL + L + M - 1, e equivalente M ≤ n - kL ≤ L + M - 1, podemos escrever: 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: 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. 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: 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.