Tools are presented for the extension of the Cooley-Tukey (1965) and Pease (1968) fast Fourier transform algorithms to arbitrary dimensions in a compact Kroenecker product formulation. Several variations of the vector radix algorithm (VRA) are presented using this formulation, and an algorithm suitable for spatial concurrency is derived. The tools presented are the multidimensional stride and partitioning permutations together with the multidimensional lower-ordered transforms. The concepts of partitioning permutation and multidimensional perfect shuffle permutations are studied. The first enables one to apply a divide-and-conquer strategy used in Cooley-Tukey algorithms to multidimensions and the second defines algorithm data flow in a lattice.>

The authors propose and discuss hybrid VLSI architectures for implementing the Wigner distribution in any dimension. Two contributions are made to the analysis of pipelined architectures for digital signal processing. The first is in introducing the notion of asymptotic area efficiency which in addition to AT/sup 2/ is used as another focal point in the analyses. The second is in presenting a basic design methodology for pipelining arrays under construction of I/O bandwidth by matching their data rate ratios. Well-matched arrays yield good area-time performance with high efficiency. The pipeline methodology forms the basis for new architectures by a systematic construction from arrays that compute subproblems. The authors systematically search for an optimal structure for computing the Wigner distribution in any dimension from arrays that compute subproblems and (static) permutation networks. The pipelining technique yields several structures of which the optimal designs in the sense of AT/sup 2/ and area efficiency are extracted.>

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(n2log2n). 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 AT2pof O(n2log2n· log2N). 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 AT2plower bound for the multidimensional FT processing.