5.5. The Discrete Fourier Transform

In this section, we will formally introduce the Discrete Fourier Transform (DFT). The DFT is the digital version of the Fourier transform, which was originally developed by Joseph Fourier in the early 19th century as a way to model heat flow with differential equations [Fou22]. The Fourier transform proved to be useful for many different applications, especially in audio and signal processing.

Many texts introduce the DFT by first starting with the continuous Fourier transform (using integral calculus), and then show the DFT as a discrete-time approximation of the continuous Fourier transform. We’ll take a different approach here, motivating the DFT from first principles entirely in the discrete time domain.

Aside: the Fast Fourier Transform

If you have previously come across the term Fast Fourier Transform (FFT), you might be wondering how the DFT relates to the FFT.

We’ll cover the FFT later in Fast Fourier Transform, but the key take-away is that the FFT is an algorithm for efficiently computing the DFT. It is not a separate transformation.

5.5.1. Dealing with phase

Recall that in the previous section, when we compare a sinusoid \(\blue{x[n]}\) to a collection of reference signals

\[\red{y_m[n] = \cos\left(2\pi \cdot \frac{m}{N} \cdot n \right)},\]

the resulting similarity score \(\purple{S(x, y_m)}\) depends on the phase of the signal, and whether or not the frequency of \(\blue{x}\) is an analysis frequency.

In the worst case, if

\[\blue{x[n] = \sin\left(2\pi \cdot \frac{m}{N}\cdot n \right) = \cos\left(2\pi \cdot \frac{m}{N}\cdot n - \frac{\pi}{2} \right),}\]

then the similarity score will be 0 even if the frequency matches one of our reference signals. This representation therefore cannot distinguish an out-of-phase sinusoid from a null signal \(x[n] = 0\).

5.5.1.1. Comparing to multiple references

In the specific case above, we could try to resolve the problem by changing the reference signals \(\red{y}\) to use \(\sin\) instead of \(\cos\). This will fix the problem if \(\blue{x}\) is a \(\sin\) wave, but then it will fail in exactly the same way if \(\blue{x}\) is a \(\cos\) wave.

But what if we try both?

Let’s see what happens if we take \(\blue{x}\) as a sinusoid at an analysis frequency with arbitrary phase, and compare it to two reference signals at the same frequency: one is \(\cos\) and one is \(\sin\).

In the following example, we’ll continue with the settings from the previous section: \(f_s = 20\) [samples / sec], \(N=40\) [samples], and \(\red{m=3}\) (equivalently, \(f_0 = 1.5\) [cycles/sec]). This gives an input signal

(5.9)\[\blue{x[n] = \cos\left(2\pi \cdot \frac{m}{N} \cdot n + \phi \right)}\]

where \(\phi\) is allowed to vary.

We’ll compare to reference signals

\[\red{\cos\left(2\pi \cdot \frac{m}{N} \cdot n\right)}, \quad\quad\text{and}\quad\quad \green{\sin\left(2\pi \cdot \frac{m}{N} \cdot n\right)}\]

Once Loop Reflect