17 May 1989 Practical Algorithm For Computing The 2-D Arithmetic Fourier Transform
Author Affiliations +
Proceedings Volume 1058, High Speed Computing II; (1989); doi: 10.1117/12.951666
Event: OE/LASE '89, 1989, Los Angeles, CA, United States
Abstract
Recently, Tufts and Sadasiv [10] exposed a method for computing the coefficients of a Fourier series of a periodic function using the Mobius inversion of series. They called this method of analysis the Arithmetic Fourier Transform(AFT). The advantage of the AFT over the FN 1' is that this method of Fourier analysis needs only addition operations except for multiplications by scale factors at one stage of the computation. The disadvantage of the AFT as they expressed it originally is that it could be used effectively only to compute finite Fourier coefficients of a real even function. To remedy this the AFT developed in [10] is extended in [11] to compute the Fourier coefficients of both the even and odd components of a periodic function. In this paper, the improved AFT [11] is extended to a two-dimensional(2-D) Arithmetic Fourier Transform for calculating the Fourier Transform of two-dimensional discrete signals. This new algorithm is based on both the number-theoretic method of Mobius inversion of double series and the complex conjugate property of Fourier coefficients. The advantage of this algorithm over the conventional 2-D FFT is that the corner-turning problem needed in a conventional 2-D Discrete Fourier Transform(DFT) can be avoided. Therefore, this new 2-D algorithm is readily suitable for VLSI implementation as a parallel architecture. Comparing the operations of 2-D AFT of a MxM 2-D data array with the conventional 2-D FFT, the number of multiplications is significantly reduced from (2log2M)M2 to (9/4)M2. Hence, this new algorithm is faster than the FFT algorithm. Finally, two simulation results of this new 2-D AFT algorithm for 2-D artificial and real images are given in this paper.
© (1989) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
I S Reed, Y. Y. Choi, Xiaoli Yu, "Practical Algorithm For Computing The 2-D Arithmetic Fourier Transform", Proc. SPIE 1058, High Speed Computing II, (17 May 1989); doi: 10.1117/12.951666; https://doi.org/10.1117/12.951666
PROCEEDINGS
8 PAGES


SHARE
KEYWORDS
Fourier transforms

Algorithm development

Detection and tracking algorithms

Computer simulations

Very large scale integration

Algorithms

Target detection

Back to Top