# The Discrete Fourier Transform

*This Jupyter notebook is part of a [collection of notebooks](../index.ipynb) in the bachelors module Signals and Systems, Comunications Engineering, Universität Rostock. Please direct questions and suggestions to [Sascha.Spors@uni-rostock.de](mailto:Sascha.Spors@uni-rostock.de).*

## Definition

The [discrete Fourier transform](https://en.wikipedia.org/wiki/Discrete_Fourier_transform) (DFT) is defined as

\begin{equation}
X[\mu] = \sum_{k=0}^{N-1} x[k] \; e^{-j \mu \frac{2 \pi}{N} k}
\end{equation}

where $N \in \mathbb{N}$ denotes the length of the DFT and $\mu \in \mathbb{Z}$ the discrete frequency. The DFT maps a discrete signal $x[k]$ to its discrete spectrum $X[\mu] = \text{DFT}_N \{ x[k] \}$. Since its kernel $e^{-j \mu \frac{2 \pi}{N} k}$ is periodic with period $N$ with respect to the discrete frequency $\mu$, the spectrum $X[\mu]$ is periodic with period $N$

\begin{equation}
X[\mu] = X[\mu + \nu N]
\end{equation}

for $\nu \in \mathbb{Z}$. It follows from the periodicity that the unique range for $\mu = 0,1, \dots, N-1$. For $k = 0,1, \dots, N-1$ the inverse discrete Fourier transform (IDFT) is consequently defined as

\begin{equation}
x[k] = \frac{1}{N} \sum_{\mu=0}^{N-1} X[\mu] \; e^{j \mu \frac{2 \pi}{N} k}
\end{equation}

The kernel $e^{j \mu \frac{2 \pi}{N} k}$ of the IDFT is periodic with respect to the sample index $k$. It follows that the IDFT $x[k] = \text{IDFT}_M \{ X[\mu] \}$ is periodic

\begin{equation}
x[k] = x[k + \nu N]
\end{equation}

Although $k$ and $\mu$ can take any integer value it can be concluded from the periodicity, that the DFT is only unique for $k, \mu = 0, 1, \dots N-1$. As shown later, the periodicity of the DFT and IDFT has wide-ranging consequences for the properties and theorems of the DFT.

The kernel of the DFT is often represented in terms of the primitive $N$-th [root of unity](https://en.wikipedia.org/wiki/Root_of_unity) abbreviated by $w_N = e^{-j \frac{2 \pi}{N}}$

\begin{equation}
X[\mu] = \sum_{k=0}^{N-1} x[k] \; w_N^{\mu k}
\end{equation}

The kernel of the IDFT is given by reversing the sign of the exponent of $w_N$. Other common definitions of the DFT and IDFT may be found in the literature. They differ with respect to the sign of the exponent and the normalization factor $\frac{1}{N}$. As a consequence, the properties, theorems and transforms may differ from the ones given here.

### Link to the Discrete-Time Fourier Transform

The [discrete-time Fourier transform](../discrete_time_fourier_transform/definition.ipynb) (DTFT) $X(e^{j \Omega}) = \mathcal{F}_* \{ x[k] \}$ of a causal signal of finite length $x[k] = 0$ for $k \in \mathbb{Z} \setminus \{0,1,\dots, N-1 \}$ is continuous with respect to the normalized angular frequency $\Omega$. The DFT $X[\mu]$ of the same signal is discrete. In order to derive the relation between both transforms, the definition of the DTFT is compared with the definition of the DFT. This reveals that both are linked by

\begin{equation}
X[\mu] = X(e^{j \Omega}) \big\rvert_{\Omega = \mu \frac{2 \pi}{N}}
\end{equation}

The DFT $X[\mu]$ of a finite-length discrete signal $x[k]$ can be derived by sampling its DTFT $X(e^{j \Omega})$ equidistantly at $\Omega = \mu \frac{2 \pi}{N}$. 

The questions arises if the DFT $X[\mu]$ fully represents a discrete signal $x[k]$ of finite length? In order to elaborate on this, the DTFT of a discrete signal is investigated. The [DTFT of a discrete signal is periodic](../discrete_time_fourier_transform/definition.ipynb#Definition) with period $2 \pi$. This holds also for a discrete signal $x[k]$ of finite length. This is depicted below



The [spectrum of a periodic signal](../periodic_signals/spectrum.ipynb) consists of a series of weighted Dirac impulses. It can be described fully by the weights of the Dirac impulses. The same holds also for the spectrum $X_\text{p} (e^{j \Omega})$ of the periodic continuation $x_\text{p}[k] = \sum_{\nu = - \infty}^{\infty} x[k - \nu N]$ of the finite length signal $x[k]$. The weights of the Dirac pulses are given by equidistant sampling of the spectrum of one period $X(e^{j \Omega})$ at $\Omega = \mu \frac{2 \pi}{N}$. This is depicted below



It can be concluded from above reasoning that the DFT of a causal finite-length discrete signal contains all information on the signal.

### Interpretation of the Spectrum

Inspection of the definition of the inverse DFT reveals, that a discrete signal $x[k]$ of finite length can be represented as a superposition of weighted harmonic exponential signals $z^k$ with the complex frequencies $z = e^{j \mu \frac{2 \pi}{N}}$ for $\mu = 0, 1, \dots, N-1$. The corresponding normalized angular frequencies of the exponential signal are given as $\Omega = \mu \frac{2 \pi}{N}$. In the following, the complex frequencies $z$ are illustrated in the $z$-plane for the case of an even ($N=10$) and odd length ($N=11$) of the DFT



The distribution of the complex frequencies in the $z$-plane is different for an even or odd length of the DFT. Only in the case of an even length, the normalized frequency $\Omega = \pi$ is included. For a further interpretetation of the discrete frequency $\mu$, the link between the DFT and the DTFT is used. The DFT $X[\mu]$ can be derived from the DTFT by sampling $X(e^{j \Omega})$ at $\Omega = \mu \frac{2 \pi}{N}$. The DTFT $X(e^{j \Omega})$ is sampled in the range of $0 \leq \Omega < 2 \pi$. Since the DTFT is periodic with a period of $2 \pi$, it can be conluded that the DTFT $X(e^{j \Omega})$ for $\pi < \Omega < 2 \pi$ is equal to the DTFT for $-\pi < \Omega < 0$. It follows, that the DFT $X[\mu]$ for $\frac{N}{2} < \mu \leq (N-1)$ is equal to the sampled DTFT for [negative normalized angular frequencies](https://en.wikipedia.org/wiki/Negative_frequency) $-\pi < \Omega < 0$. The resulting normalized frequency axis of the DFT is illustrated for the case of an even length ($N=10$)



For a discrete signal which has been derived by sampling from a continuous signal $x[k] = x(k T)$, the normalized angular frequency $\Omega$ can be related to the 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. The lowest axis illustrates the resulting frequency axis. It can be concluded that the first half of the spectrum represents the complex values of $X[\mu]$ for increasing positive frequencies, while the second half represents the complex values for decreasing negative frequencies. This structure has to be kept in mind when interpreting a DFT.

The DFT of a discrete signal $x[k] \in \mathbb{C}$ is in general complex valued, $X[\mu] \in \mathbb{C}$. It is commonly illustrated by its real and imaginary part 

\begin{equation}
X[\mu] = \Re \{ X[\mu] \} + j \cdot \Im \{ X[\mu] \}
\end{equation}

or by its magnitude and phase 

\begin{equation}
X[\mu] = |X[\mu]| \cdot e^{j \varphi[\mu]}
\end{equation}

The magnitude spectrum $|X[\mu]|$ provides insights into the superposition of a discrete signal in terms of the level of its harmonic contributions. It is therefore a valuable tool for the analysis of signals and systems.

### Matrix/Vector Representation

Above definition of the DFT is given in terms of a summation over the samples $x[k]$ for $k=0, 1, \dots, N-1$. The summation has to be evaluated for $\mu = 0, 1, \dots, N-1$ in order to yield the DFT $X[\mu] = \text{DFT}_N \{ x[k] \}$. The calculation can be represented in terms of a matrix/vector multiplication. First the $N$ samples of the signal $x[k]$ are combined into the $N \times 1$ vector

\begin{equation}
\mathbf{x} = \left[ x[0], x[1], \dots, x[N-1] \right]^T
\end{equation}

In the same manner, the $N$ samples of the spectrum $X[\mu]$ are combined  into the $N \times 1$ vector

\begin{equation}
\mathbf{X} = \left[ X[0], X[1], \dots, X[N-1] \right]^T
\end{equation}

The computation of all $N$ values of $X[\mu]$ from all $N$ values of $x[k]$ can now be expressed as matrix/vector product

\begin{equation}
\mathbf{X} = \mathbf{F} \mathbf{x}
\end{equation}

where the $N \times N$ [DFT matrix](https://en.wikipedia.org/wiki/DFT_matrix) is defined as 

\begin{equation}
\mathbf{F} = \left[ \begin{array}{ccccc}
1 & 1 & 1 & \dots & 1 \\
1 & w_N & w_N^2 & \dots & w_N^{N-1} \\
1 & w_N^2 & w_N^6 & \dots & w_N^{2 (N-1)} \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
1 & w^{N-1} & w^{2(N-1)} & \dots & w^{(N-1)(N-1)}
\end{array} \right]
\end{equation}

Above DFT matrix is, besides the scaling factor $N$, [unitary](https://en.wikipedia.org/wiki/Unitary_matrix)

\begin{equation}
\mathbf{F} \, \mathbf{F}^H = N \cdot \mathbf{I}
\end{equation}

where $(\cdot)^H$ denotes the [Hermitian](https://en.wikipedia.org/wiki/Hermitian_adjoint) (conjugate transpose) of a matrix and $\mathbf{I}$ the $N \times N$ [identity matrix](https://en.wikipedia.org/wiki/Identity_matrix). Multiplying the left- and right-hand side of above matrix/vector representation of the DFT from the left by $\frac{1}{N} \mathbf{F}^H$ yields the representation of the inverse DFT as

\begin{equation}
\mathbf{x} = \frac{1}{N} \cdot \mathbf{F}^H \mathbf{X}
\end{equation}

The matrix/vector representation of the DFT is useful for the discussion of its properties and its implementation. Functions for the computation of the DFT matrix are provided in many toolkits for numerical mathematics. In the following the Python function [`scipy.linalg.dft`](http://docs.scipy.org/doc/scipy/reference/generated/scipy.linalg.dft.html) is used. The real part of $w_N^\mu$ for $\mu=0, 1, \dots, N-1$ is plotted for illustration of the kernel of the DFT. The application of the matrix/vector representation is shown in the following section.


```python
%matplotlib inline
import numpy as np
import matplotlib.pyplot as plt
from scipy.linalg import dft

F = dft(8)

plt.figure(figsize=(10, 10))
for n in range(8):
    ax = plt.subplot(4, 2, n+1)
    ax.stem(np.real(F[:, n]))
    plt.title('$\mu = %d$'%n)
    plt.ylabel(r'$\Re \{ e^{-j \mu \frac{2 \pi}{N} k} \}$')
    plt.xlabel('$k$')
plt.tight_layout()
```

### Transformation of the Dirac Impulse

The $\text{DFT}_N \{ \delta[k] \}$ of the [Dirac impulse](../discrete_signals/standard_signals.ipynb#Dirac-Impulse) is derived by introducing $\delta[k]$ into the definition of the DFT and exploiting the sifting property of the Dirac impulse

\begin{equation}
\text{DFT}_N \{ \delta[k] \} = \sum_{k = 0}^{N-1} \delta[k] \, e^{-j \mu \frac{2 \pi}{N} k} = 1
\end{equation}

The transform of the Dirac impulse is equal to one. Hence, all discrete frequencies $\mu$ 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](../discrete_systems/impulse_response.ipynb) $h[k] = \mathcal{H} \{ \delta[k] \}$.

**Exercise**

* Derive the $\text{DFT}_N \{ \delta[k - \kappa] \}$ of the shifted Dirac impulse for $0 \leq \kappa < N$.

### Transformation of the Exponential Signal

The DFT $X[\mu] = \text{DFT}_N \{ e^{j \Omega_0 k} \}$ of the [harmonic exponential signal](../discrete_signals/standard_signals.ipynb#Complex-Exponential-Signal) with normalized frequency $\Omega_0$ is derived by introducing it into the definition of the DFT. This results in

\begin{equation}
X[\mu] = \sum_{k=0}^{N-1} e^{j \Omega_0 k} \; e^{-j \mu \frac{2 \pi}{N} k} 
= \sum_{k=0}^{N-1} e^{j k (\Omega_0 - \mu \frac{2 \pi}{N})} 
= \frac{1 - e^{j (\Omega_0 - \mu \frac{2 \pi}{N}) N}}{1 - e^{j (\Omega_0 - \mu \frac{2 \pi}{N})}} 
= e^{-j (\Omega_0 - \mu \frac{2 \pi}{N} ) \frac{N-1}{2} } \cdot \frac{\sin \left( \frac{N (\Omega_0 - \mu \frac{2\pi}{N})}{2} \right)}{\sin \left( \frac{ \Omega_0 - \mu \frac{2\pi}{N}}{2} \right)}
\end{equation}

The second last equality has been derived by noting that the sum constitutes a [finite geometrical series](https://en.wikipedia.org/wiki/Geometric_series) with the common ratio $e^{-j (\Omega - \mu \frac{2 \pi}{N})}$.

Unlike the [DTFT of the exponential signal](../discrete_time_fourier_transform/definition.ipynb#Transformation-of-the-Exponential-Signal), its DFT is in general not given by a series of shifted Dirac impulses. In order to gain further insight, let's consider an harmonic exponential signal which is periodic with period $N$. The lowest normalized frequency such a periodic signal can have is $\Omega_\text{min} =\frac{2 \pi}{N}$. Note that an exponential signal whose frequency is a multiple of $\Omega_\text{min}$ is also periodic with period $N$. It can be concluded that the normalized frequency of an harmonic exponential signal with period $N$ is given as $\Omega_0 = M \cdot \frac{2 \pi}{N}$ for $M = 0,1,\dots, N-1$. Introducing this specific choice for $\Omega_0$ into the DFT above yields

\begin{equation}
\text{DFT}_N \{ e^{j M \cdot \frac{2 \pi}{N} k} \} = N \cdot \delta[\mu - M]
\end{equation}

since

\begin{equation}
\frac{\sin \left(\pi (M-\mu) \right)}{\sin \left(\frac{\pi}{N} (M - \mu) \right)} = \begin{cases}
N & \text{for } M=\mu \\
0 & \text{otherwise}
\end{cases}
\end{equation}

Note that [L'Hôpital's rule](https://en.wikipedia.org/wiki/L'H%C3%B4pital's_rule) was applied for $M=\mu$. The DFT of an harmonic exponential signal which is periodic with period $N$ is given as a Dirac impulse. The case of an aperiodic exponential signal is discussed in the following example.

**Example**

In the following example the DFT of an harmonic exponential signal $e^{j \Omega_0 k}$ with $\Omega_0 = M \cdot \frac{2 \pi}{N}$ is computed by the matrix/vector representation of the DFT. The signal is periodic with period $N$ for $M \in \mathbb{Z}$ and aperiodic for $M \notin \mathbb{Z}$. The latter case is considered first, the former in the exercises below.


```python
N = 16
M = 3.33
W0 = M * 2*np.pi/N

F = dft(N)
k = np.arange(N)
x = np.exp(1j*W0*k)
X = np.matmul(F, x)
X
```




    array([ 1.31266387 +5.28685729e-01j,  1.63083183 +1.06667837e+00j,
            2.38037882 +2.33409311e+00j,  7.49352177 +1.09799457e+01j,
           -2.57047932 -6.03735081e+00j, -0.54711115 -2.61602209e+00j,
           -0.01688123 -1.71945225e+00j,  0.24191786 -1.28184690e+00j,
            0.40512534 -1.00587811e+00j,  0.52515992 -8.02910730e-01j,
            0.62378131 -6.36151064e-01j,  0.71244674 -4.86226008e-01j,
            0.79885258 -3.40121704e-01j,  0.88992974 -1.86118644e-01j,
            0.99422729 -9.76111721e-03j,  1.12563462 +2.12436536e-01j])



The real and imaginary part of the signal $x[k]$ as well as its DFT $X[\mu]$ are plotted for illustration


```python
plt.figure(figsize=(10, 8))

plt.subplot(2, 2, 1)
plt.stem(x.real)
plt.xlabel('$k$')
plt.ylabel('$\Re \{ x[k] \}$')
plt.ylim([-1.1, 1.1])

plt.subplot(2, 2, 2)
plt.stem(x.imag)
plt.xlabel('$k$')
plt.ylabel('$\Im \{ x[k] \}$')
plt.ylim([-1.1, 1.1])

plt.subplot(2, 2, 3)
plt.stem(X.real)
plt.xlabel('$\mu$')
plt.ylabel('$\Re \{ X[\mu] \}$')
plt.ylim([-N, N])

plt.subplot(2, 2, 4)
plt.stem(X.imag)
plt.xlabel('$\mu$')
plt.ylabel('$\Im \{ X[\mu] \}$')
plt.ylim([-N, N]);

plt.tight_layout()
```

**Exercise**

* Rerun the example with different normalized frequencies $\Omega_0 = M \frac{2 \pi}{N}$ resulting in periodic or aperiodic harmonic exponential signals.
* Where is the maximum of the real and imaginary part, and the absolute value $|X[\mu]|$ located in case of an aperiodic signal?

It should become obvious that depending on the chosen frequency a more or less 'smeared' Dirac impulse can be observed. This effect is known as [leakage effect](https://en.wikipedia.org/wiki/Spectral_leakage) of the DFT, since the Dirac impulse leaks into the neighboring bins.

**Example**

In order to facilitate the interpretation of a spectrum, many libraries for signal processing provide functionality to compute the values of the frequency axis for a sampled signal. This is illustrated for the spectrum $X[\mu]$ of the exponential signal from the previous example. The magnitude spectrum $|X[\mu]|$ is plotted for a sampling frequency of $f_\text{s} = 48000$ Hz.


```python
fs = 48000
f = np.fft.fftfreq(N, 1/fs)

plt.stem(f, abs(X))
plt.xlabel('$f[\mu]$ in Hz')
plt.ylabel(r'$|X[\mu]|$')
plt.xlim([-fs/2, fs/2]);
```

**Copyright**

The notebooks are provided as [Open Educational Resource](https://de.wikipedia.org/wiki/Open_Educational_Resources). Feel free to use the notebooks for your own educational purposes. The text is licensed under [Creative Commons Attribution 4.0](https://creativecommons.org/licenses/by/4.0/), the code of the IPython examples under the [MIT license](https://opensource.org/licenses/MIT). Please attribute the work as follows: *Lecture Notes on Signals and Systems* by Sascha Spors.

4cea75e33e39b701925ebeb79a38f543a996c0df
ipynb
Jupyter Notebook
discrete_fourier_transform/definition.ipynb
swchao/signalsAndSystemsLecture
7f135d091499e1d3d635bac6ddf22adee15454f8
MIT
2019-01-27T12:39:27.000Z
2022-03-15T10:26:12.000Z
discrete_fourier_transform/definition.ipynb
xushoucai/signals-and-systems-lecture
30dbbf9226d93b454639955f5462d57546a921c5
MIT
discrete_fourier_transform/definition.ipynb
xushoucai/signals-and-systems-lecture
30dbbf9226d93b454639955f5462d57546a921c5
MIT
2020-09-18T06:26:48.000Z
2021-12-10T06:11:45.000Z
Qwen/Qwen-72B
1. YES
2. YES