# convolution theorem

Pointwise multiplication in the freq domain is equivalent to circular convolution in the time domain.

\begin{equation} f[n] \circledast g[n] = F^{-1} \{F\{f\} \cdot F\{g\}\} \end{equation}

You can use this to compute linear convolution as well.

## 1. Proof

We are trying to prove that the DFT of the circular convolution is the product of the DFT of each signal.

Let $$f[n]$$ and $$g[n]$$ be sequences of length $$N$$. Let $$y[n] = f[n] \circledast g[n]$$.

From the definition of the circular convolution,

\begin{equation} y[n] = \sum_{k = 0}^{N-1} f[k] \cdot g[n-k] \end{equation}

and so the DFT of $$y[n]$$, $$Y[m]$$ is

\begin{align*} Y[m] &= F\{ \sum_{k = 0}^{N-1} f[k] \cdot g[n-k] \} \\ &= \sum_{k = 0}^{N-1} f[k] \cdot G[n-k] &&\text{DFT linearity} \\ &= \sum_{k = 0}^{N-1} f[k] \cdot G[m] \cdot e^{-j2\pi \frac{m}{N} k} &&\text{DFT shift property} \\ &= G[m] \cdot \sum_{k = 0}^{N-1} f[k] \cdot e^{-j2\pi \frac{m}{N} k} \\ &= G[m] \cdot F[m] \end{align*}

Equivalence 3 comes from the DFT shifting theorem.