Discrete Fourier Transform

Definition¶

The discrete-time equivalent of the Fourier transform is the Discrete Fourier Transform (DFT). The DFT works like the continuous-time Fourier transform - but diecrete. Most notably, the integral is replaced with the sum. The complex DFT $X[k]$ of a discrete signal $x[n]$ with the length $N$ is calculated as follows:

$$ \begin{eqnarray} X[k] & = & \sum\limits_{n=0}^{N-1} x[n] e^{-j 2 \pi k \frac{n}{N}} \\ \end{eqnarray} $$

As with the contious Fourier transform, the inverse DFT can calculate the time-domain signal of a complex signal in the frequency domain:

$$ \begin{eqnarray} x[n] & = & \frac{1}{N} \sum\limits_{k=0}^{N-1} X[k] e^{j 2 \pi k \frac{n}{N}} \\ \end{eqnarray} $$

Euler¶

With the help of euler's formula, the DFT can be expressed through sine and cosine:

$$ \begin{eqnarray} X[k] & = & \sum\limits_{n=0}^{N-1} x[n] e^{-j 2 \pi k \frac{n}{N}} \\ & = & \sum\limits_{n=0}^{N-1} x[n] \left( \cos \left(2 \pi k \frac{n}{N} \right) -j \sin \left( 2 \pi k \frac{n}{N} \right) \right) \\ \end{eqnarray} $$

Every Detail¶

For every frequency bin $k=0 ... N-1, N \in \mathbb{N}$ of $X[k]$, the correlation of the signal with a complex oscillation is calculated.

$k$ is the frequency index.
$\frac{n}{N}$ represents the time vector.

DFT of a Sine¶

The animation below visualizes the complete DFT process for a sine with a length of $N=100$ and a frequency of $10$ (not in Hz, since there is no time in seconds). The upper plot shows the input signal $x[n]$. The middle plot shows the real and imaginary component of $ e^{-j 2 \pi k \frac{n}{N}}$ The lower plot shows real and imaginary part of the resulting DFT, adding each bin stepwise.

No description has been provided for this image

A positive peak occurs for the imaginary part at $k=10$.
Negative frequencies occur after $n/N=0.5$ (resulting in a phase shift of $\pi$).
A negative peak occurs for the imaginary part at $N-10-1$.

DFT of a Cosine¶

The animation below shows the same process for a cosine.

A positive peak occurs for the real part at $k=10$.
Negative frequencies occur after $n/N=0.5$ (resulting in a phase shift of $\pi$).
A positive peak occurs for the real part at $N-10-1$.

Magnitude Spectrum¶

DFT results are most commonly plotted as magnitude spectra:

$$ |X[k]| = \sqrt{\mathcal{Re}^2(X[k]) + \mathcal{Im}^2(X[k])} $$

In this representation, both sine and cosine are identical:

DFT Bins & Frequency Resolution¶

The length of the output signal of a DFT has the same length as the input signal. The elements of a DFT vector are called bins. For a DFT with $N$ points, the DFT bins $f[k]$ - or support points - are located at the following frequencies:

$$ f[k] = k \frac{f_s}{N} $$

The frequency resolution - that is the $\Delta f$ between two neighboring bins - of the DFT for a signal with the sampling rate $f_s$ can be obtained as the derivative of $f[k]$:

$$ \Delta f = k \frac{f_s}{N} dk = \frac{f_s}{N} $$

The above equation shows that the frequency resolution of the DFT depends on both the length of the input signal and the sampling rate: The longer the signal, the higher the resolution.

Fast Fourier Transfor (FFT)¶

In DSP, the Fast Fourier Transform is used as the standard instead of the DFT. The FFT delivers the exact same results a DFT does, but it uses more advanced algorithms in the implementation. The split-radix FFT, for example, makes use of the symmetry in the FFT to significantly reduce the number of computations needed.