Symmetrical factorization of the fast Fourier transform for efficient implementation

This paper shows a symmetrical decomposition of the Fast Fourier Transform (FFT) into stages such that butterflies of small radices can be applied efficiently. Due to symmetric, the bit reversal sorting is also symmetrical and allows semi in-place self-sorting to be carried out together with the butterfly processing at the middle stage. Furthermore, the mirroring effect due to the symmetry, halves the implementation effort of the remaining stages. No sorting of the data is required before or after the FFT processing, since they are all in-place. The in-place processing negates the need for any temporary storage of the data and hence a more cost and area effective design.