Multidimensional systolic arrays for the implementation of discrete Fourier transforms

Hyesook Lim, Earl E. Swartzlander

Research output: Contribution to journalArticlepeer-review

28 Scopus citations

Abstract

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
Volume47
Issue number5
DOIs
StatePublished - 1999

Fingerprint

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

Cite this