A new efficient algorithm for computing a few DFT points

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.<>