### Acyclic Convolution

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

*dual*of the usual sampling theorem.

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.

**Next Section:**

Example of Overlap-Add Convolution

**Previous Section:**

STFT of COLA Decomposition