一种新的基数为2的DFT快速算法

A NEW FAST ALGORITHM FOR COMPUTING DISCRETE FOURIER TRANSFORM WITH RADIX-2

本文介绍一种基于γ－循环阵快速分解方法的、新的基数为２的ＤＦＴ快速算法；该算法与具有最小乘法数的Ｐｒｅｕｓｓ算法比较，新算法的乘法数接近Ｐｒｅｕｓｓ算法，但其加法数仅为它的７５％。在Ｓｕｎ－ＳＰＡＲＣＳｔａｔｉｏｎ２工作站上，采用Ｆｏｒｔｒａｎ７７语言编程实现，结果表明：新算法在阶数（Ｎ）小于１０２４时，速度比分裂基（Ｓｐｌｉｔ—Ｒａｄｉｘ）算法快。如果进一步考虑算法中的固定常数乘法，那么新算法将会更加有效。

This paper proposes a new approach to compute the Discrete Fourier Transform(DFT)with the power of 2 length using the efficient method to decompose γ-circular matrix.its multiplications are near to that of the Preuss algorithm,aug its additions are only 75 percent of that by the preuss algorithm.The authors implement this algorithm in Fortran 77 language on Sun-SPARC Station 2,the result shows that the new algorithm is faster than the Split-Radix algorithm when the order number(N)is below 1024.If the fixed constant multiplications are further taken into account,the new algorithm will becomes more efficient.