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 to <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">N \log_{2} N</tex> for any <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">N, N</tex> being 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 to <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">N^{3/2}</tex> .