提高运算速度的素因子分解FFT算法

 对一种用素因子分解计算离散傅里叶变换的算法进行了研究。其特点是能用简单的下标映射并以同址方式实现快速离散傅里叶变换运算。运算结果表明该算法可比常规的Ｃｏｏｌｅｙ－Ｔｕｋｅｙ基２算法快３２％。

A PRIME FACTOR FFT ALGORITHMFOR IMPROVING COMPUTING SPEED

An algorithm of computing discrete Fourier transfonn(DFT)using prime factor de-composition is studied, The algorithm proposed reduces time of computing DFT by about 32% as compared with traditional radix 2 Cooley-Tukey algorithm。The reason of improving speed of computing DFT due to the algorithm resuIts from mapping one dimensional large seale DFT into muLtidimensional small scale DFTs by means of very simple index mapping scheme as well as sm a l l scale W i n ograd cyclic convolu tion algorithms. Because of Burrus’s smart choiee of reconstuction coefficients in Chinese Remainder Theorem index mapping schemes come to be very simple and prime factor FFT algorithm can be computed in place in order.Depending upon small scale Winograd cyclic convolution algorithms which minimize the number of muLtiplica-tions the prime factor algorithm can reduce the number of muLtiplications of large scale DFT signiflcantly as compared with radix2 Cooley-Tukey FFT algorithm。