In-place butterfly-style FFT of 2-D real sequences

Abstract

Methodologies for constructing fast algorithms to compute the discrete Fourier transform (DFT) of a 2-D real sequence are introduced. The resulting algorithms are shown to be in-place and butterfly-style as well as the usual 1-D FFT algorithms. Above all, the computational load of these algorithms is reduced to less than one-half of their complex counterparts. Due to the in-place property, the storage requirement is exactly halved. A comparison is made on the basis of arithmetic complexity, storage, and input/output requirements.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>