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 dft.

- Title: Digital Signal Processing A Practical Approach
- Implementation of Fast Fourier transforms on Motorola's Digital Signal Processors App. Note