樹形分解FFT算法
TREE DECOMPOSITION FFT ALGORITHM
-
摘要: 本文對(duì)K.Nakayama提出的時(shí)間-頻率混合抽選FFT算法作了簡(jiǎn)化和深化,提出了樹形分解FFT算法,其實(shí)數(shù)乘法次數(shù)與K.Nakayama的方法相比,由(3/2)Nlog2N7N+10N1/24減少到約為(65/64)Nlog2N3N4。該算法并未改變FFT算法的基本結(jié)構(gòu),用軟件和硬件實(shí)現(xiàn)不致有太大的變化。
-
關(guān)鍵詞:
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. -
計(jì)量
- 文章訪問數(shù): 1907
- HTML全文瀏覽量: 198
- PDF下載量: 447
- 被引次數(shù): 0