Computing the pipelined phase-rotation FFT

Author

O´Hallaron, David R. ; Lieu, Peter J. ; Withers, L.P., Jr. ; Whelchel, John E.

Author_Institution

Sch. of Comput. Sci., Carnegie Mellon Univ., Pittsburgh, PA, USA

fYear

1994

fDate

23-25 May 1994

Firstpage

462

Lastpage

469

Abstract

The phase-rotation FFT is a new form of the FFT that replaces data movement with multiplications by constant phasor multipliers. The result is an FFT that is simple to pipeline. The paper completes the pipelined design of the the original phase-rotation FFT, provides a fundamental new description of the algorithm directly in terms of the parallel pipeline, and describes a radix-2 implementation on the iWarp computer system that balances computation and communication to run at the full-bandwidth of the communications links, regardless of the input data set size

Keywords

fast Fourier transforms; parallel machines; parallel programming; pipeline processing; communications links; constant phasor multipliers; data movement; iWarp computer system; input data set size; parallel pipeline; pipelined design; pipelined phase-rotation FFT; radix-2 implementation; Algorithm design and analysis; Application software; Computer science; Concurrent computing; Discrete Fourier transforms; Flexible printed circuits; Kernel; Pipelines; Signal design; Signal processing algorithms;

fLanguage

English

Publisher

ieee

Conference_Titel

Scalable High-Performance Computing Conference, 1994., Proceedings of the

Conference_Location

Knoxville, TN

Print_ISBN

0-8186-5680-8

Type

conf

DOI

10.1109/SHPCC.1994.296679

Filename

296679