9.3 The convolution theorem

We have defined convolution and seen that it generalizes difference equations, but it is not yet obvious that we have made progress toward our stated goal of sculpting content in the frequency domain. So far everything has happened in the time domain. The bridge between the two is one of the most important results in all of signal processing.

Theorem 2 (The convolution theorem)

Convolution in the time domain corresponds to multiplication in the frequency domain. If \(\purple{y} = \red{h} * \blue{x}\), then their DFTs satisfy

\[\purple{Y[k]} = \red{H[k]} \cdot \blue{X[k]}\]

at every frequency bin \(k\).

A technical caveat: the theorem as stated holds exactly for circular convolution, in which the index \(n-k\) wraps around modulo \(N\) rather than running off the end into assumed zeros. The ordinary (linear) convolution we defined agrees with the circular version only when both signals are first zero-padded to length \(N + K - 1\), which is exactly what the fast-convolution recipe below does.

A proof is beyond the scope of this book (see this page from [Smi07b], or [McF23]), but the consequence is exactly what we were after. Convolving with a filter \(\red{h}\) multiplies the spectrum of the input by \(\red{H}\), the spectrum of the filter. So to boost or attenuate particular frequencies, we simply design a filter whose spectrum \(\red{H}\) has the desired shape. This is precisely the frequency-sculpting picture from the start of the chapter, now made concrete: \(\purple{|Y[k]|} = \red{|H[k]|} \cdot \blue{|X[k]|}\).

Let’s draw an analogy to something we have already seen. Back in Chapter 4 we shaped a sound’s loudness over time by multiplying it by an amplitude envelope. The convolution theorem says that a filter is, in effect, an envelope applied in the frequency domain: \(H\) is a shape we multiply the spectrum by, sculpting which frequencies come through, exactly as an amplitude envelope sculpts which moments in time come through.

The theorem also has a dual, obtained by swapping the roles of the two domains:

Theorem 3 (The convolution theorem (dual))

Multiplication in the time domain corresponds to convolution in the frequency domain. If \(\purple{y} = \red{h} \cdot \blue{x}\) is the element-wise product of two signals, then their DFTs satisfy

\[\purple{Y[k]} \;\propto\; \big(\red{H} * \blue{X}\big)[k]\]

at every frequency bin \(k\). Accordingly, the spectrum of a product is (up to a constant scale factor) the convolution of the spectra.

This dual form connects to several phenomena we have already encountered, each an instance of “multiplying in time smears in frequency”:

1. In Chapter 7, sampling was modeled as multiplying a signal by an impulse train in time. In frequency, this convolves the spectrum with an impulse train, producing the spectral copies that lead to aliasing.

2. In Chapter 8, windowing a signal to a finite length meant multiplying by a rectangular window in time. In frequency, this convolves the spectrum with the window’s spectrum, producing spectral leakage.

3. In Chapter 6, ring modulation multiplied one sinusoid by another in time. In frequency, this convolves their spectra, creating the sidebands at sum and difference frequencies.

Seen this way, three seemingly different effects from three different chapters are all consquences of the convolution theorem.

Leveraging the convolution theorem

The convolution theorem is not just conceptually satisfying, it is also enormously practical. Recall that directly convolving two signals of length \(N\) costs \(O(N^2)\) operations. The theorem offers a shortcut. Since convolution in time equals multiplication in frequency, we can convolve by transforming to the frequency domain, multiplying, and transforming back:

\[\begin{split} \begin{aligned} \red{h} * \blue{x} &= \texttt{IDFT}\big(\texttt{DFT}(\red{h}) \cdot \texttt{DFT}(\blue{x})\big) \\ &= \texttt{IFFT}\big(\texttt{FFT}(\red{h}) \cdot \texttt{FFT}(\blue{x})\big). \end{aligned} \end{split}\]

The first line is just the convolution theorem read backwards, using the invertibility of the DFT from Chapter 8. The second line swaps in the fast Fourier transform (and its equally fast inverse) for the same result. Now count the cost: two forward FFTs and one inverse FFT are each \(O(N \log N)\), and the sample-by-sample multiplication in between is only \(O(N)\). The total is

\[O(N \log N) + O(N \log N) + O(N \log N) = O(N \log N),\]

a massive improvement over the \(O(N^2)\) of direct convolution.

In practice, for a filter of length \(K\) and a signal of length \(N\), we first zero-pad both to a common length of at least \(N + K - 1\) (so the circular wraparound of the DFT does not corrupt the result), rounded up to the nearest power of two so the FFT is maximally efficient.

Note

The constant factors still favor direct time-domain convolution for short filters, but frequency-domain convolution wins as the filter grows, and for long filters it wins by a landslide.