Accession Number : ADP002606

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

Corporate Author : CALIFORNIA INST OF TECH PASADENA DEPT OF COMPUTER SCIENCE

Personal Author(s) : Johnsson,L. ; Cohen,D.

Report Date : 1983

Pagination or Media Count : 11

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)

Descriptors :   *Fast fourier transforms, *Algorithms, *Data management, Binary notation, Discrete fourier transforms, Arrays, Computer operators, Computations

Distribution Statement : APPROVED FOR PUBLIC RELEASE