A new efficient algorithm for computing a few DFT points
- 6 January 2003
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1915-1918
- https://doi.org/10.1109/iscas.1988.15312
Abstract
The authors describe an efficient method for computing the discrete Fourier transform (DFT) when only a few output points are needed. The method is shown to be more efficient than either Goertzel's method or pruning, and it allows any band in the output to be computed. It is based on a novel factorization of the DFT, where one part is computed using standard power-of-two FFTs (fast Fourier transforms) and the other uses a technique similar to the Goertzel algorithm.<>Keywords
This publication has 8 references indexed in Scilit:
- Real-valued fast Fourier transform algorithmsIEEE Transactions on Acoustics, Speech, and Signal Processing, 1987
- A rearranged DFT algorithm requiring N2/6 multiplicationsIEEE Transactions on Acoustics, Speech, and Signal Processing, 1986
- Pruning the decimation-in-time FFT algorithm with frequency shiftIEEE Transactions on Acoustics, Speech, and Signal Processing, 1986
- On computing the split-radix FFTIEEE Transactions on Acoustics, Speech, and Signal Processing, 1986
- High-resolution narrow-band spectra by FFT pruningIEEE Transactions on Acoustics, Speech, and Signal Processing, 1980
- Pruning the decimation in-time FFT algorithmIEEE Transactions on Acoustics, Speech, and Signal Processing, 1976
- FFT pruningIEEE Transactions on Audio and Electroacoustics, 1971
- An algorithm for the machine calculation of complex Fourier seriesMathematics of Computation, 1965