# The Discrete Fourier Transform

## Contents

# 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.

## 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

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

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

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

We’ll compare to reference signals