Donald Bren School of Information and Computer Sciences

Fourier transform techniques are very popular and practical for DSP applications. Among them, Discrete Fourier Transform (DFT) and its fast algorithm (FFT) are best known and most important. In this report, we define two general communication models and a corresponding handshaking protocol for the FFT chip. We explore multiple design alternatives using efficient pipelining techniques, and show what algorithm transformations are needed. From this example we derive a methodology for applying the pipelining techniques in a time-constrained formulation. Parameterization for a more general ITT chip is also discussed.