The Fourier Transform: From Time to Frequency

Magnitude and Phase

The DFT produces complex numbers — each $X[k]$ has both a magnitude ($|X[k]|$) and a phase ($\angle X[k]$).

Each bin $X[k]$ can be written as:

$X[k] = a + jb$

Using Euler's identity, the DFT can be rewritten as:

$X[k] = \sum_{n=0}^{N-1} x[n] \cdot \cos\left(\frac{2\pi}{N} k n\right) - j \sum_{n=0}^{N-1} x[n] \cdot \sin\left(\frac{2\pi}{N} k n\right)$

From this, the real and imaginary parts are:

$a = \sum_{n=0}^{N-1} x[n] \cdot \cos\left(\frac{2\pi}{N} k n\right)$
$b = -\sum_{n=0}^{N-1} x[n] \cdot \sin\left(\frac{2\pi}{N} k n\right)$

The real part $a$ tells us how much of the signal matches a cosine at frequency $k$. The imaginary part $b$ tells us how much matches a sine. Together, they determine both the magnitude and the phase of that frequency component.

From $a$ and $b$, we obtain:

$|X[k]| = \sqrt{a^2 + b^2}$
$\angle X[k] = \operatorname{atan2}(b, a)$

Depending on the chosen normalisation, the magnitude may need to be scaled to recover the actual sinusoidal amplitude. The magnitude indicates the strength of the sinusoidal component at frequency $f_k$. The phase specifies its relative alignment with respect to the chosen time origin. Two signals with identical magnitude spectra but different phase spectra can have completely different time-domain shapes.

The phase is essential for reconstruction. Without it, the inverse DFT would not be possible. It carries the structural information needed to recover the original signal.

In practice, engineers often discard the phase and look only at the magnitude spectrum — for example, when analysing the frequency content of an audio signal or detecting harmonics. In other applications, such as radar or communications, the phase is equally important, as it carries information about timing or distance.

The figure above illustrates the Fourier decomposition of a signal. The time-domain signal (left) is a sum of three sinusoids at 5 Hz, 12 Hz, and 25 Hz. The DFT (right) reveals these frequencies as distinct peaks. This is the essence of frequency-domain analysis: it shows what frequencies are present and how strong each one is.

Fourier Series vs Fourier Transform

A common point of confusion is the distinction between Fourier series and the Fourier transform. A Fourier series represents a periodic signal as a discrete sum of sinusoids (harmonics). The Fourier transform generalises this to non-periodic signals, replacing the sum with an integral over all frequencies. For discrete signals, the DFT is the practical implementation.

Among these, the DFT is the one used in practice, typically implemented via the Fast Fourier Transform (FFT) algorithm.

Filtering in the Frequency Domain

One of the most powerful applications of the Fourier transform is frequency-domain filtering. The convolution theorem states that convolution in the time domain is equivalent to multiplication in the frequency domain:

$x[n] * h[n] \leftrightarrow X[k] \cdot H[k]$

This is a cornerstone of DSP. It means that if we want to filter a signal — for example, to remove high-frequency noise — we can:

• Transform the signal into the frequency domain using the DFT.
• Multiply its spectrum $X[k]$ by a filter function $H[k]$ that attenuates unwanted frequencies.
• Transform back to the time domain using the inverse DFT.

This is how a low-pass filter removes high-frequency noise, how a high-pass filter removes slow drifts, and how a band-pass filter isolates a specific frequency band. The filter function $H[k]$ acts as a mask in the frequency domain.

In practice, the filter is often designed in the frequency domain by specifying the desired response: unity gain (1.0) for frequencies to preserve, and zero gain (0.0) for frequencies to reject. More sophisticated designs use gradual transitions to avoid artefacts.

Frequency-domain filtering is not just theoretical — it is widely used in audio processing, image processing, radar, telecommunications, and biomedical signal analysis.

The Fast Fourier Transform (FFT)

The DFT is defined as a sum over $N$ samples for each of $N$ frequency bins. This results in $O(N^2)$ operations — acceptable for small $N$, but impractical for long signals.

The Fast Fourier Transform (FFT) is a family of algorithms that compute the DFT in $O(N \log N)$ operations — not an approximation, but exactly the same result, computed more efficiently. The savings are substantial. For a 1024‑point DFT, the FFT reduces the computational effort by a factor of roughly 100; for a 1,000,000‑point DFT, the factor is closer to 50,000.

How does it achieve this? It splits the signal into even and odd samples, computes smaller DFTs for each half, and combines the results — recursively, again and again. This divide‑and‑conquer strategy eliminates a huge number of redundant calculations.

There are two main variants: decimation‑in‑time (DIT), which splits the input sequence, and decimation‑in‑frequency (DIF), which splits the output. In both cases, the computational cost drops from $N^2$ to $N \log N$.

Without the FFT, real-time spectrum analysis (mobile communications, medical imaging) simply would not be feasible in practice.

Once the Fourier transform is understood, the next step is to explore how it is implemented in practice. The FFT implementation guide covers the algorithmic details, optimisations, and practical considerations for embedded systems.