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 situations are mostly real. The more efficient algorithms for real data are those that are derived from the algorithms for complex data. So far, all such algorithms use a real array to store the data. However, as the data values are real and their transform values are mostly complex, two possible data structures can be used for these algorithms: real or complex. DFT algorithms for real data that use a complex array for storing both the real data and their transform values are derived from the Cooley-Tukey radix-2 algorithm for complex data. This approach reduces the number of bit-reversal and array-index updating operations, eliminates independent data-swapping operations, and yields a computational structure that is almost as regular as that of the algorithms for complex data. Detailed derivations of the proposed algorithms for the computation of both the DFT of real data and the inverse DFT of the transform of real data, as well as their computational complexities, 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 included to show that the proposed algorithms are faster and simpler than the real-valued split-radix and other algorithms.