S5-3.1 The DFT & Fast Fourier Transform
You can compute the DFT and apply its properties, derive radix-2 decimation-in-time and decimation-in-frequency FFT algorithms with in-place computation and bit reversal, and perform linear filtering using the FFT.
The DFT is the only Fourier transform a computer can actually evaluate, and the FFT is what took it from N squared to N log N and so made the whole field practical. Decimation in time and decimation in frequency reach the same saving by splitting the sequence differently; learn one butterfly diagram properly and the other reads as its mirror. Linear filtering via the FFT is the payoff - convolution becomes multiplication - but only if you handle the circular-versus-linear distinction with overlap-add or overlap-save.
Work through these
Introduction to the discrete Fourier transform
The only Fourier transform a computer can actually evaluate, which is why it exists at all. Everything in this subject downstream of here assumes you are comfortable with it.
Properties of the DFT
The properties that let you avoid computing things twice, and the source of the circular convolution trap in the last item of this topic. Worth knowing well rather than looking up.
Efficient computation of the DFT
The setup for the two algorithms below: the direct calculation costs too much, and the redundancy in it is what will be exploited. Seeing the cost before the saving makes the saving mean something.
Radix-2 decimation-in-time FFT algorithm
The algorithm that took this from unusable to routine. Learn one butterfly diagram properly and the mirror version in the next item reads almost for free.
Radix-2 decimation-in-frequency FFT algorithm
The same saving reached by splitting the sequence the other way. Compare the two flow graphs side by side rather than memorising both.
In-place computation and the bit reversal algorithm
The practical details that make the algorithm fit in memory: computing in place, and the reordering that costs. Bit reversal looks like a curiosity until you have to implement it.
Linear filtering using the FFT algorithm
The payoff of the whole topic: convolution becomes multiplication. It only works if you handle the difference between circular and linear correctly, which is what overlap-add and overlap-save are for.
Lab: linear convolution, circular convolution and correlation of sequences in MATLAB
The bench version of the convolution ideas. Doing linear and circular convolution on the same sequences is the fastest way to see why the distinction matters.
Lab: compute the DFT and FFT of a sequence in MATLAB
The bench version of the transform itself. Comparing the direct computation against the fast one on a long sequence turns the cost argument into something you have watched happen.
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.