\begin{equation} \label{eq:DFT} \sum_{k=0}^{n-1} x[k] \omega_{n}^{\mu k} \end{equation}

Deriving the discrete Fourier transformation

The discrete Fourier transformation (\ref{eq:DFT}), hence forth abbreviated with “DFT”, can be derived from the Fourier transformation by use of the Fourier Series. Given any continuous signal \(x_0(t)\) and it’s spectrum \(X_0(t)\). We define \(x_p(t)\) as the periodic continuation of \(x_0(t)\) in the time domain which corresponds to a sampling of the spectrum.

\begin{equation} x_p(t) = \sum_{k=-\inf}^{\inf} x_0(t - kT) = \frac{1}{T} \sum_{\nu=-\inf}^{\inf} X_0(\nu/T)e^{j2\pi\nu t/T} \end{equation}

Second, sampling in the time domain with sampling period \(T_A = T/M\), \(M\) being the sampling values per minute. This corresponds to a periodic continuation of the spectrum.

Fourier Matrix

The DFT can be represented by a matrix multiplication of the discrete Fourier matrix \(A\) with the discrete signal \(x\) which holds the individual samples \(x(i)\).

\begin{equation} X = Ax \end{equation}

Example \(n = 4\)

\[A_4 = \begin{bmatrix} \omega^0 & \omega^0 & \omega^0 & \omega^0 \\ \omega^0 & \omega^1 & \omega^2 & \omega^3 \\ \omega^0 & \omega^2 & \omega^4 & \omega^6 \\ \omega^0 & \omega^4 & \omega^6 & \omega^9 \\ \end{bmatrix} = \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & -j & -1 & j \\ 1 & -1 & 1 & -1 \\ 1 & j & -1 & j \\ \end{bmatrix}\]

This matrix is special in multiple ways. Additionally, to it obviously being quadratic, it is also orthogonal meaning that the inner product of any row with any other row is always zero.

Fast Fourier Transform

The fast Fourier transform is an algorithm to efficiently calculate the discrete Fourier transform which itself is a subset of the Fourier transform. The fast Fourier transform or FFT algorithm described here was derived by James Cooley and John W. Tukey about 1965 but just like with all things in math, Gauß used some version of it 100 years before everyone else.

Step 1

When calculating the FFT on a finite set of discrete numerical values the first step is to permute the order of the indices by recursively splitting the sequence of length m in two by separating every second index into a new sequence and repeating this until there are m/2 sequences with only two indices. Luckily this corresponds to the binary representation of the index being reversed, e.g. flipping the MSB and LSB. In hardware, this is easily accomplished by reversing the address register. Matlab has the bitrevorder function for this. But this also demonstrates a major drawback of the algorithm as it can only be performed on a sequence of 2^n length n being a natural number.

Step 2

After reordering the indices the individual frequency components are calculated using the butterfly graph.

All sequences in the time domain are to be thought of as periodically continued. By correspondence of the Fourier transform this implies that the spectrum of the signal is discrete and since the signal is discrete the spectrum is also periodic.

Sources

  • Prof. Dr.-Ing. Robert Fischer. Signale und Systeme Skriptum. 2020. - Universität Ulm, Institut für Nachrichtentechnik
  • https://www.youtube.com/watch?v=M0Sa8fLOajA