Understanding the Fft: A Tutorial on the Algorithm & Software for Laymen, Students, Technicians & Working Engineers
Citrus Press is proud to announce the second edition (revised) of Andy Zonst's Understanding the FFT (publication date April 2000). This edition is much more than just a "cleanup" of the original text - two completely new chapters have been added. The first of these deals with the conventional FFT (i.e., scrambled data and bit reversal) and the second is an introduction to the mathematical procedure known as convolution. The conventional FFT offers certain advantages (primarily more efficient use of RAM, allowing larger arrays to be processed); but, beyond that, if one wants to work in this field, they need to be conversant with this "standard" technology (even if they never use it).
The chapter on convolution is perhaps even more important. This technique is such an integral part of Fourier analysis that a chapter (presenting it at the same level as the other material in the book) seemed very nearly imperative. There can be no doubt that it is a better book because of these revisions, and the claim still holds that, for anyone who wants to understand and use this tool known as the FFT, this book is the best place to start.
Why Read This Book
You should read this book if you want a compact, implementation-oriented explanation of how FFTs actually work in practice — including radices, in-place/bit-reversal layouts, and memory-efficient (conventional) variants. It also gives a clear, applied introduction to convolution via the FFT so you can exploit fast convolution in real systems.
Who Will Benefit
Practicing DSP engineers and engineers-in-training who need to implement, optimize, or apply FFTs and FFT-based convolution in signal-processing systems.
Level: Intermediate — Prerequisites: Basic signals-and-systems concepts, familiarity with the Discrete Fourier Transform (DFT), complex arithmetic, and some programming experience (C or pseudocode will help).
Key Takeaways
- Implement the radix-2 FFT (decimation-in-time and decimation-in-frequency) including in-place algorithms.
- Explain and perform bit-reversal and scrambled-data arrangements used by conventional FFTs.
- Use the FFT to compute fast convolution and understand overlap-add/overlap-save approaches.
- Analyze computational complexity, memory usage, and trade-offs for different FFT implementations.
- Apply FFTs to practical tasks such as spectral analysis, filtering, and real-input optimizations.
Topics Covered
- Introduction and motivation: DFT versus FFT
- The discrete Fourier transform: definitions and properties
- Derivation of the radix-2 FFT
- Decimation-in-time and decimation-in-frequency algorithms
- Conventional FFT: scrambled data, bit-reversal and in-place organization
- Implementation details: memory, scaling, and numerical considerations
- Convolution and the FFT: circular vs. linear convolution
- Fast convolution techniques: overlap-add and overlap-save
- Real-input and real-output FFT optimizations
- Applications: spectral analysis, filtering, and practical examples
- Appendices: worked examples and pseudocode/code snippets
Languages, Platforms & Tools
How It Compares
More compact and implementation-focused than Brigham's The Fast Fourier Transform and Its Applications, and far more FFT-specific than Lyons' Understanding Digital Signal Processing which covers many DSP topics beyond the FFT.
