Discrete Fourier Transform (DFT)

1 Arguments for the discrete implementation of the Fourier transform
2 Time discretisation – Periodification in the frequency domain
3 Frequency discretisation – Periodification in the time domain
4 Finite signal representation
5 From the continuous to the discrete Fourier transform
6 Inverse discrete Fourier transform
7 Interpretation of DFT and IDFT
8 Exercises for the chapter

Arguments for the discrete implementation of the Fourier transform

The $\text{Fourier transform}$ according to the previous description in chapter Aperiodic Signals – Pulses has an infinitely high selectivity due to the unlimited extension of the integration interval and is therefore an ideal theoretical tool of spectral analysis.

If the spectral components $X(f)$ of a time function $x(t)$ are to be determined numerically, the general transformation equations are

$$\begin{align*}X(f) & = \int_{-\infty }^{+\infty}x(t) \cdot {\rm e}^{-{\rm j} \hspace{0.05cm}\cdot \hspace{0.05cm} 2 \pi f t}\hspace{0.1cm} {\rm d}t\hspace{0.5cm} \Rightarrow\hspace{0.5cm} \text{Transform}\hspace{0.7cm} \Rightarrow\hspace{0.5cm} \text{first Fourier integral} \hspace{0.05cm},\\ x(t) & = \int_{-\infty }^{+\infty}\hspace{-0.15cm}X(f) \cdot {\rm e}^{\hspace{0.05cm}+{\rm j} \hspace{0.05cm}\cdot \hspace{0.05cm} 2 \pi f t}\hspace{0.1cm} {\rm d}f\hspace{0.35cm} \Rightarrow\hspace{0.5cm} \text{Inverse Transform}\hspace{0.4cm} \Rightarrow\hspace{0.5cm} \text{second Fourier integral} \hspace{0.05cm}\end{align*}$$

unsuitable for two reasons:

The equations apply exclusively to time-continuous signals. With digital computers or signal processors, however, one can only process time-discrete signals.
For a numerical evaluation of the two Fourier integrals it is necessary to limit the respective integration interval to a finite value.

$\text{This leads to the following consequence:}$

A $\text{continuous signal}$ must undergo two processes before the numerical determination of its spectral properties, viz.

that of $\text{sampling}$ for discretisation, and
that of $\text{windowing}$ to limit the integration interval.

In the following, starting from an aperiodic time function $x(t)$ and the corresponding Fourier spectrum $X(f)$ a time- and frequency-discrete description suitable for computer processing is developed step by step.

Time discretisation – Periodification in the frequency domain

The following graphs show uniformly the time domain on the left and the frequency domain on the right. Without limiting generality, $x(t)$ and $X(f)$ are each real and Gaussian.

Time discretisation ⇒ Periodification in the frequency domain

According to the chapter Time-Discrete Signal Representation one can describe the sampling of the time signal $x(t)$ by multiplying it by a Dirac impulse train ⇒ Dirac comb in the time domain)

$$p_{\delta}(t) = \sum_{\nu = - \infty }^{+\infty} T_{\rm A} \cdot \delta (t- \nu \cdot T_{\rm A} )\hspace{0.05cm}.$$

The result is the time signal sampled at a distance $T_{\rm A}$

$${\rm A}\{x(t)\} = \sum_{\nu = - \infty }^{+\infty} T_{\rm A} \cdot x(\nu \cdot T_{\rm A})\cdot \delta (t- \nu \cdot T_{\rm A} )\hspace{0.05cm}.$$

We transform this sampled signal $\text{A}\{ x(t)\}$ into the frequency domain:

The multiplication of the Dirac comb $p_{\delta}(t)$ with $x(t)$ corresponds in the frequency domain to the convolution of $P_{\delta}(f)$ with $X(f)$.

The result is the periodised spectrum $\text{P}\{ X(f)\}$, where $f_{\rm P}$ indicates the frequency period of the function $\text{P}\{ X(f)\}$ :

$${\rm A}\{x(t)\} \hspace{0.2cm}\circ\!\!-\!\!\!-\!\!\!-\!\!\bullet\, \hspace{0.2cm} {\rm P}\{X(f)\} = \sum_{\mu = - \infty }^{+\infty} X (f- \mu \cdot f_{\rm P} ).$$

