Efficient computation of the large DFT and DCT coefficients

An algorithm for computing the large discrete Fourier transform (DFT) coefficients of a correlated data sequence is introduced. A novel formulation of the decimation-in-frequency (DIF) fast Fourier transform (FFT) algorithm is introduced which generalizes the decimation method FFT algorithm. The radix-2 DIF FFT algorithm is modified to introduce an efficient algorithm for computing the DFT coefficients larger than a given threshold. This algorithm significantly reduces the computations associated with the small coefficients. Results are extended to all the DIF-based FFT algorithms as well as the multidimensional FFT and the FFT-based fast discrete cosine transform algorithm.<>