Implementation of "Split-radix" FFT algorithms for complex, real, and real-symmetric data

A new algorithm is presented for the fast computation of the discrete Fourier transform. This algorithm belongs to that class of recently proposed 2 n -FFT's which present the same arithmetic complexity (the lowest among any previously published one). Moreover, this algorithm has the advantage of being performed "in-place," by repetitive use of a "butterfly"-type structure, without any data reordering inside the algorithm. Furthermore, it can easily be applied to real and real-symmetric data with reduced arithmetic complexity by removing all redundancy in the algorithm.