Notes on Digital Signal Processing: Practical Recipes for Design, Analysis and Implementation

Note 18. FFT: Decimation-in-Frequency Algorithms

Decimation-in-time FFTs are based on repeatedly splitting the DFT summation into two summations—one for the decimated time sequence from which even-indexed samples have been removed and one for the decimated time sequence from which odd-indexed samples have been removed. As the name implies, decimation-in-frequency FFTs split the DFT summation in a way that produces decimated frequency sequences. The DFT summation can be specialized for computing only the even-indexed frequency samples:

18.1

After some algebraic manipulations, Eq. (18.1) can be put in the form

18.2

where a[n] is the sequence ...