Double Factors Algorithm for Computing DFT

摘要：

A fast Fourier transform algorithm for computing N=N1×N2-point DFT, where both factors N1 and N2 are smaller positive integer, said to be a double factors algorithm(DFA), is developed. The DFA subdivides a DFT of length N=N1×N2 into smaller transforms of length N1 and N2 and takes the following steps:(1) computes N1 N2-point DFTs , (2) multiplies the values of DFT by twiddle factors, (3) computes N2 N1-point DFTs. The structure of the DFA is similar to those of the most simple PFA and WFTA, but N1 and N2 are not necessarily relatively prime. When N=2M or 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.

关键词： double factors algorithm prime factor algorithm radiz-4 FFT spliz-radiz FFT smaller-length DFT

作者: Haijun Li Caojun Yan Wenbiao Peng

作者单位: Electrical and Information College, China Three Gorge University Yichang,Hubei Province, China Electrical and Information College,China Three Gorge University Yichang,Hubei Province, China

会议类型: 国际会议

会议名称: 2009图像分析与信号处理国际会议(2009 International Conference on Image Analysis and Signal Processing)

会议地点: 浙江台州

会议语种:英文

页码: 133-137

在线出版日期: 2009-04-11（万方平台首次上网日期，不代表论文的发表时间）