A limited range discrete Fourier transform algorithm
James W. Cooley, Shmuel Winograd · 2005
Some recent work (1) has shown how one can compute limited portions of the discrete Fourier transform (DFT) of a long sequence by first passing it through a decimating FIR filter and then using the FFT algorithm on the result. The filter is designed by an easily available program (2) to put a pass-band at the desired frequencies and stop-bands at all frequencies which will be aliased into the pass-band by the decimation. It is shown here how one may relax the constraints put upon the pass-band of the filter and significantly shorten the filter impulse response with a corresponding reduction in the amount of computation. A second innovation is to show how a set of cascaded decimating filters may be designed which requires less arithmetic and storage than a single large decimating filter. This reduction is achieved by designing each cascaded filter so as to take into account the attenuation of the preceding filters.