FAST COMPUTATION OF THE DISCRETE FOURIER-TRANSFORM OF REAL DATA

Fast algorithms for the computation of the discrete Fourier transform (DFT) of real signals are important since the signals in practical sit uations are mostly real, The more efficient algorithms for real data a re those that are derived from the algorithms for complex data. So far , all such algorithms use real array to store the data, However, as th e data values are real and their transform values are mostly complex, two possible data structures can be used for these algorithms: real or complex, In this paper, DFT algorithms for real data that use a compl ex array for storing both the real data and their transform values are derived from the Cooley-Tukey radix-2 algorithm for complex data, Thi s approach reduces the number of bit-reversal and array-index updating operations, eliminates independent data-swapping operations, and yiel ds a computational structure that is almost as regular as that of the algorithms for complex data, Detailed derivations of the proposed algo rithms for the computation of both the DFT of real data and the invers e DFT of the transform of real data, as well as their computational co mplexities, are presented, A C-language program of one of the proposed algorithms is given, illustrating the use of all the features of the new approach in software implementation, Comparison results are includ ed to show that the proposed algorithms are faster and simpler than th e real-valued split-radix and other algorithms.