discreteFourierMatrixForm.tex

%
% Copyright © 2014 Peeter Joot.  All Rights Reserved.
% Licenced as described in the file LICENSE under the root directory of this GIT repository.
%
%\input{../blogpost.tex}
%\renewcommand{\basename}{discreteFourierMatrixForm}
%\renewcommand{\dirname}{notes/ece1254/}
%%\newcommand{\dateintitle}{}
%%\newcommand{\keywords}{}
%
%\input{../peeter_prologue_print2.tex}
%
%\beginArtNoToc
%
%\generatetitle{Matrix form for discrete time Fourier transform}
%\chapter{Matrix form for discrete time Fourier transform}
\label{chap:discreteFourierMatrixForm}
%
\paragraph{Transform pair}
\index{DFT|see {discrete Fourier transform}}
\index{discrete Fourier transform}
%
In \citep{phy487:discreteFourierTransform} a verification of the discrete Fourier transform pairs was performed.  A much different looking discrete Fourier transform pair is given in \citep{giannini2004NonlinearMicrowaveCircuitDesign} \S A.4.  This transform pair samples the points at what are called the \textAndIndex{Nykvist time instant}s given by
%
\begin{equation}\label{eqndiscreteFourierMatrixForm:20}
t_k = \frac{T k}{2 N + 1}, \qquad k \in [-N, \cdots N]
\end{equation}
%
Note that the endpoints of these sampling points are not \( \pm T/2 \), but are instead at
%
\begin{equation}\label{eqndiscreteFourierMatrixForm:40}
\pm \frac{T}{2} \inv{1 + 1/N},
\end{equation}
%
which are slightly within the interior of the \( [-T/2, T/2] \) range of interest.  The reason for this slightly odd seeming selection of sampling times becomes clear if one calculate the inversion relations.
%
Given a periodic (\( \omega_0 T = 2 \pi \)) bandwidth limited signal evaluated only at the Nykvist times \( t_k \),
%
%\begin{equation}\label{eqndiscreteFourierMatrixForm:60}
\boxedEquation{eqndiscreteFourierMatrixForm:80}{
x(t_k) = \sum_{n = -N}^N X_n e^{ j n \omega_0 t_k},
}
%\end{equation}
%
assume that an inversion relation can be found.  To find \( X_n \) evaluate the sum
%
\begin{equation}\label{eqndiscreteFourierMatrixForm:100}
\begin{aligned}
\sum_{k = -N}^N x(t_k) e^{-j m \omega_0 t_k}
&=
\sum_{k = -N}^N
\lr{
\sum_{n= -N}^N X_n e^{ j n \omega_0 t_k}
}
e^{-j m \omega_0 t_k}
\\ &=
\sum_{n= -N}^N X_n
\sum_{k= -N}^N
e^{ j (n -m )\omega_0 t_k}
\end{aligned}
\end{equation}
%
This interior sum has the value \( 2 N + 1 \) when \( n = m \).  For \( n \ne m \), and
\( a = e^{j (n -m ) \frac{2 \pi}{2 N + 1}} \), this is
%
\begin{equation}\label{eqndiscreteFourierMatrixForm:120}
\begin{aligned}
\sum_{k = -N}^N
e^{ j (n -m )\omega_0 t_k}
&=
\sum_{k = -N}^N
e^{ j (n -m )\omega_0 \frac{T k}{2 N + 1}}
\\ &=
\sum_{k= -N}^N a^k
\\ &=
a^{-N} \sum_{k= -N}^N a^{k+ N}
\\ &=
a^{-N} \sum_{r= 0}^{2 N} a^{r}
\\ &=
a^{-N} \frac{a^{2 N + 1} - 1}{a - 1}.
\end{aligned}
\end{equation}
%
Since \( a^{2 N + 1} = e^{2 \pi j (n - m)} = 1 \), this sum is zero when \( n \ne m \).  This means that
%
\begin{equation}\label{eqndiscreteFourierMatrixForm:140}
\sum_{k = -N}^N
e^{ j (n -m )\omega_0 t_k} = (2 N + 1) \delta_{n,m},
\end{equation}
%
which provides the desired Fourier inversion relation
%
%\begin{equation}\label{eqndiscreteFourierMatrixForm:160}
\boxedEquation{eqndiscreteFourierMatrixForm:180}{
X_m = \inv{2 N + 1} \sum_{k = -N}^N x(t_k) e^{-j m \omega_0 t_k}.
}
%\end{equation}
%
\paragraph{Matrix form}
%
The discrete time Fourier transform has been seen to have the form
%
\begin{subequations}
\begin{equation}\label{eqn:discreteFourierMatrixForm:200}
x_k = \sum_{n = -N}^N X_n e^{ 2 \pi j n k /(2 N + 1)}
\end{equation}
\begin{equation}\label{eqn:discreteFourierMatrixForm:220}
X_n = \inv{2 N + 1} \sum_{k = -N}^N x_k e^{- 2 \pi j n k /(2 N + 1)}.
\end{equation}
\end{subequations}
%
A matrix representation of this form is desired.  Let
%
\begin{subequations}
\begin{equation}\label{eqndiscreteFourierMatrixForm:240}
\Bx =
\begin{bmatrix}
x_{-N} \\
\vdots \\
x_0 \\
\vdots \\
x_{N}
\end{bmatrix}
\end{equation}
\begin{equation}\label{eqndiscreteFourierMatrixForm:260}
\BX =
\begin{bmatrix}
X_{-N} \\
\vdots \\
X_0 \\
\vdots \\
X_{N}
\end{bmatrix}
\end{equation}
\end{subequations}
%
\Cref{eqn:discreteFourierMatrixForm:200} written out in full is
\begin{equation}\label{eqn:discreteFourierMatrixForm:280}
\begin{aligned}
x_k
&= X_{-N} e^{ -2 \pi j N k /(2 N + 1)} \\
&+ X_{1-N} e^{ -2 \pi j \lr{N-1} k /(2 N + 1)}  \\
&+ \cdots \\
&+ X_0  \\
&+ \cdots \\
&+ X_{N-1} e^{ 2 \pi j \lr{N-1} k /(2 N + 1)}  \\
&+ X_N e^{ 2 \pi j N k /(2 N + 1)}
\end{aligned}
\end{equation}
%
Following the FFT discussion in \citep{press1996numerical}, let
\( W = e^{ 2 \pi j /(2 N + 1) } \).  The matrix relation is
%
\begin{equation}\label{eqn:discreteFourierMatrixForm:300}
\Bx = \Bw \BX,
\end{equation}
where \( \Bw \) is
\begin{equation}\label{eqn:discreteFourierMatrixForm:300b}
\begin{bsmallmatrix}
 W^{N N } &  W^{\lr{N-1} N }  & \Compactcdots & 1 & \Compactcdots &  W^{- \lr{N-1} N }  &  W^{- N N } \\
 W^{N \lr{N-1} } &  W^{\lr{N-1} \lr{N-1} }  & \Compactcdots & 1 & \Compactcdots &  W^{- \lr{N-1} \lr{N-1} }  &  W^{- N \lr{N-1} } \\
 \vdots              &  \vdots                      & \vdots      & \vdots & \vdots      &  \vdots                    &  \vdots               \\
 1              &  1                      & 1      & 1 & 1      &  1                    &  1               \\
 \vdots              &  \vdots                      & \vdots      & \vdots & \vdots      &  \vdots                    &  \vdots               \\
 W^{- N \lr{N-1} } &  W^{- \lr{N-1} \lr{N-1} }  & \Compactcdots & 1 & \Compactcdots &  W^{{N-1} \lr{N-1} }  &  W^{N \lr{N-1} } \\
 W^{- N N } &  W^{\lr{1 - N} N }  & \Compactcdots & 1 & \Compactcdots &  W^{\lr{N-1} N }  &  W^{N N } \\
