Multidimensional systolic arrays for the implementation of discrete Fourier transforms

Hyesook Lim, Earl E. Swartzlander

Research output: Contribution to journalArticlepeer-review

30 Scopus citations


This paper presents an efficient technique for using a multidimensional systolic array to perform the multidimensional discrete Fourier transform (DFT). Extensions of the multidimensional systolic array suitable for fast Fourier transform (FFT) computations such as the prime-factor computation or the 2n-point decomposed computation of the one-dimensional (1-D) discrete Fourier transform are also presented. The essence of our technique is to combine two distinct types of semisystolic arrays into one truly systolic array. The resulting systolic array accepts streams of input data (i.e., it does not require any preloading), and it produces output data streams at the boundary of the array. No networks for intermediate spectrum transposition between constituent transforms are required. The systolic array has regular processing elements that contain a complex multiplier accumulator and a few registers and multiplexers. Simple and regular connections are required between the PE's.

Original languageEnglish
Pages (from-to)1359-1370
Number of pages12
JournalIEEE Transactions on Signal Processing
Issue number5
StatePublished - 1999


Dive into the research topics of 'Multidimensional systolic arrays for the implementation of discrete Fourier transforms'. Together they form a unique fingerprint.

Cite this