A Caltech Library Service

A Formal Derivation of Array Implementations of FFT Algorithms

Johnsson, Lennart and Cohen, Danny (1982) A Formal Derivation of Array Implementations of FFT Algorithms. California Institute of Technology , Pasadena, CA. (Unpublished)

See Usage Policy.


Use this Persistent URL to link to this item:


Fast Fourier Transform, FFT, 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 is guaranteed by way of derivation.

Item Type:Report or Paper (Technical Report)
Additional Information:© California Institute of Technology. Presented at USC Workshop on VLSI and Modern Signal Processing (sponsored by ON R) November 1982 The research described in this paper was sponsored by the Defense Advanced Research Projects Agency, ARPA Order number 3771, and monitored by the Office of Naval Research under contract number N00014-79-C-0597. This work was sponsored by the Defense Advanced Project Agency (DARPA) under Contract No. MDA903-81-C-0335 with USC/Information Sciences Institute and Contract N00014-79-C-0597 with the California Institute of Technology. Views and conclusions contained in this paper are the author's and should not be interpreted as representing the official opinion or policy of DARPA, the U.S. Government, or any person or agency connected with them.
Group:Computer Science Technical Reports
Funding AgencyGrant Number
Defense Advanced Research Projects Agency (DARPA)ARPA order 3771
Office of Naval ResearchN00014-79-C-0597
Other Numbering System:
Other Numbering System NameOther Numbering System ID
Computer Science Technical Memorandum5043
Record Number:CaltechAUTHORS:20120420-155106097
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:30248
Deposited On:23 Apr 2012 21:16
Last Modified:03 Oct 2019 03:48

Repository Staff Only: item control page