Overlap–save method: Difference between revisions

Revision as of 18:45, 25 December 2019

Revision as of 11:25, 9 January 2020

Line 40:

==Pseudocode==

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

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

h := FIR_impulse_response

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

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

overlap := M − 1

L = M; // >=1 is OK

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

P = O + L;

step_size := N − overlap

H := DFTFFT(h, NP); // just calc once

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

position := 0

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

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

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

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

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

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

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

position := position + step_size

idx = idx + L;

'''end'''

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

==Efficiency==