\end{bsmallmatrix}
\end{equation}
%
Similarly, from \cref{eqn:discreteFourierMatrixForm:220}, the inverse relation expands out to
%
\begin{equation}\label{eqn:discreteFourierMatrixForm:320}
\begin{aligned}
( 2 N + 1 ) X_n
&= x_{-N} e^{ 2 \pi j n N/(2 N + 1)} \\
&+ x_{1-N} e^{ 2 \pi j n \lr{ N-1 }/(2 N + 1)}  \\
&\cdots  \\
&+ x_0 \\
&\cdots  \\
&+ x_{N-1} e^{- 2 \pi j n \lr{N-1}/(2 N + 1)}  \\
&+ x_N e^{- 2 \pi j n N /(2 N + 1)},
\end{aligned}
\end{equation}
%
with a matrix form of
%
\begin{equation}\label{eqn:discreteFourierMatrixForm:340}
( 2 N + 1 ) \BX = \BY,
\end{equation}
where \( \BY \) is
\begin{equation}\label{eqn:discreteFourierMatrixForm:340b}
\begin{bsmallmatrix}
W^{- N N } & W^{- N \lr{N-1}} &\Compactcdots & 1 &\Compactcdots & W^{N \lr{ N-1 }} & W^{N N} \\
W^{- \lr{N-1} N } & W^{- \lr{N-1} \lr{N-1}} &\Compactcdots & 1 &\Compactcdots & W^{\lr{N-1} \lr{ N-1 }} & W^{\lr{N-1} N} \\
\vdots               & \vdots                     &  \vdots    & \vdots & \vdots     & \vdots                      &  \vdots            \\
1               & 1                     &  1    & 1 & 1     & 1                      &  1            \\
\vdots               & \vdots                     &  \vdots    & \vdots & \vdots     & \vdots                      &  \vdots            \\
W^{\lr{N-1} N } & W^{\lr{N-1} \lr{N-1}} &\Compactcdots & 1 &\Compactcdots & W^{- \lr{N-1} \lr{ N-1 }} & W^{- \lr{N-1} N} \\
W^{N N } & W^{N \lr{N-1}} &\Compactcdots & 1 &\Compactcdots & W^{- N \lr{ N-1 }} & W^{- N N} \\
\end{bsmallmatrix}.
\end{equation}
%
Let \( \BF \) equal
%
\begin{equation}\label{eqn:discreteFourierMatrixForm:360}
%\BF =
\begin{bsmallmatrix}
 W^{N N } &  W^{\lr{N-1} N }  & \Compactcdots & 1 & \Compactcdots &  W^{- \lr{N-1} N }  &  W^{- N N } \\
 W^{N \lr{N-1} } &  W^{\lr{N-1} \lr{N-1} }  & \Compactcdots & 1 & \Compactcdots &  W^{- \lr{N-1} \lr{N-1} }  &  W^{- N \lr{N-1} } \\
 \vdots              &  \vdots                      & \vdots      & \vdots & \vdots      &  \vdots                    &  \vdots               \\
 1              &  1                      & 1      & 1 & 1      &  1                    &  1               \\
 \vdots              &  \vdots                      & \vdots      & \vdots & \vdots      &  \vdots                    &  \vdots               \\
 W^{- N \lr{N-1} } &  W^{- \lr{N-1} \lr{N-1} }  & \Compactcdots & 1 & \Compactcdots &  W^{{N-1} \lr{N-1} }  &  W^{N \lr{N-1} } \\
 W^{- N N } &  W^{\lr{1 - N} N }  & \Compactcdots & 1 & \Compactcdots &  W^{\lr{N-1} N }  &  W^{N N } \\
\end{bsmallmatrix},
\end{equation}
%
the discrete transform pair has the following compactly matrix representation
%
\begin{subequations}
\begin{equation}\label{eqn:discreteFourierMatrixForm:380}
\Bx = \BF \BX
\end{equation}
\begin{equation}\label{eqn:discreteFourierMatrixForm:400}
\BX = \inv{2 N + 1} \overbar{\BF} \Bx,
\end{equation}
\end{subequations}
%
where \( \overbar{\BF} \) is the complex conjugate of \( \BF \).
%
%\EndArticle