This relation was already derived in the chapter Time-Discrete Signal Representation but with slightly different nomenclature:

We now denote the sampled signal by $\text{A}\{ x(t)\}$ instead of $x_{\rm A}(t)$.
The $\text{frequency period}$ is now denoted by $f_{\rm P} = 1/T_{\rm A}$ instead of $f_{\rm A} = 1/T_{\rm A}$ .

These nomenclature changes are justified on the following pages.

The graph above shows the functional relationship described here. It should be noted:

The frequency period $f_{\rm P}$ has been deliberately chosen to be small here so that the overlap of the spectra to be summed can be clearly seen.
In practice $f_{\rm P}$ should be at least twice as large as the largest frequency contained in the signal $x(t)$ due to the sampling theorem.
If this is not fulfilled, then $\text{Aliasing}$ must be reckoned with - see chapter Possible Errors when using DFT.

Frequency discretisation – Periodification in the time domain

The discretisation of $X(f)$ can also be described by a multiplication with a Dirac comb. The result is the spectrum sampled in the distance $f_{\rm A}$ :

$${\rm A}\{X(f)\} = X(f) \cdot \sum_{\mu = - \infty }^{+\infty} f_{\rm A} \cdot \delta (f- \mu \cdot f_{\rm A } ) = \sum_{\mu = - \infty }^{+\infty} f_{\rm A} \cdot X(\mu \cdot f_{\rm A } ) \cdot\delta (f- \mu \cdot f_{\rm A } )\hspace{0.05cm}.$$

If one transforms the frequency-dirac comb $($with pulse weights $f_{\rm A})$ used here into the time domain, one obtains with $T_{\rm P} = 1/f_{\rm A}$:

$$\sum_{\mu = - \infty }^{+\infty} f_{\rm A} \cdot \delta (f- \mu \cdot f_{\rm A } ) \hspace{0.2cm}\bullet\!\!-\!\!\!-\!\!\!-\!\!\circ\, \hspace{0.2cm} \sum_{\nu = - \infty }^{+\infty} \delta (t- \nu \cdot T_{\rm P } ) \hspace{0.05cm}.$$

The multiplication with $X(f)$ corresponds in the time domain to the convolution with $x(t)$. One obtains the signal $T_{\rm P}$ periodified in the distance $\text{P}\{ x(t)\}$:

$${\rm A}\{X(f)\} \hspace{0.2cm}\bullet\!\!-\!\!\!-\!\!\!-\!\!\circ\, \hspace{0.2cm} {\rm P}\{x(t)\} = x(t) \star \sum_{\nu = - \infty }^{+\infty} \delta (t- \nu \cdot T_{\rm P } )= \sum_{\nu = - \infty }^{+\infty} x (t- \nu \cdot T_{\rm P } ) \hspace{0.05cm}.$$

Frequency Discretisation – Periodisation in the Time Domain

$\text{Example 1:}$ This correlation is illustrated in the graph:

Due to the coarse frequency rastering, this example results in a relatively small value for the time period $T_{\rm P}$ .

Therefore, the (blue) periodised time signal $\text{P}\{ x(t)\}$ differs significantly from $x(t)$.

due to overlaps.

Finite signal representation

Finite Signals of the Discrete Fourier Transform (DFT)

One arrives at the so-called finite signal representation ,

if both the time function $x(t)$
and the spectral function $X(f)$

are specified exclusively by their sample values.
The graph is to be interpreted as follows:

In the left picture, drawn in blue, is the function $\text{A}\{ \text{P}\{ x(t)\}\}$. This results from sampling the periodified time function $\text{P}\{ x(t)\}$ with equidistant dirac pulses at a distance $T_{\rm A} = 1/f_{\rm P}$.
In the right picture the function is drawn in green $\text{P}\{ \text{A}\{ X(f)\}\}$. This results from periodisation $($with $f_{\rm P})$ of the sampled spectral function $\{ \text{A}\{ X(f)\}\}$.
There is a Fourier correspondence between the blue finite signal (left sketch) and the green finite signal (right sketch), as follows:

