Sampling reduction for the arithmetic Fourier transform

Implementation aspects of the recently introduced arithmetic Fourier transform (AFT) are considered. The AFT is derived, and it is shown that the components of the Fourier coefficients are averages of values of the time function sampled at Farey fractions of the periodic interval. A calculation showing the number of samples required under the assumption of a uniform sampling rate is presented. An analysis of an approximation of the AFT that allows computation with fewer samples than required by the exact AFT is presented. The technique uses a simple interpolation procedure to achieve the sampling rate reduction. Examples showing the effectiveness (relatively low errors) of linear interpolation are presented. The hardware implementation of a 60 sample, 12 coefficient, approximate AFT is discussed, and a simulation of an efficient hardware implementation is presented