VECTOR COMPUTATION OF THE DISCRETE FOURIER-TRANSFORM

Since the invention of fast algorithms for the computation of the disc rete Fourier transform (DFT) by Cooley and Tukey in 1965, the DFT has been widely used for the frequency-domain analysis and design of signa ls and systems in communications, digital signal processing, and in ma ny other areas of science and engineering. While the Cooley-Tukey algo rithms are simple, regular, and efficient, they have the drawback of r equiring a significant amount of overhead operations such as bit-rever sal, data-swapping, etc. In this paper, we develop a generalized versi on of a new family of DFT algorithms by decomposing a form of the DFT relation in which the input data and transform quantities are represen ted as vectors. These algorithms have the features that eliminate or r educe the drawbacks of the Cooley-Tukey algorithms while improving the simplicity and regularity of their implementations. The generalized v ersion makes it easier to deduce a large family of algorithms with dif ferent features. The relative merits of the various algorithms with di fferent vector lengths are discussed and the optimum vector length for DFT computation is pointed out.