Efficient systolic arrays for fft algorithms

Hyesook Lim, Earl E. Swartzlander

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

9 Scopus citations


A new approach for the systolic implementation of FFT algorithms is presented. The proposed approach is based on the fundamental principle that a 1-dimensional DFT can be decomposed to a 2-dimensional DFT (with or without twiddle factors) and the 2-dimensional DFT can be computed efficiently on a 2-dimensional systolic array. The essence of the proposed systolic array is to combine different types of semi-systolic arrays into one array so that the resulting array becomes truly systolic. The proposed systolic array does not require any preloading of input data and it produces output data at boundary PEs. No networks for intermediate spectrum transposition between constituent 1-dimensional transforms are required; therefore the entire processing is fully pipelined. This approach also has significant advantages over existing architectures in reduced throughput and latency for large transforms.

Original languageEnglish
Title of host publicationConference Record of the 29th Asilomar Conference on Signals, Systems and Computers, ACSSC 1995
EditorsAvtar Singh
PublisherIEEE Computer Society
Number of pages5
ISBN (Electronic)0818673702
StatePublished - 1995
Event29th Asilomar Conference on Signals, Systems and Computers, ACSSC 1995 - Pacific Grove, United States
Duration: 30 Oct 19951 Nov 1995

Publication series

NameConference Record - Asilomar Conference on Signals, Systems and Computers
ISSN (Print)1058-6393


Conference29th Asilomar Conference on Signals, Systems and Computers, ACSSC 1995
Country/TerritoryUnited States
CityPacific Grove

Bibliographical note

Publisher Copyright:
© 1995 IEEE.


Dive into the research topics of 'Efficient systolic arrays for fft algorithms'. Together they form a unique fingerprint.

Cite this