ITERATIVE REALIZATION OF THE ARITHMETIC FOURIER-TRANSFORM

A Fourier analysis method using an iterative arithmetic Fourier transform (AFT) is presented. It overcomes the difficulty of dense, Farey-fraction sampling inherent in the original AFT algorithm presented by Tufts and Sadasiv. This disadvantage of the AFT is turned into an advantage and dense frequency-domain samples are obtained without any additional interpolation or zero padding. The implementation of the iterative computations is designed to preserve the advantage of the AFT for VLSI implementation by using a permuted difference coefficient structure. This iterative AFT is intended for cases in which 1) the function to be analyzed can only be sampled uniformly and at a rate close to the Nyquist rate; or 2) the dense frequency-domain samples are needed.