Double factors algorithm for computing DFT
Haijun Li, Caojun Yan, Wenbiao Peng · 2009
A fast Fourier transform algorithm for computing N=N1timesN2-point DFT, where both factors N1and N2are smaller positive integer, said to be a double factors algorithm(DFA), is developed. The DFA subdivides a DFT of length N=N1timesN2into smaller transforms of length N1and N2and takes the following steps:(1) computes N1N2-point DFTs , (2) multiplies the values of DFT by twiddle factors, (3) computes N2N1-point DFTs. The structure of the DFA is similar to those of the most simple PFA and WFTA, but N1and N2are not necessarily relatively prime. When N=2Mor 4M, the total number of computations of DFT in the DFA is less than those in the radix-2 and radix-4 FFT algorithm but slightly more than that in the split-radix FFT algorithm. When N is other values, the total number of computations of DFT in the DFA is less than those in the PFA and WFTA.