The Decimation in Time FFT employs the breakdown of a N point time sampled sequence sequence into
groups of 2 point dfts. The formula for the two point dft is listed below.
We see that the even and odd grouped sequences can be decomposed into further decompositions listed below.
If N in an integer power of 2, this process can be repeated until a simple, two-point dft is obtained. The
decomposition of the dft can be represented as a butterfly diagram showing how the decomposition exposes the
redundancy within the FFT algorithm. This redundancy is also what makes the algorithm faster than the original
The Decimation in Frequency FFT is a decomposition of the sampled points in the frequency domain.
The equation for the DIF FFT is listed below.
- Title: Digital Signal Processing A Practical Approach
- Implementation of Fast Fourier transforms on Motorola's Digital Signal Processors App. Note