S5-3.1 The DFT & Fast Fourier Transform

What this is and why it exists

A computer cannot evaluate a continuous Fourier transform. It holds a finite list of numbers, not a function.

The discrete Fourier transform is the version it can evaluate. The fast Fourier transform is what made evaluating it affordable. Between them they turned frequency analysis from a piece of theory into a routine operation.

The vocabulary

• DFT — the discrete Fourier transform. It turns a finite list of samples into a finite list of frequency values.
• Twiddle factor — the complex number the transform multiplies by at each step.
• FFT — a family of algorithms that compute the DFT with far less work.
• Radix-2 — an FFT that repeatedly splits the sequence in half.
• Decimation in time — splitting the input sequence into even and odd samples.
• Decimation in frequency — splitting the output sequence instead.
• Butterfly — the two-input, two-output operation the algorithm repeats.
• In-place computation — writing each result over an input that is no longer needed.
• Bit reversal — the reordering that in-place computation forces on one end.
• Circular convolution — the wrap-around convolution the DFT actually performs.
• Overlap-add and overlap-save — the two ways of getting ordinary convolution from circular convolution.

The mental model

Start with the cost, because the saving means nothing without it. Computing the DFT directly means, for each of the outputs, a sum over all the inputs. With a sequence of length N that is about N times N complex multiplications. Double the length and the work goes up four times. For a long recording that is unaffordable.

The redundancy is what the FFT exploits. The same twiddle factors appear again and again across those sums. Split the sequence in half and much of the work is shared between the halves. Split each half again and more is shared. Keep splitting and the cost falls to about N times the logarithm of N. For a sequence of a thousand points that is roughly a hundredfold saving.

There are two ways to do the splitting. Decimation in time separates the input into even-numbered and odd-numbered samples. Decimation in frequency separates the outputs into the first half and the second half. Both reach the same saving. Their flow graphs are near mirrors of each other. Learn one butterfly properly and read the other beside it, rather than memorising both.

In-place computation is what keeps the memory small. Each butterfly takes two values and produces two, so the results can be written over the inputs. The cost of that is ordering. One end of the algorithm needs its samples in bit-reversed order, meaning the index with its binary digits written backwards. It looks like a curiosity until you implement it, and then it is a real piece of work.

The payoff is linear filtering. Convolution in time is multiplication in frequency, so a long convolution can be done by transforming, multiplying and transforming back. That is far cheaper than the direct sum.

There is a trap, and it is the reason the DFT properties are worth knowing well. The DFT treats a sequence as if it repeats forever, so multiplying two transforms gives circular convolution, not ordinary convolution. The end of the result wraps round and corrupts the start. Padding with zeros gives enough room to avoid it. Overlap-add and overlap-save are the two standard ways of applying that idea to a stream too long to transform at once.

What you should now be able to explain or do

Compute a short DFT and use its properties. Say why the direct computation costs about N squared operations and where the redundancy is. Draw a radix-2 butterfly and explain how the two decimation schemes differ. Explain in-place computation and why bit reversal follows from it. Filter a long signal with the FFT, and say why overlap-add or overlap-save is needed.

Check yourself