A new efficient algorithm to compute the two-dimensional discrete Fourier transform

Abstract

An algorithm is presented for computation of the two-dimensional discrete Fourier transform (DFT). The algorithm is based on geometric properties of the integers and exhibits symmetry and simplicity of realization. Only one-dimensional transformation of the input data is required. The transformations are independent; hence, parallel processing is feasible. It is shown that the number of distinct N-point DFTs needed to calculate N*N-point two-dimensional DFTs is equal to the number of linear congruences spanning the N*N grid. Examples for N=3, N=4, and N=10 are presented. A short APL code illustrating the algorithm is given.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>