Fast computation of Fourier transforms at arbitrary frequencies

Abstract

An algorithm is proposed for computing the Fourier Transform (FT) of a uniformly sampled signal at arbitrary frequencies. In most of the applications, the algorithm retains the computational efficiency of the Fast Fourier Transform (FFT) algorithm. The method is based on the fact that the FT at an arbitrary frequency can be expressed as a weighted sum of its Discrete Fourier Transform (DFT) coefficients. In the proposed method, these weights are suitably approximated so that the desired FT is very nearly the sum of (i) a few dominant terms of the sum of the DFT which are computed directly, and (ii) the DFT of a new sequence obtained by multiplying the original sequence with a sawtooth function. The number of directly computed terms is so chosen that the error of approximation does not exceed the specified limits. The computational aspects of the algorithm and its error behavior with typical signals have been critically examined.