$${\rm A}\{{\rm P}\{x(t)\}\} \hspace{0.2cm}\circ\!\!-\!\!\!-\!\!\!-\!\!\bullet\, \hspace{0.2cm} {\rm P}\{{\rm A}\{X(f)\}\} \hspace{0.05cm}.$$

The diraclines of the periodic continuation $\text{P}\{ \text{A}\{ X(f)\}\}$ of the sampled spectral function, however, only fall into the same frequency grid as those of $\text{A}\{ X(f)\}$ if the frequency period $f_{\rm P}$ is an integer multiple $(N)$ of the frequency sampling interval $f_{\rm A}$ .
Therefore, when using the finite signal representation, the following condition must always be fulfilled, where the natural number $N$ in practice is usually a power of two (the above graph is based on the value $N = 8$ ):

$$f_{\rm P} = N \cdot f_{\rm A} \hspace{0.5cm} \Rightarrow\hspace{0.5cm} {1}/{T_{\rm A}}= N \cdot f_{\rm A} \hspace{0.5cm} \Rightarrow\hspace{0.5cm} N \cdot f_{\rm A}\cdot T_{\rm A} = 1\hspace{0.05cm}.$$

If the condition $N \cdot f_{\rm A} \cdot T_{\rm A} = 1$ the order of periodization and sampling is interchangeable. Thus:

$${\rm A}\{{\rm P}\{x(t)\}\} = {\rm P}\{{\rm A}\{x(t)\}\}\hspace{0.2cm}\circ\!\!-\!\!\!-\!\!\!-\!\!\bullet\, \hspace{0.2cm} {\rm P}\{{\rm A}\{X(f)\}\} = {\rm A}\{{\rm P}\{X(f)\}\}\hspace{0.05cm}.$$

$\text{Conclusion:}$

The time function $\text{P}\{ \text{A}\{ x(t)\}\}$ has the period $T_{\rm P} = N \cdot T_{\rm A}$.
The period in the frequency domain is $f_{\rm P} = N \cdot f_{\rm A}$.
For the description of the discretised time and frequency response in each case $N$ complex numerical values in the form of pulse weights are thus sufficient.

$\text{Example 2:}$ A time-limited (pulse-like) signal $x(t)$ is present in sampled form, where the distance between two samples $T_{\rm A} = 1\, {\rm µ s}$ is:

After a discrete Fourier transform with $N = 512$ the spectrum $X(f)$ is in the form of samples spaced $f_{\rm A} = (N \cdot T_{\rm A})^{-1} \approx 1.953\,\text{kHz} $ before.
Increasing the DFT–parameter to $N= 2048$ results in a (four times) finer frequency grid with $f_{\rm A} \approx 488\,\text{Hz}$.

From the continuous to the discrete Fourier transform

From the conventional first Fourier integral

$$X(f) =\int_{-\infty }^{+\infty}x(t) \cdot {\rm e}^{-{\rm j} \hspace{0.05cm}\cdot \hspace{0.05cm} 2 \pi \hspace{0.05cm}\cdot \hspace{0.05cm} f \hspace{0.05cm}\cdot \hspace{0.05cm}t}\hspace{0.1cm} {\rm d}t$$

arises from discretisation $(\text{d}t \to T_{\rm A}$, $t \to \nu \cdot T_{\rm A}$, $f \to \mu \cdot f_{\rm A}$, $T_{\rm A} \cdot f_{\rm A} = 1/N)$ the sampled and periodised spectral function

$${\rm P}\{X(\mu \cdot f_{\rm A})\} = T_{\rm A} \cdot \sum_{\nu = 0 }^{N-1} {\rm P}\{x(\nu \cdot T_{\rm A})\}\cdot {\rm e}^{-{\rm j} \hspace{0.05cm}\cdot \hspace{0.05cm} 2 \pi \hspace{0.05cm} \cdot \hspace{0.05cm}\nu \hspace{0.05cm} \cdot \hspace{0.05cm}\mu /N} \hspace{0.05cm}.$$

It is taken into account that due to the discretisation, the periodised functions are to be used in each case.

For reasons of simplified notation, we now make the following substitutions:

The $N$ time-domain coefficients' are with the iterating variable $\nu = 0$, ... , $N - 1$:

