Getting back to acyclic convolution, we may write it as

Since is time limited to (or ), can be sampled at intervals of without time aliasing. If is time-limited to , then will be time limited to . Therefore, we may sample at intervals of

(9.22) |

or less along the unit circle. This is the

We conclude that practical FFT acyclic convolution may be carried out using an FFT of any length satisfying

(9.23) |

where is the frame size and is the filter length. Our final expression for is

where is the length DFT of the zero-padded frame , and is the length DFT of , also zero-padded out to length , with .

Note that the terms in the outer sum *overlap* when
even if
. In general, an LTI filtering by
increases
the amount of overlap among the frames.

This completes our derivation of FFT convolution between an indefinitely long signal and a reasonably short FIR filter (short enough that its zero-padded DFT can be practically computed using one FFT).

The fast-convolution processor we have derived is a special case of
the *Overlap-Add* (OLA) method for short-time Fourier analysis,
modification, and resynthesis. See [7,9] for more details.

[How to cite this work] [Order a printed hardcopy] [Comment on this page via email]

Copyright ©

Center for Computer Research in Music and Acoustics (CCRMA), Stanford University