Design, Optimization, and Implementation of a Universal FFT Processor

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Sep 01, 2000
Accession Number
ADA460551

Entities

People

  • Jeremy Johnson
  • Pinit Kumhom
  • Prawat Nagvajara

Organizations

  • Drexel University

Tags

Communities of Interest

  • Advanced Electronics

DTIC Thesaurus Topics

  • Algorithms
  • Arithmetic Units
  • Complex Numbers
  • Computations
  • Computer Science
  • Flow
  • Generators
  • Hypervelocity Flow
  • Lepidoptera
  • Models
  • Numbers
  • Optimization
  • Permutations
  • Sequences
  • Simulations
  • Simulators
  • Two Dimensional

Fields of Study

  • Engineering

Readers

  • Graph Algorithms and Convex Optimization.
  • Image Processing and Computer Vision.
  • Parallel and Distributed Computing.