A Formal Derivation of Array Implementations of FFT (Fast Fourier Transform) Algorithms,

Abstract

Fast Fourier Transform algorithms are interesting for direct hardware implementation in VLSI. The description of FFT algorithms is typically made either in terms of graphs illustrating the dependency between different data elements or in terms of mathematical expressions without any notion of how the computations are implemented in space or time. Expressions in the notation used in this paper can be given an interpretation in the implementation domain. The notation is in this paper used to derive a description of array implementations of decimation-in-frequency and decimation-in-time FFT algorithms. Correctness of the implementations in guaranteed by way of derivation. (Author)

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1983
Accession Number
ADP002606

Entities

People

  • David J. Cohen
  • L. Johnsson

Organizations

  • California Institute of Technology

Tags

DTIC Thesaurus Topics

  • Algorithms
  • California
  • Computations
  • Fast Fourier Transforms
  • Frequency
  • Large Scale Integration
  • Mathematical Analysis
  • Mathematics
  • Notation
  • Signal Processing
  • Universities
  • Very Large Scale Integration
  • Workshops

Fields of Study

  • Engineering

Readers

  • Approximation Theory.
  • Computer Programming and Software Development.
  • Distributed Systems and Data Platform Development

Technology Areas

  • Space