The Discrete-Time Fourier Transform¶

This Jupyter notebook is part of a collection of notebooks in the bachelors module Signals and Systems, Comunications Engineering, Universität Rostock. Please direct questions and suggestions to Sascha.Spors@uni-rostock.de.

Definition¶

The discrete-time Fourier transform (DTFT) of a discrete signal $x[k]$ is defined as

\begin{equation} X(e^{j \Omega}) = \sum_{k = -\infty}^{\infty} x[k] \, e^{-j \Omega k} \end{equation}

where $\Omega \in \mathbb{R}$ denotes the normalized angular frequency. The DTFT maps a discrete signal $x[k]$ with $k \in \mathbb{Z}$ onto its continuous transform $X(e^{j \Omega}) = \mathcal{F}_* \{ x[k] \}$ with $\Omega \in \mathbb{R}$. It is frequently termed as spectrum of the discrete signal $x[k]$. The argument $e^{j \Omega}$ copes for the fact that the kernel $e^{-j \Omega k}$ of the DTFT is a complex exponential signal $z^{-k}$ with $z = e^{j \Omega}$. Other common definitions of the DTFT may be found in the literature. They differ with respect to the sign of the exponential function and normalization factors. The properties, theorems and transforms may differ from the ones given here, as a consequence.

A sufficient but not necessary condition for the existence of the DTFT is

\begin{equation} \left|X(e^{j \Omega})\right| = \left| \sum_{k = -\infty}^{\infty} x[k] \, e^{-j \Omega k} \right| \leq \sum_{k = -\infty}^{\infty} \left| x[k] \right| < \infty \end{equation}

where the upper bound results from the triangle inequality. As sufficient condition for the existence of the DTFT, it follows that a signal $x[k]$ needs to be absolutely summable.

The DTFT is periodic with a period of $T_\text{p} = 2 \pi$,

\begin{equation} X(e^{j \Omega}) = X(e^{j (\Omega + n \cdot 2 \pi)}) \end{equation}

for $n \in \mathbb{Z}$. This follows from the periodicity of its exponential kernel $e^{j \Omega k} = e^{j (\Omega + 2 \pi) k}$ for discrete $k \in \mathbb{Z}$. It is therefore sufficient to regard the DTFT in one period only. Typically the period $-\pi < \Omega < \pi$ is chosen. The information on the discrete signal $x[k]$ is contained in one period. As a consequence, the inverse discrete-time Fourier transform $x[k] = \mathcal{F}_*^{-1} \{ X(e^{j \Omega}) \}$ is defined as

\begin{equation} x[k] = \frac{1}{2 \pi} \int_{-\pi}^{\pi} X(e^{j \Omega}) \, e^{j \Omega k} \; d \Omega \end{equation}

Transformation of the Dirac Impulse¶

The transform $\mathcal{F}_* \{ \delta[k] \}$ of the Dirac impulse is derived by introducing $\delta[k]$ into the definition of the DTFT and exploiting the sifting property of the Dirac impulse

\begin{equation} \mathcal{F}_* \{ \delta[k] \} = \sum_{k = -\infty}^{\infty} \delta[k] \, e^{-j \Omega k} = 1 \end{equation}

The transform of the Dirac impulse is equal to one. Hence, all normalized frequencies $\Omega$ are present with equal weight. This is an important property in the theory of discrete signals and systems, since the Dirac impulse is used to characterize linear time-invariant (LTI) systems by their impulse response $h[k] = \mathcal{H} \{ \delta[k] \}$.

Exercise

• Derive the DTFT of a shifted Dirac impulse $\delta[k - \kappa]$.

Transformation of the Rectangular Signal¶

The DTFT $X(e^{j \Omega}) = \mathcal{F}_* \{ \text{rect}_N[k] \}$ of the rectangular signal is derived by introducing its definition into the definition of the DTFT. This results in

\begin{equation} \mathcal{F}_* \{ \text{rect}[k] \} = \sum_{k = -\infty}^{\infty} \text{rect}[k] \, e^{-j \Omega k} = \sum_{k = 0}^{N-1} e^{-j \Omega k} = e^{-j \Omega \frac{N-1}{2}} \cdot \frac{\sin \left(\frac{N \Omega}{2} \right)}{\sin \left( \frac{\Omega}{2} \right)} \end{equation}

The latter equality has been derived by noting that the sum constitutes a finite geometrical series with the common ratio $e^{-j \Omega}$. Note, that

\begin{equation} \frac{\sin \left(\frac{N \Omega}{2} \right)}{\sin \left( \frac{\Omega}{2} \right)} \bigg\rvert_{\Omega = n \cdot 2 \pi} = N \end{equation}

for $n \in \mathbb{Z}$ due to L'Hôpital's rule.

Example

The DTFT $X(e^{j \Omega}) = \mathcal{F}_* \{ \text{rect}_N[k] \}$ of the rectangular signal is computed for a specific length $N$ by evaluating the finite series above using SymPy.

