BeginnerTopic 28 of 101Signals, Control & Comms
Fast Fourier transform
An O(N log N) algorithm to compute the DFT.
In depth
FFT algorithms (Cooley-Tukey) reduce DFT cost from O(N²) to O(N log N) by recursive decomposition into smaller DFTs, using symmetry of twiddle factors. Radix-2 requires N a power of two; mixed-radix and Bluestein cover other sizes. Enables real-time spectral analysis and fast convolution.
Key points
- Butterfly operations
- Bit reversal
- Libraries FFTW, KissFFT
ExampleA 1M-point FFT takes milliseconds versus hours for direct DFT.
What is Fast Fourier transform?
An O(N log N) algorithm to compute the DFT.
Why is it important to understand fast Fourier transform?
The FFT makes spectrum analysis fast enough for real-time work, which is why it is among the most used algorithms in engineering.
Why is the FFT so much faster than the direct DFT?
It reuses intermediate results by dividing the transform into smaller ones, which reduces the work from N squared to N log N.
Does the FFT need N to be a power of two?
The classic radix-2 version does, but mixed-radix and other variants handle other lengths, often with padding.
How is Fast Fourier transform used in practice?
Typical applications include analysing an audio stream in real time on a microcontroller, computing the spectrum of a radar echo for detection and processing large image data by two-dimensional transforms.
What should I learn before Fast Fourier transform?
Study "Discrete Fourier transform" first (topic 27 of 101 in Signals, Control & Comms). It covers the groundwork this topic builds on.
What are the key points of Fast Fourier transform?
Butterfly operations. Bit reversal. Libraries FFTW, KissFFT.
Can you give an example of Fast Fourier transform?
A 1M-point FFT takes milliseconds versus hours for direct DFT.
What comes after Fast Fourier transform?
The next topic is "Windowing", which builds directly on this one.
How difficult is Fast Fourier transform?
It is classed as Beginner in Signals, Control & Comms (topic 28 of 101). It is an entry-level topic. It relies only on basic school mathematics and the ideas introduced earlier in this discipline.