例:计算一个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的组合，则 显然可以达到减少运算工作量的效果