The Fourier Transform: From Time to Frequency

The Fourier Transform: From Time to Frequency

Imagine a piano chord. You hear a single sound, but in reality, it is a sum of several individual notes sounding simultaneously. The Fourier transform does exactly that with any signal — it takes something complex and "untangles" which simple oscillations (sinusoids) compose it and how strongly each one is present.

That is the whole idea. Everything else in this article is simply about how to write down and compute this "untangling".

There are two ways to look at a signal:

• Time domain — the signal as a sequence of values changing over time (the way it appears on an oscilloscope).
• Frequency domain — the same signal, but described by which frequencies are present and with what strength.

The Fourier transform is the bridge between these two perspectives.

The Continuous Fourier Transform

The continuous Fourier transform is defined as:

$X(f) = \int_{-\infty}^{\infty} x(t) e^{-j2\pi ft} dt$

Do not be alarmed by the complex exponential $e^{-j2\pi ft}$ — it is simply a compact way to describe both sine and cosine simultaneously (via Euler's identity). The idea behind the formula is simple: for every possible frequency $f$, it checks "how well does the signal match a pure sinusoid at this frequency?" The result $X(f)$ tells us two things:

• Magnitude $|X(f)|$ — how strongly this frequency is present.
• Phase $\angle X(f)$ — how the component is shifted in time.

The inverse Fourier transform recovers the original signal from its spectrum:

$x(t) = \int_{-\infty}^{\infty} X(f) e^{j2\pi ft} df$

In practice, however, computers do not work with continuous time and infinite precision. Before any computation, the signal must go through two steps:

• Sampling — taking measurements of the signal at regular intervals (e.g., 44,100 times per second for audio).
• Quantisation — rounding each sampled value to the nearest level from a finite set (e.g., 65,536 levels for 16‑bit recording).

Both steps exist for a simple reason: digital systems can only store finite numbers, not infinite precision.

The Discrete Fourier Transform (DFT)

It is worth clarifying what discrete actually means. A discrete signal is one that is defined only at specific instants in time — typically at equally spaced intervals. This is the result of sampling, the process of taking measurements of a continuous signal at regular intervals (every $T$ seconds).

Sampling is not the only step. In a digital system, the sampled values must also be represented as numbers with finite precision. This is called quantisation — the process of mapping each continuous amplitude value to a discrete level from a finite set. The number of available levels depends on the bit depth of the system (e.g., 8‑bit gives 256 levels, 16‑bit gives 65,536 levels).

Both sampling and quantisation are necessary because digital processors cannot handle continuous time or infinite precision. They can only operate on finite sequences of numbers.

The figure above illustrates the two key steps in converting a continuous signal into a digital representation. The left plot shows the continuous signal (blue) and the discrete samples taken at regular intervals (red). The right plot shows the sampled points (red) and the quantised values (green) after rounding to the nearest available level. The quantisation levels are shown as faint dashed lines.

After sampling and quantisation, we obtain a signal represented as a finite list of numbers: $x[0], x[1], ..., x[N-1]$. This is exactly the list that the Discrete Fourier Transform (DFT) processes.

For a discrete signal $x[n]$ of length $N$, where $n$ is the sample index $(n = 0, 1, ..., N-1)$, the DFT is defined as:

$X[k] = \sum_{n=0}^{N-1} x[n] \cdot e^{-j \frac{2\pi}{N} k n}$

The DFT transforms N time-domain samples into N frequency-domain bins. Each bin $k$ corresponds to a specific frequency:

$f_k = \frac{k \cdot f_s}{N}$

where $f_s$ is the sampling frequency. The first bin ($k = 0$) represents DC — the average value of the signal. The bin at $k = N/2$ represents the Nyquist frequency — the highest frequency that can be represented without aliasing.

An important point about the DFT is that it assumes the signal is periodic — the finite segment of length $N$ is treated as one period of an infinitely repeating sequence. If the signal is not periodic within the analysis window, spectral leakage occurs. This is precisely why window functions are needed.

The DFT is a linear transform, which means superposition holds: the transform of a sum of signals is the sum of their transforms. This property is what makes frequency-domain filtering possible.

A Concrete Example: Computing One DFT Coefficient

Let us immediately see what the DFT does in practice. Consider the signal $x[n] = [1, 0, -1, 0]$ (four numbers, $N = 4$). We want to compute $X[2]$.

Substitute $k = 2$ into the DFT formula:

$X[2] = \sum_{n=0}^{3} x[n] \cdot e^{-j \pi n}$

because $\frac{2\pi}{4} \cdot 2 = \pi$.

Expanding the sum:

$X[2] = 1 \cdot e^{0} + 0 \cdot e^{-j\pi} + (-1) \cdot e^{-j2\pi} + 0 \cdot e^{-j3\pi}$

Using Euler's identity, $e^{-j\pi n}$ gives values $1, -1, 1, -1$ for $n = 0, 1, 2, 3$ respectively. Thus:

$X[2] = 1 \cdot 1 + 0 \cdot (-1) + (-1) \cdot 1 + 0 \cdot (-1) = 0$

Therefore, $X[2] = 0$ — the signal has no energy at the frequency corresponding to $k = 2$ (the Nyquist frequency). This makes sense: the signal $[1, 0, -1, 0]$ repeats every two samples, not every four, so it does not match that frequency component.

With this example in mind, the remaining concepts become easier to absorb.

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.

Example: Given $x[n] = [1, 0, -1, 0]$, compute the DFT magnitude for $k = 0, 1, 2, 3$.

Computing one DFT coefficient (k=2)

Given the signal $x[n] = [1, 0, -1, 0]$ with $N = 4$, the DFT formula is:

$X[k] = \sum_{n=0}^{3} x[n] \cdot e^{-j \frac{2\pi}{4} k n}$

For $k = 2$, this becomes:

$X[2] = \sum_{n=0}^{3} x[n] \cdot e^{-j \pi n}$

because $\frac{2\pi}{4} \cdot 2 = \pi$.

Now expand the sum for each $n$:

$X[2] = x[0] \cdot e^{-j \pi \cdot 0} + x[1] \cdot e^{-j \pi \cdot 1} + x[2] \cdot e^{-j \pi \cdot 2} + x[3] \cdot e^{-j \pi \cdot 3}$

Substitute the signal values $x[0] = 1$, $x[1] = 0$, $x[2] = -1$, $x[3] = 0$:

$X[2] = 1 \cdot e^{0} + 0 \cdot e^{-j\pi} + (-1) \cdot e^{-j2\pi} + 0 \cdot e^{-j3\pi}$

Simplify using Euler's identity. Recall that:

• $e^{0} = 1$
• $e^{-j\pi} = -1$
• $e^{-j2\pi} = 1$
• $e^{-j3\pi} = -1$

Thus:

$X[2] = 1 \cdot 1 + 0 \cdot (-1) + (-1) \cdot 1 + 0 \cdot (-1) = 1 - 1 = 0$

Therefore, $X[2] = 0$.

Interpretation: The signal $x[n] = [1, 0, -1, 0]$ contains no energy at frequency $k = 2$ (which corresponds to $f = f_s/2$, the Nyquist frequency). This makes sense because the signal alternates every two samples, which is a different frequency component.

References:

Alan V. Oppenheim and Ronald W. Schafer, Discrete-Time Signal Processing, Prentice Hall, 3rd edition, 2010.

John G. Proakis and Dimitris G. Manolakis, Digital Signal Processing: Principles, Algorithms, and Applications, Pearson, 4th edition, 2006.

Richard G. Lyons, Understanding Digital Signal Processing, Pearson, 3rd edition, 2010.

Steven W. Smith, The Scientist and Engineer's Guide to Digital Signal Processing, California Technical Publishing, 1997. (Available online at dspguide.com)

Bob Meddins, Introduction to Digital Signal Processing, Butterworth-Heinemann, 2000.

See also: FFT Implementation Guide | Window Functions Overview