COMPUTATIONAL STRUCTURES FOR THE FREQUENCY-DOMAIN ANALYSIS OF SIGNALS AND SYSTEMS

摘要

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 th e frequency-domain analysis and design of signals and systems in communications, d igital signal processing, and in other areas of science and engineering. While the Cool ey-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 opera tions 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 m ember of this set of structures is characterized by two parameters, u and v, where u ( u = 2r, r = 1, 2, . . ., (log2 N)-1) specifies the size of each data vector applied at the t wo input nodes of a butterfly and v represents the number of consecutive stages of the structur e whose multiplication operations are merged partially or fully. It is shown that the na ture 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 elimina te or reduce the drawbacks of the Cooley-Tukey structure while retaining its simplicity and r egularity. A comprehensive description of the two most useful structures from this sub-fami ly along with their hardware implementations is presented.