Note 17. FFT: Decimation-in-Time Algorithms

Consider the discrete Fourier transform for an N-point sequence

17.1

image

where

image

For even N, the DFT summation can be split into two separate summations—one for the even-indexed samples of x[n] and one for the odd-indexed samples.

17.2

image

Each of the summations in the final line of Eq. (17.2) is in the form of an (N/2)-point DFT. The signal flow graph (SFG) corresponding to the final line of Eq. (17.2) is shown ...

Get Notes on Digital Signal Processing: Practical Recipes for Design, Analysis and Implementation now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.