资源描述：
《数字信号处理傅里叶计算》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第9章离散傅里叶变换的计算¢9.0引言¢9.1离散傅里变换的高效计算¢9.2Goertzel算法¢9.3按时间抽取的FFT算法¢9.4按频率抽取的FFT算法¢9.5小结9.0引言¢降低离散傅里叶变换的计算量¢方法：¢利用离散傅里叶变换系数的对称性和周期性¢主要算法：¢Goertzel算法¢按时间抽取的FFT算法¢按频率抽取的FFT算法¢里程碑：¢1965年CooleyTukery9.1离散傅里变换的高效计算¢N点有限长序列的DFT：N−1knX]k[=∑]n[xWN,k=,1,0"，N−,1n=0¢反变换：N−11
2、−kn]n[x=∑X]k[WN,n=,1,0"，N−,1Nk=0¢直接计算：N−1knknX]k[=∑[(Re{n[x]}Re{WN}−Im{n[x]}Im{WN})n=0knkn+j(Re{n[x]}Im{W}+Im{n[x]}Re{W})],NNk=,1,0"，N−,1计算复乘复加实乘实加复乘142复加12X[k]NN-14N4N-2DFT4N24N2+2NFFT傅里叶变换系数的性质¢对称性（复共轭对称）k()N−n−kn(kn)*W=W=WNNN¢周期性（n,k的周期性）knk(N+n)n(N+k)W=W=W
3、NNNN−1knknX]k[=∑[(Re{n[x]}Re{WN}−Im{n[x]}Im{WN})n=0knkn+j(Re{n[x]}Im{W}+Im{n[x]}Re{W})],NNk=,1,0"，N−,1¢利用对称性可直接计算n和N-nknk(N−n)Re{x[n]}Re{W}+Re{x[N−n]}Re{W}NN()kn=Re{x[n]}+Re{x[N−n]}Re{W}Nknk(N−n)−Im{x[n]}Im{W}−Im{x[N−n]}Im{W}NN()kn=−Im{x[n]}−Im{x[N−n]}Im{W}N乘法
4、减少1/2，利用对称性可大量降低计算量离散傅里变换快速算法的寻找过程¢1805年的高斯¢Runge(1905),Danielson&Lanczos(1942)指出DFT的计算量正比于NlogN而不是NN。¢1965年CooleyTukery的论文指出，当N为复合数时，可以进行分解。该论文为DFT的快速算法的发现指出了一条行之有效的方法。此后出现了一大批快速算法：按时间抽取的FFT算法、按频率抽取的FFT算法、素因子法等等。9.2Goertzel算法¢利用了周期性−kn2(jπ/N)Nk2jπkW=e=e=1NN−1
5、N−1−kNkr−(kN−)rX]k[=WN∑]r[xWN=∑]r[xWNr=0r=0¢定义一个中间序列∞−k(n−r)−knyk[n]=∑x[r]WNu[n−r]=x[n(*]WNu[n])r=−∞X]k[=y
6、]n[kn=Nx[]nyn[]k−1z−kWNXk[]的一阶复递推计算流图计算复复实乘实加1乘加H)z(=k−k−11−WNz复乘142复加12X[k]NN-14N4N-21144•极点：xn[]ynk[]−1z–2次实乘4次2πk实加（每个样本2cos()k−WNN的计算量）−1z–2N次实乘4N次实加
7、−1•零点：Xk[]的二阶递推计算流图（Goertzel算法）–迭代的最后一次计算4次实乘4次实加kk−−1111−−WzWzNNHz()==k−kk−−11−1−2(1−−−Wz)(1Wz)12cos(2πkNzz/)+NN计算量¢极点：¢2次实乘4次实加（每个样本的计算量）¢2N次实乘4N次实加¢零点：¢迭代的最后一次计算4次实乘4次实加¢共需：22¢2N+4N次实乘4N+4N次实加¢利用共轭对称¢一次可以算出两个点的极点，零点复共轭。所以一次可以算出两个点。N2+2N次实乘2N2+2N次实加¢可以计算N点DF
8、T其中的任意长（M）¢其计算量MN9.3按时间抽取的FFT算法2点DFT两个2点2点DFTDFTX1(k)两个2点DFT两个2点4点DFTDFT2点DFT两个…...N/2点2点DFT两个2点DFTDFT2点DFT两个X2(k)2点DFT两个2点4点DFT2点DFTDFTx(n)一.DFT的计算工作量N−1nkX(k)=∑x(n)WN,k=,1,0",N−1n=0N−11−nkx(n)=∑X(k)WN,n=,1,0",N−1Nk=0两者的差别仅在指数的符号和因子1/N.一个X(k)的值的工作量,如X(1)012N−
9、1X)1(=x)0(W+x)1(W+x)2(W+"+x(N−)1WNNNNnk通常x(n)和W都是复数,所以计算一个NX(k)的值需要N次复数乘法运算,和N−1次复数加法运算.那么,所有的X(k)就要N2次复数乘法运算,N(N-1)次复数加法运算.当N很大时,运算量将是惊人的,如N=1024,则要完成1048576次(一百多万次)运算.这样,难以做到实时处理