$$d(\nu) =. {\rm P}\left\{x(t)\right\}{\big|}_{t \hspace{0.05cm}= \hspace{0.05cm}\nu \hspace{0.05cm}\cdot \hspace{0.05cm}T_{\rm A}}\hspace{0.05cm}.$$

Let $N$ frequency domain coefficients' be associated with the running variable $\mu = 0,$ ... , $N$ – 1:

$$D(\mu) = f_{\rm A} \cdot {\rm P}\left\{X(f)\right\}{\big|}_{f \hspace{0.05cm}= \hspace{0.05cm}\mu \hspace{0.05cm}\cdot \hspace{0.05cm}f_{\rm A}}\hspace{0.05cm}.$$

Abbreviation is written for the from $N$ dependent complex rotation factor' :

$$w = {\rm e}^{-{\rm j} \hspace{0.05cm}\cdot \hspace{0.05cm} 2 \pi /N} = \cos \left( {2 \pi}/{N}\right)-{\rm j} \cdot \sin \left( {2 \pi}/{N}\right) \hspace{0.05cm}.$$

On Defining the Discrete Fourier Transform (DFT) with $N=8$

$\text{Definition:}$

The term Discrete Fourier Transform (in short DFT) means the calculation of the $N$ spectral coefficients $D(\mu)$ from the $N$ signal coefficients $d(\nu)$:

$$D(\mu) = \frac{1}{N} \cdot \sum_{\nu = 0 }^{N-1} d(\nu)\cdot {w}^{\hspace{0.05cm}\nu \hspace{0.07cm} \cdot \hspace{0.05cm}\mu} \hspace{0.05cm}. $$

In the diagram you can see

the $N = 8$ signal coefficients $d(\nu)$ by the blue filling,
the $N = 8$ spectral coefficients $D(\mu)$ at the green filling.

Inverse discrete Fourier transform

The Inverse Discrete Fourier Transform (IDFT) describes the second Fourier integral

$$\begin{align*}x(t) & = \int_{-\infty }^{+\infty}X(f) \cdot {\rm e}^{\hspace{0.05cm}{\rm j} \hspace{0.05cm}\cdot \hspace{0.05cm} 2 \pi \hspace{0.05cm}\cdot \hspace{0.05cm} f \hspace{0.05cm}\cdot \hspace{0.05cm} t}\hspace{0.1cm} {\rm d}f\end{align*}$$

in discretized form:

$$d(\nu) = {\rm P}\left\{x(t)\right\}{\big|}_{t \hspace{0.05cm}= \hspace{0.05cm}\nu \hspace{0.05cm}\cdot \hspace{0.05cm}T_{\rm A}}\hspace{0.01cm}.$$

On the Definition of the IDFT with $N=8$

$\text{Definition:}$

The term Inverse Discrete Fourier Transform (in short IDFT) means the calculation of the signal coefficients $d(\nu)$ from the spectral coefficients $D(\mu)$:

$$d(\nu) = \sum_{\mu = 0 }^{N-1} D(\mu) \cdot {w}^{-\nu \hspace{0.07cm} \cdot \hspace{0.05cm}\mu} \hspace{0.05cm}.$$

With the run variables $\nu = 0, \hspace{0.05cm}\text{...} \hspace{0.05cm}, N-1$ und $\mu = 0, \hspace{0.05cm}\text{...} \hspace{0.05cm}, N-1$ gilt auch hier:

$$d(\nu) = {\rm P}\left\{x(t)\right\}{\big \vert}_{t \hspace{0.05cm}= \hspace{0.05cm}\nu \hspace{0.05cm}\cdot \hspace{0.05cm}T_{\rm A} }\hspace{0.01cm},$$

$$D(\mu) = f_{\rm A} \cdot {\rm P}\left\{X(f)\right\}{\big \vert}_{f \hspace{0.05cm}= \hspace{0.05cm}\mu \hspace{0.05cm}\cdot \hspace{0.05cm}f_{\rm A} } \hspace{0.01cm},$$

$$w = {\rm e}^{- {\rm j} \hspace{0.05cm}\cdot \hspace{0.05cm} 2 \pi /N} \hspace{0.01cm}.$$

