Fast computation of real discrete Fourier transform for any number of data points

摘要

In many applications, it is desirable to have a fast algorithm (RFFT) for the computation of the real discrete Fourier transform (RDFT) for any number of data points N. To achieve this, the two-factor Cooley-Tukey decimation-in-time and decimation-in-frequency RFFT algorithms are first developed and expressed in terms of matrix factorization using Kronecker products. This is generalized to any number of factors with arbitrary radices. Each factor M involves the computation of the size-M RDFT, which is carried out by the best size-M RFFT algorithm available. The RFFT algorithm for the case where M is a prime number is also developed. The RFFT algorithms are more efficient in the number of operations when the factors are arranged in a certain order, unlike the Cooley-Tukey complex FFT algorithms. which have the same number of operations for any order of the factors.