Given $f(n) \ftp F(\omega)$ and $g(n) \ftp G(\omega)$, what is the transform of a convolved signal $(f*g)(n)$?


We can use a combination of the convolution sum and the DTFT:

\begin{align*}
H(\omega) &= \sum \limits_{n=-\infty}^{\infty} h(n) e^{-i\omega n} \\
H(\omega) &= \sum \limits_{n=-\infty}^{\infty} (f*g)(n) e^{-i\omega n} \\
H(\omega) &= \sum \limits_{n=-\infty}^{\infty} \lr{\sum \limits_{\ell = -\infty}^{\infty}f(\ell)g(n-\ell)}e^{-i\omega n} \\
H(\omega) &= \sum \limits_{\ell=-\infty}^{\infty} \sum \limits_{n = -\infty}^{\infty}f(\ell)g(n-\ell)e^{-i\omega n} \quad \mbox{swap the summations}\\
H(\omega) &= \sum \limits_{\ell=-\infty}^{\infty} f(\ell)\sum \limits_{m = -\infty}^{\infty}g(m)e^{-i\omega (m+\ell)} \quad \mbox{let } m = n -\ell\\
H(\omega) &= \sum \limits_{\ell=-\infty}^{\infty} f(\ell)\sum \limits_{m = -\infty}^{\infty}g(m)e^{-i\omega m} e^{-i\omega\ell} \\
H(\omega) &= \sum \limits_{\ell=-\infty}^{\infty} f(\ell)e^{-i\omega\ell} \sum \limits_{m = -\infty}^{\infty}g(m)e^{-i\omega m} \\
H(\omega) &= F(\omega)G(\omega)
\end{align*}

Therefore we can conclude that convolution in the time-domain corresponds to multiplication in the frequency domain:

\begin{nicebox}
$$ (f*g)(n) \ftp F(\omega)G(\omega) $$
\end{nicebox}


Convolution