Real-valued fast Fourier transform algorithms

TLDR

This tutorial presents methods for building fast algorithms to compute the discrete Fourier transform of real‑valued series, including a new split‑radix FFT implementation that uses fewer operations than other real‑valued power‑of‑2 FFTs. The authors apply these ideas to major FFT algorithms, compare them, and evaluate the performance of real‑valued transforms such as the fast Hartley transform and fast cosine transform against real‑valued FFTs for power‑spectrum and cyclic‑convolution computations. The comparisons show that alternative real‑valued transform techniques require more additions and produce code that is as long or longer and more complex than real‑valued FFT algorithms.

Abstract

This tutorial paper describes the methods for constructing fast algorithms for the computation of the discrete Fourier transform (DFT) of a real-valued series. The application of these ideas to all the major fast Fourier transform (FFT) algorithms is discussed, and the various algorithms are compared. We present a new implementation of the real-valued split-radix FFT, an algorithm that uses fewer operations than any other real-valued power-of-2-length FFT. We also compare the performance of inherently real-valued transform algorithms such as the fast Hartley transform (FHT) and the fast cosine transform (FCT) to real-valued FFT algorithms for the computation of power spectra and cyclic convolutions. Comparisons of these techniques reveal that the alternative techniques always require more additions than a method based on a real-valued FFT algorithm and result in computer code of equal or greater length and complexity.