Real-Valued Fast Fourier Transform Algorithms

Henrik V. Sorensen, Douglas L. Jones, Michael T. Heideman, C. Sidney Burrus

Research output: Contribution to journalComment/debate

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.

Original languageEnglish (US)
Pages (from-to)849-863
Number of pages15
JournalIEEE Transactions on Acoustics, Speech, and Signal Processing
Volume35
Issue number6
DOIs
StatePublished - Jun 1987

ASJC Scopus subject areas

  • Signal Processing

Fingerprint Dive into the research topics of 'Real-Valued Fast Fourier Transform Algorithms'. Together they form a unique fingerprint.

  • Cite this