第四章快速傅立叶变换 Fast Fourier transform
第四章 快速傅立叶变换 Fast Fourier Transform
第一节直接计算DFT的问题及改进途径 1、问题的提出 设有限长序列x(n),非零值长度为N,若 对x(n)进行一次DFT运算,共需多大的运算 工作量? 计算成本? 计算速度?
第一节 直接计算DFT的问题及改进途径 1、问题的提出 设有限长序列x(n)，非零值长度为N，若 对x(n)进行一次DFT运算，共需多大的运算 工作量？ 计算成本? 计算速度?
2.DFT的运算量 回忆DFT和DFT的变换式: X(k)=DFx(m)=∑x(m)WN0≤k≤N 0 x(n)=DFTX(k)=∑X(k)W0≤n≤N-1 =0 注意: k 1)x()为复数,W咻=eN也为复数 2)DFT与DFT的计算量相当
2. DFT的运算量 回忆DFT和IDFT的变换式： ( ) 0 1 1 ( ) [ ( )] 1 0 = = − − = − X k W n N N x n IDFT X k N k nk ( ) [ ( )] ( ) 0 1 1 0 = = − − = X k DFT x n x n W k N N n nk N 1）x(n)为复数， 也为复数。 2）DFT与IDFT的计算量相当。 nk N j nk N W e 2 − = 注意：
以DFT为例: X(k)=DFx(m)=∑x(m)W0≤k≤N-1 H=0 计算机运算时(编程实现): k=0X(0)=x(0W0+x(1)WN0+…+x(N-1-10 k=1X(1)=x(0X+x(1W+…+x(N-1)WX) (N-1)2 N个点 k=2X￥(2)=x(02+x(1)W2+…+x(N-1)WN k=N-1X(N-1)=x0+x()w+…+x(N-1)Wy-1 N次复乘,N-1次复加
计算机运算时（编程实现）： k = 0 0 0 1 0 ( 1) 0 (0) (0) (1) ( 1) − = + + + − N N N N WN X x W x W x k =1 01 11 ( 1) 1 (1) (0) (1) ( 1) N X x W x W x N W N N N − = + + + − k = 2 0 2 1 2 ( 1) 2 (2) (0) (1) ( 1) N X x W x W x N W N N N − = + + + − k = N −1 0 1 1 1 ( 1) 1 ( 1) (0) (1) ( 1) N N N N X N x W x W x N W N N N − − − − − = + + + − N次复乘，N-1次复加 N个点 ( ) [ ( )] ( ) 0 1 1 0 = = − − = X k DFT x n x n W k N N n nk N 以DFT为例：
运算量 复数乘法复数加法 个X(K) N N-1 N个X(k) N r(n N(N-1) 刀=0 (N点DFT) (atjb(c+(ac-bd)+j(bctad) 实数乘法实数加法 一次复乘4 次复加 22 个X(1) AN 2N+2(N-1)=2(2N-1) N个X(k) 4N2 2N(2N-1) (N点DFT)
复数乘法 复数加法 一个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 ( ) N nk N n x n W − = 运算量 (a+jb)(c+jd)=(ac-bd)+j(bc+ad)
例:计算一个N点DFT,共需N2次复乘。以做一次 复乘1μs计,若N=4096,所需时间为 (4096)2=167016≈17 例:石油勘探,有24个通道的记录,每通道波形记 录长度为5秒,若每秒抽样500点/秒, 1)每道总抽样点数:500*5=2500点 2)24道总抽样点数:24*2500=6万点 3)DFT复乘运算时间:N2=(600002=36*108次 (60000=36*103=36005
例：计算一个 N点DFT ，共需N2次复乘。以做一次 复乘1μs计，若N =4096，所需时间为 (4096) 16777216 s 17s 2 = 例：石油勘探，有24个通道的记录，每通道波形记 录长度为5秒，若每秒抽样500点/秒， 1）每道总抽样点数：500*5=2500点 2）24道总抽样点数：24*2500=6万点 3）DFT复乘运算时间：N2=(60000)2=36*108次 (60000) 36*10 s 3600s 2 8 = =
由于计算量大,且要求相当大的内存,难以实现实 时处理,限制了DFT的应用。长期以来,人们一直在寻 求一种能提高DFT运算速度的方法。 FFT便是 Cooley& Tukey在1965年提出的的快速 算法,它可以使运算速度提高几百倍,从而使数字信号 处理学科成为一个新兴的应用学科
由于计算量大，且要求相当大的内存，难以实现实 时处理，限制了DFT的应用。长期以来，人们一直在寻 求一种能提高DFT运算速度的方法。 FFT便是 Cooley & Tukey 在1965 年提出的的快速 算法，它可以使运算速度提高几百倍，从而使数字信号 处理学科成为一个新兴的应用学科
第二节改善DFT运算效率的基本途径 1、利用DFT运算的系数W和的固有对称性和周期 性,改善DFT的运算效率。 1)对称性 2)周期性 3)可约性
第二节 改善DFT运算效率的基本途径 kn WN 1、利用DFT运算的系数 的固有对称性和周期 性，改善DFT的运算效率。 1）对称性 2）周期性 3）可约性
2丌 Wx的特性W=cN 对称性(WW)=W=W()=WNA WN W k W.wrn 周期性Ww=W(+n=WmN 可约性W=WmW=Wm 2丌N j-mnk N 2 丌 特殊点:W=1W2=-1W(+N2)=-W
( ) ( ) nk N n k n N k W W W N N N + + 周期性 = = nk mnk 可约性 W W N mN = / / nk nk m W W N N m = 2 j mnk mN e − 2 2 1 N j N j e e − − = = − 0 / 2 ( / 2) 1 1 N k N k W W W W N N N N + 特殊点： = = − = − nk WN 的特性 2 j nk nk N W e N − = * ( ) ( ) ( ) nk nk N n k n N k W W W W N N N N − − − 对称性 = = = Nk nk W W N N − nN nk W W N N −
2、将长序列DFT利用对称性和周期性分解为短 序列DFT的思路 因为DFT的运算量与N2成正比的,如果一个大 点数N的DFT能分解为若干小点数DFT的组合,则 显然可以达到减少运算工作量的效果
2、将长序列DFT利用对称性和周期性分解为短 序列DFT的思路 因为DFT的运算量与N2成正比的，如果一个大 点数N的DFT能分解为若干小点数DFT的组合，则 显然可以达到减少运算工作量的效果
