DSP-Chapt4-zhuzwin

《DSP-Chapt4-zhuzwin》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第四章快速傅里叶变换FFT:FastFourierTransform1965年，Cooley,Tukey《机器计算傅里叶级数的一种算法》快速付里叶变换（FFT）的提出♦DFT可以对信号进行频谱分析，在通信技术、图像传输、语音压缩、生物医学等领域都有应用♦但直接计算DFT计算量太大，很难实时地处理问题，因此在很长一段时间里，它并没有得到真正的运用，频谱分析大多采用模拟信号滤波的方法解决。♦1965年美国IBM公司的库利和图基提出了DFT的快速算法—FFT算法。使DFT的运算大大简化，运算时间缩短了1-2个数量级，FFT的问

2、世使DFT在实际中得到广泛应用。♦FFT并不是一种新的变换，它只是DFT的一种快速算法，并且根据对序列分解与选取方法的不同而产生了FFT的多种算法。♦FFT在离散傅里叶反变换、线性卷积和线性相关等方面有重要应用。学习目标●理解直接计算DFT存在的问题及改进途径。●多种FFT算法♦掌握按时间抽选的基-2FFT算法的算法原理、运算流图、所需计算量和算法特点♦掌握按频率抽选的基-2FFT算法的算法原理、运算流图、所需计算量和算法特点♦掌握IFFT算法♦了解混合基、基-4FFT、分裂基和CZT算法（自学）●FFT的应用♦理解线性

3、卷积的FFT实现（分段卷积方法）本章作业（P194-195）：1、2、3、14（选做）一、直接计算DFT存在的问题及改进途径Nx点有限长序列()nDFT:N−1nk()XkD==FTx[()]n∑x()nWRkNN()n=0IDFT:N−11−nk()xnI==DFTXk[()]∑Xk()WRnNN()Nk=0★运算量X(k)=N点DFT复数乘法复数加法N−1∑x()nWnk计算一个X(k)NN–1Nn=0计算N个X(k)N2N(N–1)(aj++=−++bcj)(da)(cbdja)(dcb)实数乘法实数加法一次复乘4

4、2一次复加2一个X(k)4N2N+2(N–1)=2(2N–1)N个X(k)4N22N(2N–1)(N点DFT)♦例1:当N=210=1024点时，直接计算DFT需要:●DFT运算时间=N2=220=1048576次，即一百多万次的复乘运算对于实时性很强的信号处理(如雷达信号处理)来讲，迫切需要改进DFT的计算方法，以减少运算量。♦例2：石油勘探，24道记录，每道波形记录长度5秒，若每秒抽样500点，则●每道总抽样点数=500*5=2500点●24道总抽样点数=24*2500=6万点●DFT运算时间=N2=(60000)2

5、=36*108次如何解决？解决办法？（1）将长序列的DFT分解为短序列的DFT♦思路：由于DFT的运算量与N2成正比，如果一个大点数的DFT能分解为若干小点数DFT的组合，显然可以减少运算工作量♦将一个N（=2m）点的长序列的DFT分解为N/2个2点的短序列的DFT，则运算量由N2变为N/2×22，对于大N，可显著减少运算量，提高运算效率。例如10242>>(1024/2)×222π−jnk（2）利用nkN的特性减少运算次数We=Nnk*(−nkNnk−−)nNk()对称性(WWWW)===NNNN−mN−mW=W↓NN

6、↓Nk−nknN−nkWW⋅WW⋅NNNNnk()Nnk+nNk()+周期性WW==WNNNnkmnknknkm/可约性WW=WW=NmNNN/m↓2πN2π−⋅j−jmnkeeN2=−jπ=−1emN↑0/Nk2(+N/2)k特殊点：WW=1=−1W=−WNNNN★FFT算法思想m◆将（一个N=2点的）长序列的DFT分解为（N/2个2点）的短序列的DFT，从而减少DFT的运算量。nk◆利用旋转因子W的特性（共轭对称性、周期N性和可约性），可进一步减少DFT的运算量FFT算法分类♦按时间抽选的FFT算法：时间抽选法DIT

7、:Decimation-In-Time♦按频率抽选的FFT算法：频率抽选法DIF:Decimation-In-Frequency二、按时间抽选的基-2FFT算法1、算法原理设序列点数N=2L，L为整数。若不满足，则补零。N为基数2的整数次幂的FFT称基-2FFT。将序列x(n)按n的奇偶分成两组（两个N/2点的子序列）：x(r)=x(2r)1rN=−0,1,...,/21x(r)=x(2r+1)2则x(n)的DFT为:NNN−111−−nknknkX()kx==+∑∑∑()nWxNNN()nWx()nWnnn=000==

8、n为偶数n为奇数NN/21−/21−2rk()21rk+=+∑∑xrW()22NNxrW(+1)rr=00x(r)=x(2r)=1rN=0,1,...,/21−x(r)=x(2r+1)2NN/21−/21−rkkrk=+∑∑xrW1/()NN2WxrW2/()N2rr=00=k=+X12(kWXk)N()rk,0=,