The Discrete-Time Fourier Transform

Discrete-Time Energy Signals

For the discrete-time Fourier transform, we can express any discrete-time, energy (aperiodic) signal as a continuous summation (i.e., an integral) of complex exponentials.

The Discrete-Time Fourier Transform (DTFT)

Discrete-time Fourier transform analysis, i.e., the [forward] Discrete-time Fourier transform, is defined by

    \[X(\omega) = \sum_{n = -\infty}^{\infty} x[n] e^{-j \omega n }\]

Discrete-time Fourier transform synthesis, i.e., the inverse Discrete-time Fourier transform , is defined by

    \[x[n] = \frac{1}{2 \pi} \int_{2 \pi} X(\omega) e^{j \omega n } d \omega\]

Show Proof

A sampled signal is defined by

    \begin{align*}x_s(t) &= \sum_{n=-\infty}^{\infty} x(t) \delta(t - n T_s) \\&= \sum_{n=-\infty}^{\infty} x(n T_s) \delta(t - n T_s) \; .\end{align*}


where T_s is the sampling period of the sampled signal. Therefore, the Fourier transform of x_s(t) is defined as

    \begin{align*}X(\Omega) &= \int_{-\infty}^{\infty} x_s(t) e^{-j \Omega t} \; dt \\&= \int_{-\infty}^{\infty} \sum_{n=-\infty}^{\infty} x(n T_s) \delta(t - n T_s) e^{-j \Omega t} \; dt \\&= \sum_{n=-\infty}^{\infty} x(n T_s) \int_{-\infty}^{\infty} \delta(t - n T_s) e^{-j \Omega t} \; dt \\&= \sum_{n=-\infty}^{\infty} x(n T_s) e^{-j \Omega n T_s} \; .\end{align*}


Now let us define \omega = \Omega T_s and the discrete-time signal x[n] = x(n T_s). With these substitutions, we get

    \[X(\omega) = \sum_{n=-\infty}^{\infty} x[n] e^{-j \omega n} \; .\]


This is the known as the Discrete-time Fourier Transform.

Frequency Domain Periodicity

One of the important properties of the DTFT is that its frequency domain is periodic with a periodicity of 2 \pi. That means that for every DTFT representation,

    \[X(\omega) = X(\omega + 2 \pi k)\]

for any integer k. Typically, we study X(\omega) for frequencies in one period from -\pi to \pi, where 0 is the lowest frequency (before periodicity) and -\pi and \pi are the highest negative and positive freqencies.

Show Proof

Consider the values of X(\omega) and X(\omega + 2 \pi k) (where k is an integer). This is defined by

(1)   \begin{align*} X(\omega + 2 \pi k) &= \sum_{n = -\infty}^{\infty} x[n] e^{-j (\omega + 2 \pi k) n } \\ &= \sum_{n = -\infty}^{\infty} x[n] e^{-j \omega n + j 2 \pi k n} \\ &= \sum_{n = -\infty}^{\infty} x[n] e^{-j \omega n } e^{j 2 \pi k n} \\ &= \sum_{n = -\infty}^{\infty} x[n] e^{-j \omega n } (1) \\ &= \sum_{n = -\infty}^{\infty} x[n] e^{-j \omega n } \; . \end{align*}

Since n and k are integers, we know that e^{j 2 \pi k n} = \cos(2 \pi k n) + j \sin(2 \pi k n) = 1. Therefore,

(2)   \begin{align*} X(\omega + 2 \pi) &= \sum_{n = -\infty}^{\infty} x[n] e^{-j \omega n } \\&= X(\omega) \; . \end{align*}

This periodicity occurs because all discrete sine and cosine (and complex exponential, by extension) frequencies are always periodic with a period of 2 \pi.

Show Proof

Consider cos(\omega n + \phi). If we shift the frequency by 2 \pi k (where k is an integer), we get

    \begin{align*} \cos((\omega + 2\pi k) n + \phi) &= \cos(\omega n + \phi + 2\pi k n) \\ &= \cos(\omega n + \phi) \end{align*}

Since n and k are both integers, 2 \pi k n must a multiple of 2\pi. A phase shift of any multiple of 2 \pi will not affect a sinusoid.

This property is also why the inverse DTFT is only integrated for a period of 2 \pi. This periodicity will be important to consider later since it affects how we design filters and plays a significant role in our discussion on signal resampling.

Existence

The DTFT of a discrete-time, aperiodic signal x[n] is guaranteed to exist if

    \[\sum_{n=-\infty}^{\infty} |x[n]| < \infty \; .\]

Note that if the signal x[n] is a energy signal, it will satisfy this property.

Caveat: Some periodic signals (e.g., sines and cosines) can have a DTFT through the DTFT’s connection to the Discrete-Time Fourier Series and through the use of the Dirac delta function, even though periodic signals fail to satisfy the above property.

Difference Equations

Discrete-time systems can be characterized by linear, constant-coefficient difference equations. That is a summation of shifted and weighted inputs x[n] will equal a summation of shifted and weighted outputs y[n] such that

    \[\sum_{k=0}^{N} a_k y[n-k] = \sum_{k=0}^{N} b_k x[n-k]\]

If we take the DTFT of both sides of this equation, we get that

    \begin{align*} \sum_{k=0}^{N} a_k Y(\omega) e^{-j \omega k} &= \sum_{k=0}^{N} b_k X(\omega) e^{-j \omega k} \\ Y(\omega) \sum_{k=0}^{N} a_k e^{-j \omega k} &= X(\omega) \sum_{k=0}^{N} b_k e^{-j \omega k} \; .\end{align*}

Hence, the transfer function becomes

    \begin{align*} H(\omega) = \frac{Y(\omega)}{X(\omega)} &= \frac{\sum_{k=0}^{N} b_k e^{-j \omega k}}{\sum_{k=0}^{N} a_k e^{-j \omega k}} \; .\end{align*}

Therefore, we can represent a system by difference equations.