第六章快速傅里叶变换:引言 1669: Newton偶然发现了光谱但却没有意识到”频率”的概念( corpuscular theory of light, no waves) 1807: Fourier分析诞生 19h/20 th century:出现了两种 Fourier分析方法 Continuous& Discrete CONTINUOUS → Fourier将 Fourier分析推广至任意函数( Fourier Transform) Dirichlet等人研究了 Fourier级数的收敛问题 因不同的需要产生了不同形式的FTe.9. Short Time FT- speech analysis) DISCRETE: Fast calculation methods(FFT) →1965-| BM,s Cooley& Tukey发明了FFT算法(“ An algorithm for the machine calculation of complex Fourier series) 此后相继出现了各种用于计算机平台的改进FFT算法
第六章 快速傅里叶变换: 引言 6
FFT产生故事 当时加文( Garwin)在自已的研究中极需要一个计算付里叶变换的快 速方法。他注意到图基( J W.Turkey)正在写有关付里叶变换的文章,因 此详细询问了图基关于计算付里叶变换的技术知识。图基概括地对加文 介绍了一种方法,它实质上就是后来的著名的库利( Cooley J W图基算 法。在加文的迫切要求下,库利很快设计出一个计算机程序。1965年库 利-图基在<计算数学>、 Mathematic of Computation杂志上发表了著名 的“机器计算付里级数的一种算法”文章,提出一种快速计算DFT的方 法和计算机程序-揭开了FFT发展史上的第一页,促使FFT算法产生原 因还有1967年至1968年间FFT的数字硬件制成,电子数字计算机的条件 使DFT的运算大简化了
FFT产生故事 7 当时加文(Garwin)在自已的研究中极需要一个计算付里叶变换的快 速方法。他注意到图基(J.W.Turkey)正在写有关付里叶变换的文章，因 此详细询问了图基关于计算付里叶变换的技术知识。图基概括地对加文 介绍了一种方法，它实质上就是后来的著名的库利(Cooley J.W)图基算 法。在加文的迫切要求下，库利很快设计出一个计算机程序。1965年库 利--图基在<计算数学>、Mathematic of Computation 杂志上发表了著名 的“机器计算付里级数的一种算法”文章，提出一种快速计算DFT的方 法和计算机程序--揭开了FFT发展史上的第一页，促使FFT算法产生原 因还有1967年至1968年间FFT的数字硬件制成，电子数字计算机的条件 ， 使DFT的运算大简化了
FFT: Fast Fourier transform 1965年, James W. Cooley和 John W. Tukey在《计算数学》(《 Mathematics of Computation》)上发表了“一种用机器计算复序列傅 立叶级数的算法( An algorithm for the machine calculation of complex Fourier series)”论文。 自此之后,新的算法不断涌现。一种是对N等于2的整数次幂的算法 如基2算法,基4算法。另一种是N不等于2的整数次幂的算法,例如 Winagrad算法,素因子算法。 Calculation of B: Jena w Cadley and Joan W Tuley he as train untaa ata) M eagle a th prin=pal John W. Tukey A础计中h切 Dr James W. cooley Worked at IBM Watson Research Center in Yorktown Heights, (1915-2000) N.Y After his retirement from IBM x,1 in 1991, he joined the Electrica 出 Engineering Department at the University of Rhode islan
1965 年，James W. Cooley 和 John W. Tukey 在《计算数学》（《 Mathematics of Computation》）上发表了“ 一种用机器计算复序列傅 立叶级数的算法（An algorithm for the machine calculation of complex Fourier series）” 论文。 自此之后，新的算法不断涌现。一种是对N等于 2 的整数次幂的算法， 如基 2 算法，基 4 算法。另一种是N不等于 2 的整数次幂的算法，例如 Winagrad 算法，素因子算法。 FFT: Fast Fourier Transform Dr. James W. Cooley Worked at IBM Watson Research Center in Yorktown Heights, N.Y..After his retirement from IBM in 1991, he joined the Electrical Engineering Department at the University of Rhode Island. John W. Tukey (1915 – 2000)
●问题提出:设有限长序列x(n),非零值长度为N,计算对 x(m)进行一次DFT运算,共需多大的运算工作量? x(n)->X(k)=>x(n)WN k=0.1.N-1 X(k) IDFT )x(n)= ∑ X(kWN k n=0,1,…N-1 k=0 zTk 其中x(n)为复数,WM=eN也为复数 所以DFT与IDFT二者计算量相同
9 问题提出： 设有限长序列x(n),非零值长度为N,计算对 x(n)进行一次DFT运算，共需多大的运算工作量? 1 0 N n kn N DFT x(n) X (k) x(n)W k 0,1, N 1 1 0 N k kn N IDFT X (k) x(n) X (k)W n 0,1, N 1 其中x(n)为复数， 也为复数 所以DFT与IDFT二者计算量相同。kn N j kn N W e 2
6.0引言:直接计算DFT的运算量分析 k X(k)∑ 复数乘法复数加法 x(ne 每一个X(k) ∑ nk N个X(k) N(N-1) r(n N点DFT) (e+j)+(g+j)=(e+g)+j(f+h) a+ jb(c+ jd)=(ac-bd)+j(ad+cb) 实数乘法 实数加法 复加的加 次复乘 4 复乘的加 2 法次数 法次数 次复加 每一个X(k) AN 2N+2(N-1)=2(2N-1) N个X(k)N点DFT)4N2 2N(2N-1)
6.0 引言：直接计算 DFT 的运算量分析 10 复数乘法 复数加法 每一个X(k) N N – 1 N 个X(k) (N 点 DFT) N 2 N (N – 1) 实数乘法 实数加法 一次复乘 4 2 一次复加 2 每一个 X (k) 4N 2N+2 (N – 1)=2 (2N – 1) N个X (k) (N点DFT) 4N 2 2N (2N – 1) 1 0 1 0 2 X(k)= ( ) ( ) N n N nk N n j nk N x n n e W x a jb c jd ac bd j ad cb 复乘的加 法次数 复加的加 法次数 e jf g jh e g j f h