Title :
A limited range discrete Fourier transform algorithm
Author :
Cooley, J.W. ; Winograd, S.
Author_Institution :
I.B.M. Watson Research Center, Yorktown Heights, N.Y.
Abstract :
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.
Keywords :
Algorithms; Attenuation; Band pass filters; Chromium; Computer hacking; Convolution; Discrete Fourier transforms; Finite impulse response filter; Frequency; Technological innovation;
Conference_Titel :
Acoustics, Speech, and Signal Processing, IEEE International Conference on ICASSP '80.
DOI :
10.1109/ICASSP.1980.1170899