OE-8.3 The Fast Fourier Transform

What this is and why it exists

The fast Fourier transform is not a different transform. It is the discrete Fourier transform computed cleverly.

Say that first, because the name suggests otherwise and the misunderstanding lasts for years. Same input, same output, different arithmetic.

What it changes is the cost, and that single change is why digital signal processing became practical at all. Direct computation costs work proportional to the square of the length. This costs work proportional to the length times its logarithm.

The vocabulary

• Divide and conquer — splitting a problem into halves solved separately.
• Radix-2 — the version that repeatedly halves, requiring a power-of-two length.
• Decimation in time — splitting the input sequence into even and odd samples.
• Decimation in frequency — splitting the output instead.
• Butterfly — the two-input, two-output operation the whole algorithm is built from.
• Bit-reversed order — the reordering the splitting produces.
• In-place — writing results over the input, using no extra array.

The mental model

The saving comes from divide and conquer, which you have already met in sorting. Split the sequence in two, transform each half, and combine. The combination turns out to be cheap, because the two halves share almost all their work.

Work out what that recursion costs and you get length times logarithm rather than length squared. For a thousand points that is roughly a hundredfold saving. For a million points it is a factor of tens of thousands, which is the difference between an idea and a product.

There are two routes to the same saving. Decimation in time splits the input into even-indexed and odd-indexed samples. Decimation in frequency splits the output instead. Learn one thoroughly and recognise the other; they are two views of the same restructuring, and learning both from scratch is wasted effort.

The butterfly is the operation everything is built from: two values in, two out, one multiplication and two additions. Draw a full signal flow graph once, by hand, for a small length. It is the fastest way to see why the cost is what it is, because the structure of the saving becomes visible rather than asserted.

Bit-reversed order is not an extra step somebody bolted on. It falls out of the repeated even-odd splitting. After enough splits, the sample in a given position is the one whose index has its bits reversed. Knowing that it is a consequence rather than a convention is what makes it memorable.

In-place computation is the last piece of economy. Because each butterfly consumes exactly the two values it overwrites, the whole transform runs in the array it started in, with no second array. For a large transform on a small device, that is not a nicety.

What you should now be able to explain or do

Say what the fast transform is and is not. State the cost saving and what it meant practically. Explain the divide-and-conquer structure and connect it to sorting. Distinguish decimation in time from decimation in frequency, and say why you only need one thoroughly. Draw a butterfly and a small flow graph. Explain why bit-reversed order arises rather than being imposed. Say what in-place computation saves.

Check yourself