Overlap–add method: Difference between revisions

Revision as of 23:45, 2 November 2020

Revision as of 05:49, 27 December 2020

Line 66:

When the DFT and IDFT are implemented by the FFT algorithm, the pseudocode above requires about {{nowrap|'''N (log₂(N) + 1)'''}} complex multiplications for the FFT, product of arrays, and IFFT.{{efn-ua

|1=Cooley–Tukey FFT algorithm for N=2^k needs (N/2) log₂(N) – see [[Fast Fourier transform#Definition and speed|FFT – Definition and speed]]

}} Each iteration produces {{nowrap|'''N-M+1'''}} output samples, so the number of complex multiplications per output sample is about''':'''