Next  |  Prev  |  Up  |  Top  |  JOS Index  |  JOS Pubs  |  JOS Home  |  Search

### FFT Convolution

The convolution theorem shows us that there are two ways to perform circular convolution.

• direct calculation of the summation
• frequency-domain approach    lg
• Fourier Transform both signals
• Perform term by term multiplication of the transformed signals
• Inverse transform the result to get back to the time domain

Remember ... this still gives us cyclic convolution

Idea: If we add enough trailing zeros to the signals being convolved, we can get the same results as in acyclic convolution (in which the convolution summation goes from to ).

Question: How many zeros do we need to add?

• If we perform an acyclic convolution of two signals, and , with lengths and , the resulting signal is length .

• Therefore, to implement acyclic convolution using the DFT, we must add enough zeros to and so that the cyclic convolution result is length or longer.

• We typically zero-pad even further (to the next power of 2) so we can use the Cooley-Tukey FFT for maximum speed

A sampling-theorem based insight:

Zero-padding in the time domain results in more samples (closer spacing) in the frequency domain. This can be thought of as a higher sampling rate' in the frequency domain. If we have a high enough frequency-domain sampling rate, we can avoid time domain aliasing.

Next  |  Prev  |  Up  |  Top  |  JOS Index  |  JOS Pubs  |  JOS Home  |  Search