Lesson 17

Discrete-Time Fourier Transform

For infinite length sequences - in practice, we don't have an infinite amount of data so we'll also study the Discrete Fourier Transform for finite data sequences.

Recall that we wrote the sampled signal $x_s(t)
= \sum_{k=-\infty}^\infty x(kT) \delta(t - kT)$. We calculated its Fourier Transform using the Fourier Transform for a periodic function.

We do the following:

\fbox{Ex.} Find the Continuous Time Fourier Transform of $\delta(t - kT)$.

\fbox{Ex.} Using superposition, find the CT Fourier Transform of $x_s(t)$.

Now, you just calculated that

\begin{displaymath}x_s(t) \leftrightarrow \sum_{n=-\infty}^{\infty} x(nT) e^{-j n \omega T}\end{displaymath}

Let $x(nT) = x[n]$ and make a change of variables $\Omega = \omega T$ (we'll talk more about this later -- it relates the discrete-frequency variable $\Omega$ to the continuous frequency variable $\omega$ via the sampling period $T$) and we get:

\begin{displaymath}{\rm DTFT}: X(\Omega) = \sum_{n=-\infty}^{\infty} x[n] e^{-j \Omega n}

Formula to calculate inverse DTFT (this is similar to the Fourier Series):

\begin{displaymath}x[n] = {1 \over 2 \pi} \int_{2 \pi} X(\Omega) e^{j\Omega n} d\Omega \end{displaymath}

where DTFT is periodic in frequency with period $2 \pi$. Why? Because $e^{j\Omega}$ is periodic with period $2 \pi$.

\begin{displaymath}e^{j\Omega}=e^{j (\Omega + 2
\pi)} = e^{j \Omega} e^{j 2 \pi} =e^{j\Omega}.\end{displaymath}

Not all DTFTs converge due to the infinite sum.

Ex. 1 Find $X(\Omega)$ where $x[n]=a^n u[n]$, $\vert a\vert<1$. What if $\vert a\vert > 1$ ?

Ex. 2 $y[n]=a^n u[-n]$, $\vert a\vert > 1$. Find $Y(\Omega)$.

What if $\vert a\vert<1$?

Ex. 3 Rectangular pulse, $p[n]=u[n]-u[n-N]$. Find $P(\Omega)$.

Show that this filter has a linear phase term.

\fbox{Ex.} Find $H(\Omega)$ for

\begin{displaymath}h[n] = \delta[n] + 2 \delta[n-1] + 2 \delta[n-2] + \delta[n-3]\end{displaymath}

and show that the filter has a linear phase term.


We already saw the DTFT as the Z-transform of $x[n]$ evaluated on the unit circle when we discussed the frequency response:

\begin{displaymath}X(\Omega) = X(z)\vert _{z=e^{j\Omega}} \end{displaymath}

If the ROC for the Z-transform contains the unit circle, we can get DTFT from the Z-transform by substitution (compare the DTFT of $a^n u[n]$ with its Z-transform).

We'll see that the DTFT exists in cases where the ROC of the Z-transform does not include the unit circle (e.g. for periodic discrete-time signals) -analogous to the CT Fourier Transform and Laplace Transform.