The fast Fourier transform feels like a trapdoor in the floor.

Walk through it, multiply two spectra, walk back, and convolution becomes fast. That sentence is true often enough to be dangerous.

The missing clause is:

the DFT thinks your finite signal is one lap around a ring

If the convolution result fits inside that lap, everything is fine. If it does not, the tail does not fall off the edge. It wraps around and adds itself to the beginning.

This is not a bug in the FFT. It is the room you walked into.

On a Line, the Tail Has Somewhere to Go

For two finite sequences (x[n]) and (h[n]), linear convolution is

\[y[n] = \sum_m x[m]h[n-m].\]

If (x) has length (L) and (h) has length (M), then (y) has length

\[L + M - 1.\]

That extra (M-1) is the tail. It is where the last nonzero samples of the signal still overlap the filter.

In the time domain, the direct algorithm is almost embarrassingly literal:

for each signal sample
  add a shifted copy of the filter

It costs (O(LM)). That is fine for small filters. It is painful for long filters, large images, long audio, and repeated convolutions inside numerical pipelines.

The Fourier-domain story says convolution in time becomes multiplication in frequency. MIT lecture notes state the continuous version in the familiar form: the Fourier transform of a convolution is a product.1 The discrete version is what makes FFT convolution useful in code.

The Fast Door Opens Into a Ring

The DFT of (N) samples can be computed directly in (O(N^2)). Cooley and Tukey’s 1965 paper gave the classic fast algorithm for composite lengths, factoring the calculation into sparse stages and reducing the work to proportional to (N\log N) rather than (N^2).2

So the tempting recipe is:

FFT(x)
FFT(h)
multiply pointwise
inverse FFT

That recipe is incomplete.

The (N)-point DFT does not represent an isolated length-(N) vector. It represents one period of an (N)-periodic signal. The DSP Guide puts this plainly: the DFT views the time domain as a periodic signal with (N) samples per period.3

Therefore multiplication of two (N)-point DFTs gives (N)-point circular convolution:

\[y_N[n] = \sum_{m=0}^{N-1} x_N[m]h_N[(n-m)\bmod N].\]

The modulo is the ring.

Linear convolution becomes circular convolution when you identify sample (N) with sample (0). If the true linear result has nonzero samples beyond (N-1), those samples fold back.

Zero Padding Is a Boundary Condition

To get linear convolution from DFT multiplication, pad both inputs with enough zeros that the linear output fits into one period:

\[N \ge L + M - 1.\]

Then the circular convolution has nowhere to wrap. MathWorks states the same rule for linear and circular convolution: for vectors of lengths (P) and (Q), pad to length at least (P+Q-1), then keep the first (P+Q-1) samples.4 University of Illinois lecture notes give the equivalent condition (N \ge L + M - 1).5

That is the whole contract.

short FFT length: fast ring convolution
long enough FFT length: linear convolution via a ring large enough not to wrap

Zero padding is not decoration. It is the boundary condition that tells the DFT how much silence exists after your finite signal.

Make the Tail Wrap on Purpose

The lab below builds a finite signal, a finite smoothing kernel, and compares:

  1. direct linear convolution,
  2. FFT convolution on the selected ring length,
  3. properly padded FFT convolution.

The default is intentionally under-padded: a length-64 FFT tries to hold a length-96 convolution. The tail wraps into the beginning. Increase FFT ring length to 128 and the aliasing vanishes.

Linear convolution FFT ring output Wrapped tail Signal spectrum

Deterministic toy experiment. The FFT implementation is a plain radix-2 Cooley-Tukey transform written for the article. The operation bars are a rough model, not a benchmark of browser performance or optimized libraries.

The first useful move is deliberately boring: raise FFT ring length to 128. The required length remains 96, but the ring is now large enough. The alias metrics drop to zero and the padded FFT error is down at floating-point noise.

Now increase Kernel length. The tail grows. If the ring length does not grow with it, more of the linear output has to fold back into the first samples.

Finally change Tone mixture. The spectrum panel changes, but the padding rule does not. Frequency content affects how the convolution looks; support length determines whether the finite DFT has enough room.

The Edge Is a Policy

The ring is not always wrong.

If your domain is naturally periodic, circular convolution may be exactly the model you want. Texture synthesis, phase vocoders, spectral methods on periodic domains, and some simulation grids deliberately use wraparound boundaries.

If your domain is not periodic, circular convolution is a boundary artifact. Images blur across the left and right edges. Audio tails wrap to the beginning. Finite signals acquire ghosts from their own future.

Zero padding says:

outside the observed support, pretend the signal is zero

Reflection padding says something else. Replication padding says something else. Periodic padding says something else. Every boundary condition is a modeling choice wearing an implementation costume.

Speed Has Setup Costs

FFT convolution has overhead. You transform both inputs, multiply complex spectra, then inverse transform. For small filters, direct convolution can be faster because it is simple, cache-friendly, and has tiny constants. For long filters or large batches, the (N\log N) scaling wins.

Production systems also avoid doing one giant transform when streaming. They use overlap-add or overlap-save: split the signal into blocks, FFT each block with padding, multiply by the filter spectrum, then stitch together the valid regions. The same ring rule is still present. The block algorithm merely manages where the wrapped samples are allowed to go.

This is why FFT convolution belongs in a systems notebook, not only a signal processing textbook. The math gives an identity. The implementation has to choose:

  • the transform length,
  • the padding rule,
  • the block size,
  • the boundary condition,
  • the point where direct convolution beats FFT overhead.

The speedup is real. The boundary is part of the API.

Remember the Shape of the Room

The convolution theorem is beautiful because it turns a global sliding sum into local multiplication in a different basis.

But the finite DFT basis is periodic. It tiles the world. That is why the FFT can be both astonishingly fast and quietly wrong at the edges.

The safe sentence is:

FFT multiplication computes circular convolution.
Zero padding makes that circle large enough to contain the line.

Once you remember the ring, the magic door becomes an engineering tool again.

Reading Trail

  1. MIT OpenCourseWare, “Introduction to Neural Computation,” Lecture 12, includes the convolution theorem: convolution in time corresponds to multiplication in frequency. PDF. ↩

  2. James W. Cooley and John W. Tukey, “An Algorithm for the Machine Calculation of Complex Fourier Series,” Mathematics of Computation, 1965. PDF, Semantic Scholar. ↩

  3. Steven W. Smith, The Scientist and Engineer’s Guide to Digital Signal Processing, Chapter 9, “Convolution via the Frequency Domain.” Online chapter, chapter PDF. ↩

  4. MathWorks, “Linear and Circular Convolution.” Documentation. ↩

  5. University of Illinois ECE 401, “Lecture 24: Circular Convolution,” notes on zero-padding circular convolution to obtain linear convolution. PDF. ↩