The magnitude $|X(e^{j \Omega})|$ and phase $\varphi(e^{j \Omega}) = \arg \{ X(e^{j \Omega}) \}$ of the spectrum is plotted for illustration

Exercise

• What happens to the magnitude/phase if you increase/decrease the length $N$ of the rectangular signal?

Transformation of the Exponential Signal¶

The DTFT $X(e^{j \Omega}) = \mathcal{F}_* \{ e^{j \Omega_0 k} \}$ of the harmonic exponential signal with normalized frequency $\Omega_0$ is derived by introducing it into the definition of the DTFT. This results in

\begin{equation} \mathcal{F}_* \{ e^{j \Omega_0 k} \} = \sum_{k = -\infty}^{\infty} e^{j \Omega_0 k} \, e^{-j \Omega k} = \sum_{k = -\infty}^{\infty} e^{-j (\Omega - \Omega_0) k} = {\bot \!\! \bot \!\! \bot}\left( \frac{\Omega - \Omega_0}{2 \pi} \right) \end{equation}

where for the last equality the Fourier transform of the Dirac comb has been used. The DTFT of the exponential signal is a periodic series of shifted Dirac impulses, as

\begin{equation} {\bot \!\! \bot \!\! \bot}\left( \frac{\Omega - \Omega_0}{2 \pi} \right) = 2 \pi \sum_{\mu = -\infty}^{\infty} \delta(\Omega - \Omega_0 - 2 \pi \mu) \end{equation}

Link to Fourier Transform of a Sampled Signal¶

The link between the Fourier transform of a sampled signal $x_\text{s}(t)$ and the DTFT of its discrete counterpart $x[k] = x(k T)$ is established in the following. Under the assumption of ideal sampling, the sampled signal reads

\begin{equation} x_\text{s}(t) = \sum_{k = -\infty}^{\infty} x(k T) \cdot \delta(t - k T) = \sum_{k = -\infty}^{\infty} x[k] \cdot \delta(t - k T) \end{equation}

where $x(t)$ denotes the continuous signal and $T$ the sampling interval. Introducing the sampled signal into the definition of the Fourier transform yields the spectrum of the sampled signal

\begin{equation} X_\text{s}(j \omega) = \int_{-\infty}^{\infty} \sum_{k = -\infty}^{\infty} x[k] \cdot \delta(t - k T) \, e^{-j \omega t} \; dt = \sum_{k = -\infty}^{\infty} x[k] \, e^{-j \omega k T} \end{equation}

where the last equality has been derived by changing the order of summation/integration and exploiting the sifting property of the Dirac impulse. Comparison with the definition of the DTFT yields

\begin{equation} X_\text{s}(j \omega) = X(e^{j \Omega}) \big\rvert_{\Omega = \omega T} \end{equation}

The spectrum of the sampled signal $X_\text{s}(j \omega)$ is equal to the DTFT of the discrete Signal $X(e^{j \Omega})$ for $\Omega = \omega T$. This result can be used to interpret the frequency axis of the DTFT.

Interpretation of the Spectrum¶

It can be concluded from the definition of the inverse DTFT that a discrete signal $x[k]$ can be represented as a superposition of weighted harmonic exponential signals $X(e^{j \Omega}) \cdot e^{j \Omega k}$ for $-\pi < \Omega < \pi$. In general the spectrum $X(e^{j \Omega})$ will also have contributions for negative normalized angular frequencies $-\pi < \Omega < 0$. The concept of negative frequencies has no physical meaning. However, in the context of the DTFT with its complex kernel $e^{j \Omega k}$ negative frequencies are required to express complex and real-valued signals.

The DTFT of a discrete signal $x[k] \in \mathbb{C}$ is in general complex valued, $X(e^{j \Omega}) \in \mathbb{C}$. It is commonly represented by its real and imaginary part

\begin{equation} X(e^{j \Omega}) = \Re \{ X(e^{j \Omega}) \} + j \cdot \Im \{ X(e^{j \Omega}) \} \end{equation}

or by its magnitude and phase

\begin{equation} X(e^{j \Omega}) = |X(e^{j \Omega})| \cdot e^{j \varphi(e^{j \Omega})} \end{equation}

The magnitude spectrum $|X(e^{j \Omega})|$ provides insights into the composition of a signal in terms of its harmonic contributions. For a discrete signal which has been derived by sampling from a continuous signal, the normalized angular frequency $\Omega$ can be related to the

• angular frequency $\omega$ by $\Omega = \omega T$
• frequency $f$ by $\Omega = 2 \pi \frac{f}{f_\text{s}}$

where $T$ and $f_\text{s} = \frac{1}{T}$ denote the sampling interval and frequency, respectively. This result can be used to interpret the frequency of the DTFT as follows

Copyright

The notebooks are provided as Open Educational Resource. Feel free to use the notebooks for your own educational purposes. The text is licensed under Creative Commons Attribution 4.0, the code of the IPython examples under the MIT license. Please attribute the work as follows: Lecture Notes on Signals and Systems by Sascha Spors.