VLSI Architectures for Multidimensional Fourier Transform Processing

Abstract

It is often desirable in modern signal processing applications to perform two-dimensional or three-dimensional Fourier transforms. Until the advent of VLSI it was not possible to think about one chip implementation of such processes. In this paper several methods for implementing the multidimensional Fourier transform together with the VLSI computational model are reviewed and discussed. We show that the lower bound for the computation of the multidimensional transform is O(n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> log <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> n). Existing nonoptimal architectures suitable for implementing the 2-D transform, the RAM array transposer, mesh connected systolic array, and the linear systolic matrix vector multiplier are discussed for area time tradeoff. For achieving a higher degree of concurrency we suggest the use of rotators for permutation of data. With ``hybrid designs'' comprised of a rotator and one-dimensional arrays which compute the one-dimensional Fourier transform we propose two methods for implementation of multidimensional Fourier transform. One design uses the perfect shuffle for rotations and achieves an AT <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">p</inf> of O(n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> log <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> n· log <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> N). An optimal architecture for calculation of multidimensional Fourier transform is proposed in this paper. It is based on arrays of processors computing one-dimensional Fourier transforms and a rotation network or rotation array. This architecture realizes the AT <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">p</inf> lower bound for the multidimensional FT processing.