Transforms II: Discrete Fourier transform

Introduction

In previous modules have seen that a Fourier transform can be used to calculate the frequency distribution of a signal. Various Fourier transforms have been discussed, each for a different type signal. In this section we will introduce again another Fourier transform: The Discrete Fourier Transform (DFT). The main advantage of the DFT is that this transform, in contrast to almost all other Fourier transforms, can be calculated on a computer. In this section we will give a conceptual view of the DFT. In the first subsection we show how the DFT equation can be related, in different intermediate steps, to the Fourier Transform for Continuous time signals (FTC). In the second subsection we will discuss the periodic behaviour of the DFT. In order to calculate the frequency distribution on a computer, we will explain in the last subsection how the DFT can extract frequencies of a signal.

Screencast video [⯈]

Module overview

This module will cover the following topics:

1. From FTC to DFT - This section will describe the process of deriving the DFT starting from the FTC. From this derivation it is now possible to derive the frequency distribution of a sampled discrete-time signal.
2. The DFT [⯈] - This section will go into more depth and describe how the DFT actually extract frequencies.
3. DFT properties [⯈] - Just like with the FTC, there are several properties which greatly simply calculations. These properties will be derived in this section.
4. Convolution implementation - The DFT can be implemented using a simple convolution operation, which means that an FIR-filter can extract the frequency distribution of a signal.
5. Length of the DFT [⯈] - The resolution of the frequency distribution depends on the length of the signal. However, by appending zeros to the signal, this resolution can be increased.
6. DFT for continuous signals - In practice the DFT, or its efficient version the FFT, is often used to calculate the frequency content of (non periodic) continuous time signals. This will always result in an approximation from which the various causes of errors are shown in this section.

Summary

Definition: $$\begin{array}{c}\text{DFT:}{X}_p\left[k\right]=\sum _{n=0}^{N-1}{x}_p\left[n\right]e^{-j\frac{2\pi }{N}kn}\forall k\text{IDFT:}{x}_p\left[n\right]=\frac{1}{N}\sum _{k=0}^{N-1}{X}_p\left[k\right]e^{j\frac{2\pi }{N}kn}\forall n\end{array}$$

• Both DFT and IDFT discrete and periodic.
• Periodic extension (PE): Choose $N$ succeeding samples of $x\left[n\right]$ (usually for $n=0,1,\cdots ,N-1$) and repeat these samples. This results in the periodic signal $x_p\left[n\right]=x\left[\right(n\cdot \text{mod(N)}\left)\right]$.

DFT properties:

• DFT summation property: With twiddle factor $W_N=e^{j\frac{2\pi }{N}}$

  $$S\left[k\right]=\sum _{n=0}^{N-1}{\left\{W_N^k\right\}}^n=\sum _{n=0}^{N-1}{\left\{{\text{e}}^{j\frac{2\pi }{N}k}\right\}}^n=N\delta \left[k\text{mod}\right(N\left)\right]$$

• Linearity: $$a{x}_{p,1}\left[n\right]+b{x}_{p,2}\left[n\right]\circ -\circ a{X}_{p,1}\left[k\right]+b{X}_{p,2}\left[k\right]$$
• Circular shift: $$\begin{array}{ccc}\text{Time shift:}{x}_p[n-n_0]& \circ -\circ & e^{-j\frac{2\pi }{N}k{n}_0}\cdot X_p\left[k\right]\\ \text{Frequency shift:}{e}^{j\frac{2\pi }{N}n{k}_0}\cdot x_p\left[n\right]& \circ -\circ & X_p[k-k_0]\end{array}$$
• Circular convolution: $$x_p\left[n\right]⊛h_p\left[n\right]=\sum _{i=0}^{N-1}{x}_p\left[i\right]h_p[n-i]=\sum _{i=0}^{N-1}{x}_p[n-i]h_p\left[i\right]\circ -\circ X_p\left[k\right]\cdot H_p\left[k\right]$$ $$x_p\left[n\right]\cdot h_p\left[n\right]\circ -\circ X_p\left[k\right]⊛H_p\left[k\right]$$
• Complex conjugation: $$x_p^{\ast }\left[n\right]\circ -\circ X_p^{\ast }[N-k]$$ $$x\left[n\right]\text{real}\Rightarrow X_p\left[k\right]=X_p^{\ast }[N-k]$$
• Preserve energy (Parceval): $$\sum _{n=0}^{N-1}|x_p\left[n\right]{|}^2=\sum _{k=0}^{N-1}|X_p\left[k\right]{|}^2$$

Linear by circular convolution:

• Convolution two finite duration signals:
  If signal $x\left[n\right]$ consists of $N_1$ samples and $h\left[n\right]$ of $N_2$ samples the result of the linear convolution $y\left[n\right]=x\left[n\right]\star h\left[n\right]$ can be obtained from a circular convolution $y_p\left[n\right]=x_p\left[n\right]⊛h_p\left[n\right]$ in which both periodic extended $x_p\left[n\right]$ and $h_p\left[n\right]$ are padded with zeros up to a length of $N\ge N_1+N_2-1$ samples.
• Convolution infinite duration with finite duration signal: The overlap-add procedure is as follows:
  1. Split $x\left[n\right]$ in length $M\ge 1\left(L\right)$ non-overlapping segments
  2. Calculate $y_i\left[n\right]=h\left[n\right]\star x_i\left[n\right]$ (efficiently with FFT's)
  3. Add last $L-1$ samples previous segment with first samples current segment
  4. $y\left[n\right]={\sum }_{i=0}^{\infty }{y}_i[n-Mi]$
The overlap-save procedure is as follows:
1. Split $x\left[n\right]$ in length $M\ge L-1$ overlapping segments, overlap $L-1$
2. Calculate $y_i\left[n\right]=h\left[n\right]\star x_i\left[n\right]$ (efficiently with FFT's)
3. Construct ${\tilde{y}}_i\left[n\right]$: Discard first $L-1$ samples, last $N=M-L+1$ are correct
4. $y\left[n\right]={\sum }_{i=0}^{\infty }{\tilde{y}}_i[n-Mi]$

How choose DFT length $N$

• Periodic signals: With integer $\lambda$, if DFT length $N$ $\ne \lambda \times \#$ samples in one period $\Rightarrow$ Artefacts during PE $\Rightarrow$ Use windowing.
• Signals of finite duration $M\le N$: DFT coefficients sampled version of FTD: $X\left[k\right]=X\left(e^{j\theta }\right){\mid }_{\theta =k\cdot \frac{2\pi }{N}}$
  Note: For $N>M$:Zero padding with $N-M$ zeros:
  • Increase resolution spectral plot
  • No extra spectral information of underlying signal
• Non periodic infinite length signals:
  The DFT of an infinite duration signal is always an approximation. Exact spectral content can only be obtained by an FTD.

DFT for continuous signals: Time- bandwidth product constant $\Rightarrow$ $T\cdot \Delta \omega =2\pi /N$