Overlap–save method: Difference between revisions

Revision as of 11:25, 9 January 2020

Revision as of 14:20, 9 January 2020

Line 40:

==Pseudocode==

<font color=green>(''Overlap-save algorithm for linear convolution'')</font>

h := FIR_impulse_response

//////// revised by fantastic ////////

N = length(x), M := length(h)

overlap := M − 1

O = M – 1; // overlap length must be M-1

N := 4 × overlap <span style="color:green;">(or a nearby power-of-2)</span>

L = M; // >=1 is OK

step_size := N − overlap

P = O + L;

H := FFTDFT(h, PN); // just calc once

position := 0

idx = - (O - 1); // starting index which is offset M-1 in matlab

'''while''' (idx <= N)

'''while''' position + N ≤ length(x) '''do'''

i1 = max(1, idx); // must be >= 1

yt = IDFT(DFT(x(1 i2+ =position : min(N, idx+P-1 position); //, mustN) be× <=H, N)

y(1 + position : step_size + position) = yt(M : N) # discard M−1 y-values

yt = IFFT( FFT(x(i1:i2), P).*H, P );

position := position + step_size

y(idx:idx+P-M) = yt(M:P); // discard first M-1 values and concatenate the remaining

'''end'''

idx = idx + L;

'''end'''

y = y(1:M+N-1); // the first M+N-1 values are the convolution result

==Efficiency==