Fast Algorithms for the Real Discrete Fourier Transform

Fast algorithms for the computation of the real discrete Fourier transform (RDFT) are discussed. Implementations based on the RDFT are always efficient whereas the implementations based on the DFT are efficient only when signals to be processed are complex. The fast real Fourier (FRFT) algorithms discussed are the radix-2 decimation-in-time (DIT), the radix-2 decimation-in-frequency (DIF), the radix-4 DIT, the split-radix DIT, the split-radix DIF, the prime-factor, the Rader prime, and the Winograd FRFT algorithms