An Improved FFT (Fast Fourier Transform) for a Four Parallel Pipe SIMD Arithmetic Processor.

Abstract

An algorithm is derived that reduces the execution time of a fast Fourier transform (FFT) by a factor of 4 utilizing a loosely coupled four parallel pipe processor that a single instruction, multiple data (SIMD) stream architecture. This algorithm distributes the FFT computations among the four parallel pipes for the radix-4 and the mixed radix-2/-4 cases. The algorithm is demonstrated specifically for both a 16- and 32-point FFT. In addition, the radix-4 FFT algorithm is derived in detail, along with formulas for the execution times and a method that computes the inverse FFT. The necessity for prescrambling the input data is explained and a simple hardware implementation is given. Keywords include: Discrete Fourier Transforms; Fast Fourier Transforms; Parallel Processors; Signal Processor Architectures. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 01, 1985
Accession Number
ADA156625

Entities

People

  • T. C. Choinski
  • T. T. Tylaska

Organizations

  • Naval Underwater Systems Center

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Arithmetic
  • Classification
  • Coefficients
  • Computations
  • Data Processing
  • Data Sets
  • Discrete Fourier Transforms
  • Equations
  • Fast Fourier Transforms
  • Frequency
  • Parallel Computing
  • Parallel Processing
  • Parallel Processors
  • Security
  • Sequences
  • Signal Processing

Fields of Study

  • Engineering

Readers

  • Approximation Theory.
  • Computer Engineering