关键词: 因子分解, 离散傅里叶变换, 快速傅立叶变换

Abstract: 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。

Key words: factors-decomposition, discrete-Fourier transformtions. E FT