Fourier Transform and Convolution Theorem

Rewrite a signal by frequency instead of by time. Convolution then becomes pointwise multiplication, which is why fast filtering works.

Signals f and g transform to spectra F and G, pointwise multiply to F times G, then invert to the convolution 6, 11, 4

Why Does This Exist?

Smoothing, filtering, and detecting patterns all convolve: slide a kernel across a signal and accumulate. Directly that costs length-times-length work, which is why long audio filters and large image blurs were once impractical. Frequency thinking removes the bottleneck.

The Fourier transform rewrites the signal by frequency instead of by time. In that domain the convolution theorem turns sliding convolution into pointwise multiplication: transform both sides, multiply bin by bin, invert once. Fast convolution through the discrete Fourier transform and FFT is the payoff, built on the sliding mechanics in convolution mathematics.

The one idea you need first

A sinusoid at frequency $k$ is a pure tone. Here $F_{k}$ means how much of that tone the signal contains, with magnitude for strength and angle for shift. The building sines and cosines come from trigonometry: $e^{-2\pi i k t / n} = \cos(2\pi k t / n) - i \sin(2\pi k t / n)$ . The transform just measures the signal against each tone in turn.

Think of It Like This

Chords instead of key presses

A piano roll lists every key press in time order. A chord chart lists which notes sound together and how loudly, ignoring when each began. Same music, different index: time versus frequency.

Convolution in piano-roll form is tedious: every echo of every note overlaps every other. In chord-chart form each note multiplies independently, since echoes only scale and shift each tone. Multiply the charts, convert back to a roll, and the echoes are all placed. Where the analogy stops: real spectra carry phase as well as magnitude, and discarding phase destroys timing while the chord chart still looks right.

How It Actually Works

For length $n$ , the discrete transform and its inverse pair measurements with tones. Here $x_{t}$ is the time sample at index $t$ , $X_{k}$ is the spectrum bin at frequency $k$ , and $i$ is the imaginary unit:

X_{k} = \sum_{t=0}^{n-1} x_{t} e^{-2\pi i k t / n}, \quad x_{t} = \frac{1}{n} \sum_{k=0}^{n-1} X_{k} e^{2\pi i k t / n}

The convolution theorem says pointwise multiplication in one domain is convolution in the other. With $*$ for convolution and $\cdot$ for pointwise product, and $\mathcal{F}$ for the transform:

\mathcal{F}\{f * g\} = \mathcal{F}\{f\} \cdot \mathcal{F}\{g\}, \quad f * g = \mathcal{F}^{-1}\{\mathcal{F}\{f\} \cdot \mathcal{F}\{g\}\}

Direct convolution of length $n$ costs $O(n^{2})$ multiplies: 64 for $n = 8$ . The FFT costs $O(n \log n)$ : $8 \times 3 = 24$ steps for the same size, over two times fewer, widening fast as $n$ grows. Zero-pad both inputs to a shared length first, so linear convolution matches the circular form the theorem computes.

Worked example

Pad to length 4 with $f = [2, 1, 0, 0]$ and $g = [3, 4, 0, 0]$ . Direct linear convolution slides and accumulates:

2 \times 3 = 6, \quad 2 \times 4 + 1 \times 3 = 11, \quad 1 \times 4 = 4

So $f * g = [6, 11, 4, 0]$ . Through the theorem, transform both to $F$ and $G$ , multiply pointwise $P_{k} = F_{k} G_{k}$ at each of the 4 bins, and invert: the inverse transform of $P$ returns $[6.0, 11.0, 4.0, 0.0]$ , matching the slide-and-sum exactly. Same numbers, two routes, which is the theorem as an executable identity.

Code

The point is the check: verify the theorem on the worked example with standard-library complex arithmetic only.

1import cmath2import math3
4
5def dft(x: list[float]) -> list[complex]:6    n = len(x)7    return [sum(v * cmath.exp(-2j * math.pi * k * t / n) for t, v in enumerate(x)) for k in range(n)]8
9
10def idft(X: list[complex]) -> list[complex]:11    n = len(X)12    return [sum(v * cmath.exp(2j * math.pi * k * t / n) for k, v in enumerate(X)) / n for t in range(n)]13
14
15f = [2.0, 1.0, 0.0, 0.0]16g = [3.0, 4.0, 0.0, 0.0]17prod = [a * b for a, b in zip(dft(f), dft(g))]18back = [round(v.real, 6) for v in idft(prod)]19print(back)20# -> [6.0, 11.0, 4.0, 0.0]21print(8 * 8, 8 * 3)22# -> 64 24

The inverse lands on $[6.0, 11.0, 4.0, 0.0]$ from the hand computation, and 64 naive multiplies drop to 24 FFT steps at $n = 8$ . The code is the theorem, evaluated where the page reasons about it.

Watch Out For

Convolving without padding and reading wrap-around as signal

The DFT form is circular: energy that slides past the end wraps to the start. Without zero-padding to at least length $m + n - 1$ , the tail of the true convolution lands on the head of the computed one and no error is raised.

Symptom: filtered output starts with a ghost of its own ending. Fix: pad both inputs to the FFT length before transforming, and trim after inverting. If the first samples look like the last, suspect wrap-around before suspecting the kernel.

Multiplying magnitudes and dropping phase

Magnitude spectra are tempting to display and easy to multiply alone, but timing lives in phase. Multiplying magnitudes while ignoring angles keeps energy right and places events wrong.

Symptom: the spectrum product looks correct yet the inverted signal smears or shifts. Fix: always carry full complex bins through the product, and treat any magnitude-only pipeline as a detector, never as a reconstruction.

The Quick Version

The Fourier transform indexes a signal by frequency instead of by time.
The convolution theorem turns convolution into pointwise multiplication of spectra.
Zero-padded $[2, 1]$ convolved with $[3, 4]$ gives $[6, 11, 4]$ by either route.
Direct convolution costs $O(n^{2})$ while the FFT costs $O(n \log n)$ : 24 steps versus 64 at $n = 8$ .
Pad to avoid circular wrap-around, and always carry phase through the product.