A linear filtering approach to the computation of discrete Fourier transform

Abstract
It is shown in this paper that the discrete equivalent of a chirp filter is needed to implement the computation of the discrete Fourier transform (DFT) as a linear filtering process. We show further that the chirp filter should not be realized as a transversal filter in a wide range of cases; use instead of the conventional FFT permits the computation of the DFT in a time proportional toN \log_{2} Nfor anyN, Nbeing the number of points in the array that is transformed. Another proposed implementation of the chirp filter requires N to be a perfect square. The number of operations required for this algorithm is proportional toN^{3/2}.

This publication has 5 references indexed in Scilit: