Proving the convolution theorem for discrete signals

Sources: Here for the proof and this mathworks page for the destinction between linear and circular convolutions.

Assume that the signals $x$ and $h$ have lengths $P$ and $Q$, respectively, and are non-periodic. Then you typically define a linear convolution as

$y_\mathrm{lin}(n) = \sum_{k=0}^{P+Q-2} h(k) x(n-k) \quad .$

Some of the indices run out of bounds in this sum, so we'll tacitly assume that anything out of bounds is zero. Note that $n$ can run from 0 to $P+Q-2$! In other words, a (non-trivial) linear convolution has a longer output than the input. Our definition nicely describes a tapped delay line. The extra samples are the input and output transients.

For periodic signals, you typically switch to a seperate definition of a convolution. Assume that $x$ and $h$ are of the same length and periodic. Then in the following definition for the circular convolution nothing can run out of bounds (everything is periodic!), and the output will have the same period as the input.

$y(n) = \sum_{k=0}^{N-1}h(k) x(n-k)$

No matter if we are working with periodic signals or non-periodic signals, the discrete Fourier transform and its inverse are always defined as

$X(m) = \sum^{N-1}_{n = 0} x(n) e^{-j \, 2 \pi \, n \, m/N}$

$x(n) = \frac{1}{N} \sum^{N-1}_{m = 0} X(m) e^{-j \, 2 \pi \, m \, n/N}$

So, let's get to work and prove the convolution theorem for periodic signals. We'll start with the definition of the circular convolution

$y(n) = \sum_{k=0}^{N-1}h(k) x(n-k) \quad ,$

and replace $x$ and $h$ with the inverse Fourier transform of $X$ and $H$. Note that we need the periodicity here - otherwise we'd have to ensure that out-of-bound indexes lead to 0! (We'll get to that case in a bit.)

$= \sum_{k=0}^{N-1} \frac{1}{N} \sum^{N-1}_{m = 0} H(m) e^{-j \, 2 \pi \, m \, k/N} \frac{1}{N} \sum^{N-1}_{l = 0} X(l) e^{-j \, 2 \pi \, l \, (n-k)/N}$

Next, we rearrange the sums such that the sum over $k$ is the innermost sum.

$=\frac{1}{N} \sum^{N-1}_{m = 0} H(m) \frac{1}{N} \sum^{N-1}_{l = 0} X(l) \sum_{k=0}^{N-1} e^{-j \, 2 \pi \, m \, k/N} e^{-j \, 2 \pi \, l \, (n-k)/N}$

We can pull out the part of the exponential that does not depend on $k$.

$=\frac{1}{N} \sum^{N-1}_{m = 0} H(m) \frac{1}{N} \sum^{N-1}_{l = 0} X(l) \sum_{k=0}^{N-1} e^{-j \, 2 \pi \,( l n - l k + mk)/N}$

$=\frac{1}{N} \sum^{N-1}_{m = 0} H(m) \frac{1}{N} \sum^{N-1}_{l = 0} X(l) e^{-j \, 2 \pi \, l n /N} \sum_{k=0}^{N-1} e^{-j \, 2 \pi \, k(m-l)/N}$

If $m=l$, then the inner sum evaluates to $N$. For all other cases, you can apply the formula of a geometric series and quickly convince yourself that the result is 0 (the numerator in that formula is alwasy 0 due to the $2\pi$'s). Thus

$=\frac{1}{N} \sum^{N-1}_{m = 0} H(m) \frac{1}{N} \sum^{N-1}_{l = 0} X(l) e^{-j \, 2 \pi \, l n /N} N \delta(m-l)$

$=\frac{1}{N} \sum^{N-1}_{m = 0} H(m) X(m) e^{-j \, 2 \pi \, m n /N}$

And this is just the inverse Fourier transform of the function $Y(m) = H(m) X(m)$. In other words, we just proved that the convolution can be expressed as the inverse Fourier transform of the product of the individual spectra.

With care, we can also apply this to the linear convolution. By appropriately 0-padding both signals, such that they both have a length of $P + Q -1$, we can treat them as periodic functions! The periodicity just doesn't matter, because the ends never meet (there is just enough zeros between them.) We can then apply the convolution theorem and see that it mostly works as expected.

But there is an important side-effect: We cannot apply a pure sine frequency at the input anymore. For any non-trivial filter, the signal has to be 0-padded at the end! So you never get a pure spectrum out - this is because the input and output transients are usually not sinusoid.