Generalized FFT algorithm
A. Saidi · 2002
A novel formulation of the decimation method fast Fourier transform (FFT) algorithm is introduced. This formulation generalizes both the decimation-in-time (DIT) and the decimation-in-frequency (DIF) FFT algorithms for various radices in multidimensions. This alternative derivation of the decimation method FFT algorithm has the advantage of clearly showing what is exactly being computed in the intermediate stages of the algorithm. This information is used to present an efficient algorithm for computing the large discrete Fourier transform (DFT) coefficients of a correlated data sequence which reduces the computations associated with the small coefficients.>