A comparison between the DFT and IDFT shows that exactly the same algorithm can be used. The only differences between IDFT and DFT are:

The exponent of the rotation factor is to be applied with different sign.
In the IDFT, the division by $N$ is omitted.

Interpretation of DFT and IDFT

The graph shows the discrete coefficients in the time and frequency domain together with the periodified time-continuous functions.

Time– and Frequency range Coefficients of the DFT

When using DFT or IDFT, please note:

According to the above definitions, the DFT coefficients $d(ν)$ and $D(\mu)$ always have the unit of the time function.
Dividing $D(\mu)$ by $f_{\rm A}$, one obtains the spectral value $X(\mu \cdot f_{\rm A})$.
The spectral coefficients $D(\mu)$ must always be complex in order to be able to consider odd time functions.
In order to be able to transform band-pass signals in the equivalent low-pass–range, one usually also uses complex time coefficients $d(\nu)$.
The basic interval for $\nu$ and $\mu$ is usually defined as the range from $0$ to $N - 1$ (filled circles in the graph).
With the complex-valued number sequences $\langle \hspace{0.1cm}d(\nu)\hspace{0.1cm}\rangle = \langle \hspace{0.1cm}d(0), \hspace{0.05cm}\text{...} \hspace{0.05cm} , d(N-1) \hspace{0.1cm}\rangle$ and $\langle \hspace{0.1cm}D(\mu)\hspace{0.1cm}\rangle = \langle \hspace{0.1cm}D(0), \hspace{0.05cm}\text{...} \hspace{0.05cm} , D(N-1) \hspace{0.1cm}\rangle$ DFT and IDFT are symbolised similarly to the conventional Fourier transform:

$$\langle \hspace{0.1cm} D(\mu)\hspace{0.1cm}\rangle \hspace{0.2cm}\bullet\!\!-\!\!\!-(N)\!-\!\!\!-\!\!\hspace{0.05cm}\circ\, \hspace{0.2cm} \langle \hspace{0.1cm} d(\nu) \hspace{0.1cm}\rangle \hspace{0.05cm}.$$

If the time function $x(t)$ is already limited to the range $0 \le t \lt N \cdot T_{\rm A}$ then the time coefficients output by the IDFT directly give the samples of the time function: $d(\nu) = x(\nu \cdot T_{\rm A}).$
If $x(t)$ is shifted with respect to the basic interval, one has to choose the association shown in $\text{Example 3}$ between $x(t)$ and the coefficients $d(\nu)$ .

$\text{Example 3:}$ Die obere Grafik zeigt den unsymmetrischen Dreieckimpuls $x(t)$, dessen absolute Breite kleiner ist als $T_{\rm P} = N \cdot T_{\rm A}$.

On Assigning of the DFT Coefficients With $N=8$

The sketch below shows the assigned DFT coefficients $($valid for $N = 8)$.

For $\nu = 0,\hspace{0.05cm}\text{...} \hspace{0.05cm} , N/2 = 4$ $d(\nu) = x(\nu \cdot T_{\rm A})$ holds:

$$d(0) = x (0)\hspace{0.05cm}, \hspace{0.15cm} d(1) = x (T_{\rm A})\hspace{0.05cm}, \hspace{0.15cm} d(2) = x (2T_{\rm A})\hspace{0.05cm}, $$

$$d(3) = x (3T_{\rm A})\hspace{0.05cm}, \hspace{0.15cm} d(4) = x (4T_{\rm A})\hspace{0.05cm}.$$

On the other hand, the coefficients $d(5)$, $d(6)$ and d$(7)$ are to be set as follows:

$$d(\nu) = x \big ((\nu\hspace{-0.05cm} - \hspace{-0.05cm} N ) \cdot T_{\rm A}\big ) $$

$$ \Rightarrow \hspace{0.2cm}d(5) = x (-3T_{\rm A})\hspace{0.05cm}, \hspace{0.35cm} d(6) = x (-2T_{\rm A})\hspace{0.05cm}, \hspace{0.35cm} d(7) = x (-T_{\rm A})\hspace{0.05cm}.$$

Exercises for the chapter

Exercise 5.2: Inverse Discrete Fourier Transform

Exercise 5.2Z: DFT of a Triangular Pulse