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.- If we don't add enough zeros, some of our convolution terms ``wrap around'' and add back upon others (due to modulo indexing).
- This can be called
*time domain aliasing*.

- 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.

[Comment on this page via email]

Copyright ©

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

[Automatic-links disclaimer]