Circular Convolution and Discrete Fourier Transform
Forfatter
Frank the Bunny
Sidst opdateret
9 år siden
Licens
Creative Commons CC BY 4.0
Resumé
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}