convolution theorem
Table of Contents
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.