A linear filtering approach to the computation of discrete Fourier transform

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 N ₂ N for any N, N 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 N^3/2.