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

FFT Convolution

The convolution theorem $ h*x \leftrightarrow H \cdot X$ shows us that there are two ways to perform circular convolution.

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 $ m=0$ to $ \infty$ ).

Question: How many zeros do we need to add?

\epsfig{file=eps/convwaves.eps,width=\textwidth }

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

[Comment on this page via email]

``Review of the Discrete Fourier Transform (DFT)'', by Julius O. Smith III, (From Lecture Overheads, Music 421).
Copyright © 2020-06-27 by Julius O. Smith III
Center for Computer Research in Music and Acoustics (CCRMA),   Stanford University
CCRMA  [Automatic-links disclaimer]