DFT/FFT and Convolution Algorithms and Implementation
This readable handbook provides complete coverage of both the theory and implementation of modern signal processing algorithms for computing the Discrete Fourier transform. Reviews continuous and discrete-time transform analysis of signals and properties of DFT, several ways to compute the DFT at a few frequencies, and the three main approaches to an FFT. Practical, tested FORTRAN and assembly language programs are included with enough theory to adapt them to particular applications. Compares and evaluates various algorithms.
Why Read This Book
You should read this book if you want a compact, implementation-focused bridge between DFT/FFT theory and working code — you will learn not only the mathematical properties of discrete transforms but also practical, tested FORTRAN and assembly implementations you can adapt to real systems. It’s especially valuable when you need to evaluate trade-offs between algorithms, numerical issues, and efficient convolution techniques for audio, radar, or communications applications.
Who Will Benefit
Engineers and researchers with prior DSP coursework who need hands-on, implementation-ready guidance for DFT/FFT algorithms and convolution in real applications such as audio/speech, radar, or communications.
Level: Advanced — Prerequisites: Undergraduate-level signals and systems (discrete-time transforms), complex arithmetic, basic linear algebra, and familiarity with procedural programming (FORTRAN or equivalent); knowledge of numerical roundoff and fixed-point concepts is helpful.
Key Takeaways
- Implement multiple DFT/FFT algorithms (including radix and mixed-radix approaches) from tested code examples.
- Optimize and apply convolution techniques using FFT-based methods for efficient filtering and correlation.
- Analyze numerical stability, roundoff error, and computational trade-offs for different FFT/convolution approaches.
- Adapt and port FORTRAN and assembly implementations to target hardware and constrained environments.
- Compare and select the most appropriate FFT/convolution algorithm for audio, speech, radar, and communications workloads.
Topics Covered
- Introduction: Goals, notation, and overview of transforms
- Review of continuous and discrete-time Fourier analysis
- Properties of the Discrete Fourier Transform (DFT)
- Direct DFT evaluation and single-frequency algorithms (e.g., Goertzel-type methods)
- Convolution and correlation strategies in time and frequency domains
- The three main FFT approaches: radix-based, mixed-radix, and prime-factor methods
- Algorithmic comparisons: cost, memory, and numerical behavior
- Practical implementation techniques: memory layout, in-place transforms, and real/complex optimizations
- Numerical issues: scaling, roundoff, and fixed-point considerations
- Tested FORTRAN and assembly listings with usage notes
- Applications: spectral analysis, filter implementation, and real-time considerations
- Appendices: tables, performance benchmarks, and references
Languages, Platforms & Tools
How It Compares
Closely complements theory-focused texts like Oppenheim & Schafer's Discrete-Time Signal Processing by providing more implementation detail and tested code; compared with Numerical Recipes, Burrus concentrates specifically on DFT/FFT and convolution rather than general-purpose numerical methods.
