A Natively Real-Valued FFT Algorithm
Rajesh Thomas, Victor DeBrunner, Linda S. DeBrunner · 2021 55th Asilomar Conference on Signals, Systems, and Computers · 2021
Computation of the Discrete Fourier Transform is a long and thoroughly studied topic in digital signal processing. Modern Fast Fourier Transform (FFT) algorithms use divide-and-conquer strategies or more generally algorithms based deeply in polynomial remainder theory, such as the Chinese Remainder Theorem. As far as we know, all of these algorithms are based on natively complex-valued arithmetic. In this paper, we develop a comprehensive algorithm where every calculation is natively real-valued. We use the eigenstructure of the DFT matrix in our approach. We show that our developed algorithm requires the same number of computations as the Cooley-Tukey algorithm for data lengths N = 2n. For other lengths, our proposed method is substantially superior to other FFT methods.