Lesson 20

Discrete Fourier Transform (DFT)

Usually, we do not have an infinite amount of data which is required by the DTFT. Instead, we have 1 image, a segment of speech, etc. Also, most real- world data are not of the convenient form $a^n u[n]$.

Finally, on a computer, we can not calculate an uncountably infinite (continuum) of frequencies as required by the DTFT.

ACTUAL DATA ANALYSIS on a computer- Use a DFT to look at a finite segment of data.

In our development in the previous section of $x[n]$ periodic with $x_0[n]$ the part of the signal that was repeated, we could have assumed that our finite segment of data came from ``windowing" an infinite length sequence $x[n]$

\begin{displaymath}x_0[n] = x[n] w_R[n] \end{displaymath}

where $w_R[n]$ is a rectangular window:


\begin{displaymath}w_R[n] = \left\{ \begin{array}{ll} 1, & n=0,1, \cdots, N-1 \\ 0, & \mbox{otherwise} \end{array} \right. \end{displaymath}

$x_0[n] = x[n] w_R[n]$ is just the samples of $x[n]$ between $n=0$ and $n=N-1.$ $x_0[n]$ is 0 everywhere else. Therefore, it is defined $\forall n$, and we can take its DTFT:

\begin{displaymath} X_0(\Omega) = \mbox{DTFT}(x_0[n]) = \sum_{n=-\infty}^{\in... ..._R[n] e^{-j \Omega n} = \sum_{n=0} ^{N-1} x[n] e^{-j\Omega n} \end{displaymath}

So,


\begin{displaymath}X_0(\Omega) = \sum_{n=0}^{N-1} x[n] e^{-j\Omega n} = \sum_{n=0}^{N-1} x_0[n] e^{-j\Omega n} \end{displaymath}

as we saw before.

Let's say now that we want to sample $X_0(\Omega)$ (which is continuous and periodic with period $2\pi$) so we store it on a computer.

Sample $X_0(\Omega)$:

Assume we want 8 points in frequency - then sample $X_0(\Omega)$ at 8 uniformly spaced points on the unit circle:


Values of frequency are $0, \pi/4, \pi/2, \cdots, 7\pi/4\ or\ 2\pi k /8, k=0,1,\cdots, 7.$

If we let $k=N$, what happens? If $k=N$, we get repetition of the points we sampled so only $N$ samples are unique.

Define Discrete Fourier Transform (DFT) as

\begin{displaymath}X[k] = X_0(\frac{2 \pi k}{N}) \end{displaymath}

for $\Omega = {2 \pi k \over N}, k=0, 1, \dots, N-1$, i.e. only look at the $N$ distinct sampled frequencies of $X_0(\Omega)$.

Note: The resolution of the samples of the frequency spectrum is $\frac{2\pi}{N}$ since we sample the spectrum at points that are spaced $\frac{2\pi}{N}$ apart in frequency, that is, $\Delta \Omega = \frac{2 \pi}{N}$.

Note: If we looked at the samples of $X_0(\Omega)$ for all $k=-\infty$ to $\infty$ for frequencies $2 \pi k \over N$, we would get the closely related Discrete Fourier Series (DFS) which is of course periodic with period $N$ since $X_0(\Omega)$ is periodic.

The DFT is just one period of the DFS.

DFT is more useful because who wants to store all the samples of a periodic signal?!! The DFT is just one period of the DFS.

Now

\begin{eqnarray*} X[k] &=& X_0(\Omega)\vert \Omega={ 2 \pi k \over N}, \ k=0, 1... ...x[n] e^{ -j {2 \pi k n \over N}}, k=0,1, \cdots, N-1 \nonumber \end{eqnarray*}

Shorthand Notation for the DFT:

Let $W_N = e^{ -j {2 \pi \over N} } \Rightarrow N^{th}$ root of unity $(W_N^N =1 )$ since $W_N^N = e^{-j 2 \pi} =1$. You may also write $W_N$ simply as $W$.

Then

\begin{displaymath}X[k] = \sum_{n=0}^{N-1} x[n] W_N^{kn}, k=0,1, \cdots, N-1 \end{displaymath}

is the DFT of your windowed sequence $x_0[n].$

Ex.

Ex.


\begin{displaymath} x[n] = \left\{ \begin{array}{cc} 1, & n=0 \\ 0, & n=1, \ldots, 7 \end{array} \right. \end{displaymath}

Find $X[k], \ k=0, 1, \ldots, 7$.


Given $y[n] = \delta[n-2]$ and $N=8$, find $Y[k]$.

\fbox{Ex.} $x[n]=cW_N^{-pn}, n=0, 1, \ldots, N-1$,

$p$ is an integer with $p \in [0,1,\dots, N-1]$ and $W_N=e^{-j\frac{2\pi}{N}}$ (as usual), find its DFT.


Synthesis: INVERSE DFT

How can we recover $x[n]$ from $X[k]$?

Synthesis formula is


\begin{displaymath} x[n] = \frac{1}{N} \sum_{k=0}^{N-1} X[k] W_N^{-kn}, \ n=0, 1, \ldots, N-1 \end{displaymath}

Prove this gives back $x[n]$:

\begin{eqnarray*} x[n] &=& \frac{1}{N} \sum_{k=0}^{N-1} \sum_{l=0}^{N-1} x[l] W... ...} \sum_{l=0}^{N-1} x[l] \sum_{k=0}^{N-1} W_N^{k(l-n)} \nonumber \end{eqnarray*}

\fbox{Ex.}



ORTHOGONALITY OF EXPONENTIALS AGAIN!

So,


\begin{displaymath} \sum_{k=0}^{N-1} W_N^{k(l-n)} = \left\{ \begin{array}{cc} N, & l=n \\ 0, & l \ne n \\ \end{array} \right. \end{displaymath}

and

\begin{eqnarray*} x[n] &=& \frac{1}{N} \sum_{l=0}^{N-1} x[l] \sum_{k=0}^{N-1} W... ...[l] N \delta[n-l]\\ &=& \frac{1}{N} (N x[n]) = x[n] \nonumber \end{eqnarray*}

Ex. Find the IDFT of $X[k]=1, k=0, 1, \ldots, 7$.

\fbox{Ex.} Given $x[n] = \delta [n] + 2 \delta[n-1] + 3\delta[n-2] + \delta[n-3]$ and $N=4$, find $X[k]$.





\fbox{Ex.} Given $X[k]= 2\delta[k] + 2\delta[k-2]$ and $N=4$, find $x[n]$.


Selected DFT Properties

  1. Linearity.


    \begin{displaymath}a x_1[n] + b x_2[n] \leftrightarrow aX_1[k] + bX_2[k] \end{displaymath}

  2. Time shift.


    \begin{displaymath}x[n-n_0]_{\mbox{mod } N} \leftrightarrow W_N^{kn_0} X[k] \end{displaymath}

  3. Frequency shift.


    \begin{displaymath}W_N^{-n k_0}x[n] \leftrightarrow X[k-k_0]_{\mbox{mod }N} \end{displaymath}

  4. Multiplication.


    \begin{displaymath}x_1[n] x_2[n] \leftrightarrow \frac{1}{N} X_1[k] \otimes X_2[k] \end{displaymath}

  5. Circular convolution.


    \begin{displaymath}x_1[n] \otimes x_2[n] \leftrightarrow X_1[k] X_2[k] \end{displaymath}

  6. Real/Even.


    \begin{displaymath}x[n] = x_e[n] + x_o[n] \leftrightarrow X[k] = A[k] + j B[k] \end{displaymath}


    \begin{displaymath}x_e[n] \leftrightarrow A[k] \end{displaymath}


    \begin{displaymath}x_o[n] \leftrightarrow j B[k] \end{displaymath}

    If $x[n]$ is real, then

    \begin{displaymath}X[-k]_{\mbox{mod } N} = X^{\ast}[k]. \end{displaymath}

    If $x[n]$ is even, then $X[k]$ is real. (For a finite length function to be even, $x[n] = x[-n]_{\mbox{mod }N} $)