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.