ON IMPLEMENTING THE ARITHMETIC FOURIER-TRANSFORM

In a recent paper, Tufts and Sadasiv discuss the arithmetic Fourier transform (AFT), a method for computing the Fourier coefficients of a complex-valued periodic function. The method is based on a formula which has the advantage of eliminating many of the multiplications usually associated with computing discrete Fourier coefficients, but has the disadvantage of requiring samples of the signal at nonuniformly spaced time values. In this article we develop a method for computing the Fourier coefficients which allows uniform sampling at arbitrarily chosen sampling rates. The technique still affords a paucity of multiplications, albeit at the expense of a limited amount of linear interpolation of the sample values. Efficient hardware implementations of this algorithm are presented.