Circular Convolution and Discrete Fourier Transform
Author
Frank the Bunny
Last Updated
9 years ago
License
Creative Commons CC BY 4.0
Abstract
Prove the circular convolution property of Discrete Fourier Transform (DFT)
Use ebgaramond package
Prove the circular convolution property of Discrete Fourier Transform (DFT)
Use ebgaramond package
\documentclass{article}
\usepackage{fullpage}
\usepackage{amsmath,amssymb}
\usepackage{ebgaramond}
% complex conjugate
\newcommand{\conj}[1]{\ensuremath{\overline{#1}}}
% modulo n operator
\newcommand{\braket}[1]{\ensuremath{\langle{#1}\rangle}}
% Blackboard bold of C
\newcommand{\Cbb}{\ensuremath{\mathbb{C}}}
\begin{document}
\title{Circular Convolution and Discrete Fourier Transform}
\author{Frank the Giant Bunny}
\maketitle
\thispagestyle{empty}
Consider three vectors $a,b,c\in\Cbb^n$ where $c$
is a \emph{circular convolution} of $a$ and $b$:
\begin{equation*}
c_i = \sum_{k=0}^{n-1}a_kb_{\braket{i-k}_n}
\quad
\text{for $i\in\{0,1,\cdots,n-1\}$}
\end{equation*}
where $\braket{\ell}_n$ is a modulo operator.
Define another vectors $\alpha$, $\beta$, and $\gamma$
as the \emph{Discrete Fourier Transform} (DFT)
of $a$, $b$, and $c$
\begin{equation*}
\alpha_j = \frac{1}{\sqrt n}\sum_{i=0}^{n-1}a_i\conj{\omega}^{ij},
\quad
\beta_j = \frac{1}{\sqrt n}\sum_{i=0}^{n-1}b_i\conj{\omega}^{ij},
\quad\text{and}\quad
\gamma_j = \frac{1}{\sqrt n}\sum_{i=0}^{n-1}c_i\conj{\omega}^{ij},
\end{equation*}
where $\omega=e^{\iota 2\pi/n}$ is the
\emph{primitive $n^{\mathrm{th}}$ root of unity} and
$\conj\omega$ is its complex conjugate.
Then the \emph{circular convolution property} states that $\gamma$
is obtained by the entry-wise product of $\alpha$ and $\beta$.
This is easily seen by rearranging terms in summations.
\begin{alignat*}{2}
\gamma_j
&=
\frac{1}{\sqrt n}\sum_{i=0}^{n-1}c_i{\conj\omega}^{ij}
&\quad\text{by definition of DFT}
\\
&=
\frac{1}{\sqrt n}\sum_{i=0}^{n-1}
\left(\sum_{k=0}^{n-1}a_k b_{\braket{i-k}_n}\right)
{\conj\omega}^{ij}
&\quad\text{by definition of $c_i$}
\\
&=
\frac{1}{\sqrt n}\sum_{k=0}^{n-1}a_k
\left(\sum_{i=0}^{n-1}b_{\braket{i-k}_n}\right)
{\conj\omega}^{ij}
&\quad\text{by rearranging terms}
\\
&=
\frac{1}{\sqrt n}\sum_{k=0}^{n-1}a_k{\conj\omega}^{kj}
\left(
\sum_{i=0}^{n-1}b_{\braket{i-k}_n}{\conj\omega}^{(i-k)j}
\right)
&\quad\text{by decomposing ${\conj\omega}^{ij}$}
\\
&=
\alpha_j
\left(
\sum_{i=0}^{n-1}b_{\braket{i-k}_n}{\conj\omega}^{(i-k)j}
\right)
&\quad\text{by definition of DFT}
\\
&=
\alpha_j
\left(
\sum_{i=0}^{n-1}b_{\braket{i-k}_n}{\conj\omega}^{\braket{i-k}_n j}
\right)
&\quad\text{${\conj\omega}^n=1$}
\\
&=
\sqrt{n}\alpha_j
\left(
\frac{1}{\sqrt n}\sum_{i=0}^{n-1}b_{\braket{i-k}_n}
{\conj\omega}^{\braket{i-k}_n j}
\right)
&\quad\text{by decomposing $1$}
\\
&=
\sqrt{n}\alpha_j\beta_j
&\quad\text{by definition of DFT}
\end{alignat*}
\end{document}