Computational Arrays for the Discrete Fourier Transform

Abstract

A mathematical approach towards the development of computational arrays for the Discrete Fourier Transform (DFT) is pursued in this paper. Mathematical expressions for the DFT are given a direct hardware interpretation. Different implementations are developed by formal manipulation of the equations defining the DFT. Properties of the implementations can be told directly from the corresponding equations. Special consideration is given to the performance of implementations and corresponding hardware requirements. The standard equations defining the DFT on N values corresponds if the equations are given a direct hardware interpretation to an Implementation requiring N to the power of 2 modules. By formal manipulation of the equations defining the DFT we develop implementations requiring N and Log subscript2N modules respectively.