Convolution and the Frequency Domain

This brings us to the most important theorem in digital signal processing, one that is used more than any other operation after the Fourier transform.

The DFT of convolution output

To view the effect of convolution in the frequency domain, we take the Fourier transform of the resultant signal. Keep in mind that for the DFT, the flipping and time-shifting operations need to be circular. In what follows, we consider a conventional Fourier transform for simplicity.

The $y[n]$ output of convolution between the two signals $x[n]$ and $h[n]$ is given by:

$$y[n]= \sum_m x[m]h[n-m]$$

Applying the Fourier transform, we get:

$$\begin{align*} Y(\omega) &= \sum_n y[n]e^{-j\omega n}\\ &= \sum_n \sum_m x[m]h[n-m]e^{-j\omega n} \end{align*}$$

From here, we transform the variable as follows:

$$\begin{align*} Y(\omega) &= \sum_n \sum_m x[m]h[n-m]e^{-j\omega (n-m+m)}\\ &= \sum_n \sum_m x[m]h[n-m]e^{-j\omega (n-m)}e^{-j\omega m} &= \sum_m x[m]e^{-j\omega m}\sum_n h[n-m]e^{-j\omega (n-m)} \end{align*}$$

Plug in a new variable $(q=n-m)$, and this can be factored in two Fourier transforms as:

$$\begin{align*} Y(\omega) &= \sum_m x[m]e^{-j\omega m}\sum_q h[q]e^{-j\omega q}\\ &= X(\omega)\cdot H(\omega) \end{align*}$$

As a consequence, we can describe the most fundamental DSP result like this: Convolution in the time domain between two signals induces their multiplication in the frequency domain.

In terms of the discrete Fourier transform, it will be a circular convolution between signals that generate a product in spectral bins.