\magnification=\magstep1
\centerline{Mathematics 174 -- Applied Mathematics 2}
\centerline{Discussion 6 -- The Discrete Fourier Transform}
\centerline{April 13, 2000}
\bigskip
\noindent
{\it Background}
\bigskip
Let $\{f_j\}_{j=0}^{N-1}$ be a (finite) sequence of complex numbers.
The $N$-point discrete Fourier transform (DFT) of $\{f_j\}$ is the sequence
$F_k$, $k \in {\bf Z}$, defined by 
$$F_k = {1\over 2\pi} \sum_{j=0}^{N-1} f_j\ e^{2\pi i(jk)\over N}$$
If the $f_j$ are samples of an analog signal $f$ on the interval $[0,\Omega]$:
$f_j = f\left({j \Omega\over N}\right)$, then the DFT sequence gives
{\it approximate values for samples of the Fourier transform of $f$\/} 
as follows:
$$F_k \doteq {N\over \Omega} {\cal F}[f]\left({2\pi k\over \Omega}\right).\leqno(1)$$
The complex numbers $z_\ell = e^{2\pi i\ell\over N}$ are all $N$th roots 
of unity:  For all $\ell \in {\bf Z}$, they satisfy the polynomial equation 
$z^N  - 1 = 0$.  Since there are only $N$ distinct roots of this equation in 
${\bf C}$, in fact $z_{\ell + N} = z_\ell$ for all $\ell$, and 
$z_0, z_1,z_2 = z_1^2 \ldots z_{N-1} = z_1^{N-1}$ are one complete set of 
distinct roots.  (In abstract algebra terms, the set of $N$th roots of unity 
is a cyclic subgroup of the multiplicative group of non-zero complex numbers, 
and  $z_1$ is a generator.)
\bigskip
\noindent
{\it Discussion Questions}
\bigskip
\item{A)}  Show that the $N$-point DFT of any sequence is {\it periodic}, with 
period $N$:  $F_{k + N} = F_k$ for all $k \in {\bf Z}$.  
\bigskip
\item{B)}  If we look at equation
(1) and think of $F_k$ as giving a way to approximate 
${\cal F}[f]\left({2\pi k\over \Omega}\right)$, then notice from 
question A that essentially the maximum frequency value
for which we can approximate ${\cal F}[f]$ with the $N$-point DFT is 
$\omega = {2\pi N\over\Omega}$.  Actually ``even less is true.''  Namely,
we really want to think of $\omega \in [{-\pi N\over \Omega},{\pi N\over \Omega}]$.
For signals like $\cos(\omega x)$, the DFT is symmetric, so that
we are really talking about $0 \le \omega \le {\pi N\over \Omega}$.
 Is this reasonable?
Let's take $\Omega = 1$.  Sketch the graph $y = \cos(12\pi x)$ on $[0,1]$.  
Mark the points on the graph we would be getting by sampling with $N = 12$ 
and $N = 4$.  Use what you see to answer the following questions:
\bigskip
\itemitem{1)}  Find a different signal that
``matches'' the samples from $\cos(12\pi x)$ at $x = j/4$ (the
sampling points with $N = 4$).  Is there one of the form $\cos(\omega x)$
with $\omega < 12\pi$?
\itemitem{2)}  Find a different signal that 
``matches'' the samples from $\cos(12\pi x)$ at $x = j/12$ (the
sampling points with $N = 12$).  Is there one of the form $\cos(\omega x)$
with $\omega < 12\pi$?
\bigskip
\item{}
The name for the phenomenon you see in parts 1 and 2 is {\it aliasing}.  
An {\it alias} of a signal is a different signal that has the same sampled 
values.  
\bigskip
\itemitem{3)}  With $\Omega = 1$, and $N$ given, why is
$\omega = {\pi N\over\Omega} = \pi N$ ``special'' here?
And conversely, if $\Omega = 1$ is given and you have a signal
$\cos(\omega x)$, how often should you sample (i.e. how big does $N$
have to be)  to make sure that there is no {\it lower-frequency} alias
for your sampled values?
\bigskip
\item{}
There is an extremely important generalization
of this train of thought called the {\it Shannon-Nyquist Sampling Theorem\/}.
The statement and proof will appear on this semester's Final Problem Set.
\bigskip
\item{C)}  If $f_j$ and $g_j$ are sequences indexed by $j \in \{0,1,\ldots,N-1\}$,
then we define their {\it circular convolution} to be the sequence 
$h = f * g$ where
$$h_j = \sum_{i=0}^{N-1} f_i g_{j - i}\leqno(2)$$
where, when $j - i$ falls outside the range $\{0,1,\ldots,N-1\}$, we take
the index {\it modulo} $N$.  (Alternatively, we could think 
of making extended periodic sequences using $f$ and $g$, then applying the 
convolution formula (2) to the periodic extensions.)
\bigskip
\itemitem{1)}  Compute the convolution of the 6-point sequences
$\{f_j\} = 3,2,1,1,2,3$ and $\{g_j\} = -1,1,-1,1,-1,1$.
\bigskip
\itemitem{2)}  Show (in general) that if $F_k, G_k$, and $H_k$ are the $N$-point
DFT's of $f_j, g_j$, and $h_j = (f * g)_j$ respectively, then for all $k$,
$$H_k = 2\pi F_k G_k$$
(just like the convolution formula for the ordinary Fourier transform).
\bigskip
\item{D)}  There is also a DFT version of the Fourier Inversion Formula.
Here's how it works.  
\itemitem{1)}  Show that $z_\ell = e^{2\pi i\ell\over N}$ satisfies:
$$1 + z_\ell + z_\ell^2 + \cdots + z_\ell^{N-1} = 
\cases{ N & if $\ell \equiv 0 \bmod N$\cr
        0 & otherwise}$$
(Hint: If you have a polynomial 
$$f(z) = a_0 + a_1z + \cdots + a_{m-1}z^{m-1} + z^m,$$
with distinct roots $z = z_1, \ldots, z_m$ in ${\bf C}$, what is the sum of 
the roots?)
\bigskip
\itemitem{2)}  If $F_k$ is the $N$-point DFT of $f_j$, show that
$$f_j = {2\pi\over N} \sum_{k=0}^{N-1} F_k\ e^{-2\pi i (kj)\over N}.$$
(The right hand side is the ``DIFT'' of the sequence $F_k$.)
\bigskip
\noindent
{\it Assignment}
\bigskip
Group write-ups due Tuesday, April 18, if possible
\bye