Real-valued decimation-in-time and decimation-in-frequency algorithms

The decimation-in-time (DIT) and the decimation-in-frequency (DIF) algorithms are the typical forms of the fast Fourier transform (FFT) algorithm. Many hardware and software implementations are based on these algorithms. One class of fast algorithms for computing the discrete Fourier transform (DFT) is based on a recursive factorization of the polynomial 1-z^N. This paper introduces a simple recursive factorization of 1-z^N over the real numbers and a mathematical framework that generalizes the form of the DFT. Using the recursive factorization, efficient algorithms are derived to compute the DFT and the cyclic convolution of sequences of length with a power of two. Real-valued DIT and real-valued DIF algorithms are developed so that the accumulated FFT technologies can be fully utilized for real sequences. Introducing a real-valued butterfly, the algorithmic structures of the DIT and the DIF algorithms are shown to be equally applicable for the real-valued algorithms by systematic modifications. The computational complexity is fairly comparable with other available fast algorithms