Page MenuHomec4science
Files F104934618

4_DFT.tex
No OneTemporary
Actions

File Metadata

Created
Thu, Mar 13, 12:00

4_DFT.tex
View Options

\documentclass[aspectratio=169]{beamer}
\def\stylepath{../styles}
\usepackage{\stylepath/com303}
\begin{document}
\begin{frame}
\frametitle{The Fourier Basis for $\mathbb{C}^N$}
\begin{itemize}[<+->]
\item in ``signal'' notation: $w_k[n] = e^{j\frac{2\pi}{N}nk}, \qquad n, k = 0, 1, \ldots, N-1$
\item in vector notation: $\{\mathbf{w}^{(k)}\}_{k = 0, 1, \ldots, N-1}$ with $w^{(k)}_n = e^{j\frac{2\pi}{N}nk}$
\end{itemize}
\end{frame}
\begin{frame}
\frametitle{The Fourier Basis for $\mathbb{C}^N$}
\begin{itemize}
\item $N$ orthogonal vectors $\longrightarrow$ basis for $\mathbb{C}^{N}$
\item vectors are not ortho{\em normal}. Normalization factor would be $1/\sqrt{N}$
\item will keep normalization factor explicit in DFT formulas
\end{itemize}
\end{frame}
\begin{frame}
\frametitle{Basis expansion}
\centering
Analysis formula:
\[
X_k = \langle \mathbf{w}^{(k)}, \mathbf{x} \rangle
\]
\vspace{2em}
Synthesis formula:
\[
\mathbf{x} = \frac{1}{N} \sum_{k = 0}^{N-1} X_k \mathbf{w}^{(k)}
\]
\end{frame}
\begin{frame}
\frametitle{Basis expansion (signal notation)}
\centering
Analysis formula:
\[
X[k] = \sum_{n = 0}^{N-1} x[n]\, e^{-j\frac{2\pi}{N}nk}, \qquad k = 0,1,\ldots,N-1
\]
$N$-point signal in the {\em frequency domain}
\vspace{2em}
\pause
Synthesis formula:
\[
x[n] = \frac{1}{N} \sum_{k = 0}^{N-1} X[k]\, e^{j\frac{2\pi}{N}nk}, \qquad n = 0,1,\ldots,N-1
\]
$N$-point signal in the {\em ``time'' domain}
\end{frame}
\begin{frame}
\frametitle{Change of basis in matrix form}
\centering
Define $W_N = e^{-j\frac{2\pi}{N}}$
(or simply $W$ when $N$ is evident from the context)
\vspace{2em}
\pause
Change of basis matrix $\mathbf{W}$ with $\mathbf{W}[n,m] = W_N^{nm}$:
\[
\mathbf{W} = \begin{bmatrix}
1 & 1 & 1 & 1 & \ldots & 1 \\
1 & W^{1} & W^{2} & W^{3} & \ldots & W^{N-1} \\
1 & W^{2} & W^{4} & W^{6} & \ldots & W^{2(N-1)} \\
& & & \ldots \\
1 & W^{N-1} & W^{2(N-1)} & W^{3(N-1)} & \ldots & W^{(N-1)^2}
\end{bmatrix}
\]
\end{frame}
\begin{frame}
\frametitle{Change of basis in matrix form}
\centering
Analysis formula:
\[
\mathbf{X} = \mathbf{W} \mathbf{x}
\]
\vspace{2em}
Synthesis formula:
\[
\mathbf{x} = \frac{1}{N} \mathbf{W}^H \mathbf{X}
\]
\end{frame}
\begin{frame} \frametitle{DFT Matrix}
\centering
\[
W_N^m = W_N^{(m \mod N)}
\]
\pause
\vspace{2em}
e.g. $ W_8^{11} = W_8^{3}$
\end{frame}
\begin{frame}
\frametitle{Small DFT matrices: $N = 2, 3$}
\[
W_2 = e^{-j\frac{2\pi}{2}} = -1
\]
\[
\mathbf{W}_2 =
\begin{bmatrix}
1 & 1 \\
1 & W
\end{bmatrix}
=
\begin{bmatrix}
1 & 1 \\
1 & -1
\end{bmatrix}
\]
\vspace{2em}
\[
W_3 = e^{-j\frac{2\pi}{3}} = -(1 + j\sqrt{3})/2
\]
\[
\mathbf{W}_3 =
\begin{bmatrix}
1 & 1 & 1 \\
1 & W & W^2 \\
1 & W^2 & W^4
\end{bmatrix}
=
\begin{bmatrix}
1 & 1 & 1 \\
1 & W & W^2 \\
1 & W^2 & W
\end{bmatrix}
=
\begin{bmatrix}
1 & 1 & 1 \\
1 & -(1 + j\sqrt{3})/2 & -(1 - j\sqrt{3})/2 \\
1 & -(1 - j\sqrt{3})/2 & (1 - j\sqrt{3})/2
\end{bmatrix}
\]
\end{frame}
\begin{frame}
\frametitle{Small DFT matrices: $N = 4$}
\[
W_4 = e^{-j\frac{2\pi}{4}} = e^{-j\frac{\pi}{2}} = -j
\]
\[
\mathbf{W}_4 =
\begin{bmatrix}
1 & 1 & 1 & 1 \\
1 & W & W^2& W^3 \\
1 & W^2 & W^4 & W^6 \\
1 & W^3 & W^6 & W^9
\end{bmatrix}
=
\begin{bmatrix}
1 & 1 & 1 & 1 \\
1 & W & W^2& W^3 \\
1 & W^2 & 1 & W^2\\
1 & W^3 & W^2 & W
\end{bmatrix}
=
\begin{bmatrix}
1 & 1 & 1 & 1 \\
1 & -j & -1 & j \\
1 & -1 & 1 & -1 \\
1 & j & -1 & -j
\end{bmatrix}
\]
\end{frame}
\begin{frame}
\frametitle{Small DFT matrices: $N = 5$}
\[
\mathbf{W}_5 =
\begin{bmatrix}
1 & 1 & 1 & 1 & 1\\
1 & W & W^2& W^3 & W^4 \\
1 & W^2 & W^4 & W^6 & W^8\\
1 & W^3 & W^6 & W^9 & W^{12}\\
1 & W^4 & W^8 & W^{12} & W^{16}\\
\end{bmatrix}
=
\begin{bmatrix}
1 & 1 & 1 & 1 & 1\\
1 & W & W^2& W^3 & W^4 \\
1 & W^2 & W^4 & W & W^3\\
1 & W^3 & W & W^4 & W^{2}\\
1 & W^4 & W^3 & W^2 & W\\
\end{bmatrix}
\]
\end{frame}
\begin{frame}
\frametitle{Small DFT matrices: $N = 6$}
\[
\mathbf{W}_6 =
\begin{bmatrix}
1 & 1 & 1 & 1 & 1 & 1\\
1 & W & W^2& W^3 & W^4 & W^5\\
1 & W^2 & W^4 & W^6 & W^8 & W^{10}\\
1 & W^3 & W^6 & W^9 & W^{12} & W^{15}\\
1 & W^4 & W^8 & W^{12} & W^{16} & W^{20}\\
1 & W^5 & W^{10} & W^{15} & W^{20} & W^{25}
\end{bmatrix}
=
\begin{bmatrix}
1 & 1 & 1 & 1 & 1 & 1\\
1 & W & W^2& W^3 & W^4 & W^5\\
1 & W^2 & W^4 & 1 & W^2 & W^{4}\\
1 & W^3 & 1 & W^3 & 1 & W^{3}\\
1 & W^4 & W^2 & 1 & W^{4} & W^{2}\\
1 & W^5 & W^{4} & W^{3} & W^{2} & W
\end{bmatrix}
\]
\end{frame}
\end{document}

Event Timeline

c4science · Help