Importance

Loading Importance Indicators...

Abstract

Since the invention of the radix-2 structure for the computation of the discrete Fourier transform (DFT) by Cooley and Tukey in 1965, the DFT has been widely used for the frequency-domain analysis and design of signals and systems in communications, digital signal processing, and in other areas of science and engineering. While the Cooley-Tukey structure is simpler, regular, and efficient, it has some drawbacks such as more complex multiplications than required by higher-radix structures, and the overhead operations of bit-reversal and data-swapping. The present invention provides a large family of radix-2 structures for the computation of the DFT of a discrete signal of N samples. A member of this set of structures is characterized by two parameters, u and v, where u (u=2.sup.r, r=1,2, . . . , (log.sub.2 N)-1) specifies the size of each data vector applied at the two input nodes of a butterfly and v represents the number of consecutive stages of the structure whose multiplication operations are merged partially or fully. It is shown that the nature of the problem of computing the DFT is such that the sub-family of the structures with u=2 suits best for achieving its solution. These structures have the features that eliminate or reduce the drawbacks of the Cooley-Tukey structure while retaining its simplicity and regularity. A comprehensive description of the two most useful structures from this sub-family along with their hardware implementations is presented.

Loading the Abstract Image...

First Claim