OE-8.3 The Fast Fourier Transform
You can derive and apply radix-2 decimation-in-time and decimation-in-frequency FFT algorithms, and explain bit-reversed ordering and in-place computation.
The FFT is not a different transform - it is the DFT computed cleverly, dropping the cost from N squared to N log N, and that single change is why digital signal processing became practical. Decimation in time and decimation in frequency are two routes to the same saving; learn one thoroughly and the other by comparison. Bit reversal and in-place computation are implementation details that carry the real lesson about memory-efficient algorithms.
Work through these
Introduction to the FFT and the computational saving
The algorithm that made the transform usable, and the size of the saving. Seeing the operation count drop from one order to another is the motivation for everything below.
Radix-2 decimation-in-time FFT (DIT-FFT)
The first of the two ways to split the problem. Learn one butterfly diagram thoroughly and the second version reads almost for free.
Radix-2 decimation-in-frequency FFT (DIF-FFT)
The same saving reached by splitting the other way. Compare the two flow graphs side by side rather than learning both from scratch.
Bit-reversal ordering
Why the outputs come out shuffled, and the reordering that fixes it. It looks like a curiosity until you implement the algorithm.
In-place computation
Computing without a second array, which is what makes the algorithm fit in small memory. It is also why the reordering above is needed at all.
Butterfly diagrams and signal flow graphs
The diagrams that make the whole thing readable. Being able to draw an eight-point flow graph from memory is a reasonable target for this topic.
Sign in to keep your progress.
Free resources
We haven't checked most of these for screen reader use yet.
Links last checked 30 Aug 2026.
Stuck here?
Ask a mentor. A real person answers, and they can see exactly which topic you're on. Usually within a couple of working days.
Checking your session…
Topics shown in module order.