Source code for the pipelined phase-rotation FFT

David R. O'Hallaron
School of Computer Science
Carnegie Mellon University

The Welchel phase-rotation FFT is a new form of the fast Fourier transform (FFT) that replaces data movement at runtime with equivalent multiplications by precomputed constants. The result is an FFT that is easy to pipeline.

An F77 program that completely specifies the 1D algorithm is available as a compressed Unix tar file. The program is designed to be a tutorial on the systolic version of the phase-rotation FFT, and thus is written directly in terms of the stages in the systolic pipeline, which is described in the following companion paper:

D. O'Hallaron, P. Lieu, L. Withers, and J. Whelchel, Computing the pipelined phase rotation FFT, Scalable High Performance Computing Conference, Knoxville, TN, May, 1994, pp. 462-469. ( abstract, ps, pdf. )

After downloading the tar file, type "uncompress phase1.tar.Z" to uncompress it, followed by "tar -xvf phase1.tar" to expand it. The resulting directory, phase1, contains the following files:

File Description
README Introduction and list of files
makefile Type "make" to produce the executable "phase1"
phase1.h Some constants
phase1.f Main program
rotators.f Routines that precompute rotators
shuffle.f Routines that shuffle data
matrix.f Various matrix utilities The companion paper

Questions and comments can be directed to Dave O'Hallaron at

[count] accesses since March 1998.