Accession Number:

ADA460551

Title:

Design, Optimization, and Implementation of a Universal FFT Processor

Descriptive Note:

Technical rept.

Corporate Author:

DREXEL UNIV PHILADELPHIA PA DEPT OF COMPUTER SCIENCE

Report Date:

2000-09-01

Pagination or Media Count:

7.0

Abstract:

There exist Fast Fourier Transform FFT algorithms, called dimensionless FFTs, that work independent of dimension. These algorithms can be configured to compute different dimensional Discrete Fourier Transforms DFTs simply by relabeling the input data and by changing the values of the twiddle factors occurring in the butterfly operations. This observation allows one to design an FFT processor, which with minor reconfiguring can compute one, two, and three dimensional DFTs. In this paper, the authors design a family of FFT processors, parameterized by the number of points, the dimension, the number of processors, and the internal data flow, and show how to map different dimensionless FFTs onto this hardware design. Different dimensionless FFTs have different data flows and consequently lead to different performance characteristics. Using a performance model, the authors search for the optimal algorithm for the family of processors they considered. The resulting algorithm and corresponding hardware design was implemented using FPGA.

Subject Categories:

  • Numerical Mathematics
  • Computer Hardware
  • Computer Systems

Distribution Statement:

APPROVED FOR PUBLIC RELEASE