树形分解FFT算法
TREE DECOMPOSITION FFT ALGORITHM
-
摘要: 本文对K.Nakayama提出的时间-频率混合抽选FFT算法作了简化和深化,提出了树形分解FFT算法,其实数乘法次数与K.Nakayama的方法相比,由(3/2)Nlog2N7N+10N1/24减少到约为(65/64)Nlog2N3N4。该算法并未改变FFT算法的基本结构,用软件和硬件实现不致有太大的变化。
-
关键词:
Abstract: The Mixed Time and Frequency Decimation FFT Algorithm (MDFFT) proposed by K. Nakayama is simplified and deepened, then a new FFT algorithm based on tree-decomposition process is developed. The number of real multiplications of the newalgorithm is about (65/64)Nlog2N-3N-4 which is less than (3/2)Nlog2N-7N+10N1/2-4 of MDFFT. -
J. Cooley and J. Tukey, Mathematics of Computation, 19(1965), 297.[2]K. Nakayama, Fast Fourier Transform Using Mixed Frequency and Time Decimation, IECE of Japan, Report of Technical Group on Circuit Syst.,Vol. CAS 79-94, pp.49-54, Oct.1979.[3]C . Caraiscos and B. Liu, Two Dimensional DFT Using Mixed Time and Frequency Decimation,Proc. Int. Conf. Acoust., Speech, Signal Processing, pp. 24-27, Paris, May 1982.[4]E. O. Brigham, The Fast Fourier Transform, Prentice-Hall, 1974.
计量
- 文章访问数: 1896
- HTML全文浏览量: 194
- PDF下载量: 447
- 被引次数: 0