Overlap–save method: Difference between revisions

Revision as of 18:26, 6 May 2019

Revision as of 16:01, 16 December 2019

Line 40:

==Pseudocode==

<spanfont style="color:=green;">(''Overlap–saveOverlap-save algorithm for linear convolution'')</spanfont>

<code>

<span style="color:green;">(''Overlap–save algorithm for linear convolution'')</span>

h = FIR_impulse_response

M = length(h)

Line 54 ⟶ 53:

position = position + step_size

'''end'''

</code>

==Efficiency==

When the DFT and its inverse is implemented by the FFT algorithm, the pseudocode above requires about '''N log₂(N) + N''' complex multiplications for the FFT, product of arrays, and IFFT.<ref group{{efn-ua
|1=note>Cooley–Tukey FFT algorithm for N=2^k needs (N/2) log₂(N) – see [[Fast Fourier transform#Definition and speed|FFT – Definition and speed]]</ref>
}} Each iteration produces '''N-M+1''' output samples, so the number of complex multiplications per output sample is about''':'''

{{NumBlk|:|<math>\frac{N \log_2(N) + N}{N-M+1}.\,</math>|{{EquationRef|Eq.2}}}}

Line 67:

===Extending overlap–save===

The overlap–save algorithm may be extended to include other common operations of a system:<ref group=note>{{efn-ua
|[[#refCarlin|Carlin et al. 1999]], p 31, col 20.</ref>
}}<ref>{{Citation |last=Borgerding |first=Mark |title=Turning Overlap–Save into a Multiband Mixing, Downsampling Filter Bank |journal=IEEE Signal Processing Magazine |issue= March 2006 |pages=158–161 |year=2006 |url=http://www.3db-labs.com/01598092_MultibandFilterbank.pdf}}</ref>

* additional channels can be processed more cheaply than the first by reusing the forward FFT

Line 77 ⟶ 79:

==Notes==

{{notelist-ua}}

{{reflist|group=note}}

==References==