资源描述：
《北京邮电大学 数字信号处理 课件第3章_2》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、3.5快速离散傅氏变换FFT3.5快速离散傅氏变换FFTFFT是DFT的高效运算方法。DFT的重要应用计算DFT的一个值X(k)需要进行N次复数乘法和(N-1)是频谱分析，若直接计算DFT，则计算量非常次复数加法，为得到全部的DFT系数，直接计算N2大，尤其当序列长度很大时。点DFT需要N次复数乘法和N(N-1)次复数加法，而一次复数乘法需要４次实数乘法和两次加法。即：N−1nkN点DFT:2次复数乘法，N(N-1)次复数加法DFT:X(k)=∑x(n)W,k=0,1,LN−1NNn=0如N=512时，DFT的乘法运算N−11−nkIDFT:x(n)=∑X(k)W,
2、n=0,1,LN−122NN=512=262144(26万次)Nk=0北京邮电大学电信工程学院北京邮电大学电信工程学院123.5快速离散傅氏变换FFT时间抽选法2π−j()kn1965年，Cooley与Turkey提出了FFT算基本思路：利用knN的周期性和对称性，将W=eN法，大大减少了计算次数。付氏变换DFT分解成相继小的DFT计算如N=512时，FFT的乘法次数约为2000次，提高了约128倍，而且简化随N的增加而巨增，（即省去DFT计算中很多重复的计算）。因而用数值方法计算频谱得到实际应用。所谓时间抽取法，就是将序列x(n)分解成小的子序列，然后对子序列进行
3、DFT计算，减少运算量。北京邮电大学电信工程学院北京邮电大学电信工程学院34时间抽选法时间抽选法kn1．的WN性质(1)周期性:(3)其它knn(k+N)k(n+N)WN=WN=WNNNN−j2π⋅N(mN+)mNN2W2=W2=W⋅W2=e=−1lNNNN所以，W=Wl+N=Wl+2N=LL，这样在计算DFT时2πNN2π−j⋅k−j⋅2kN就可以把它们看作同一个数，只计算一次就行了。W2k=eN=e2=WkNN如果在作乘法时适当安排，则可以节省大量的计算。2利用以上的性质，都可以节省大量的计算。(2)对称性:[Wnk]*=W−kn=W(−n)k=W(N−n)kN
4、NNNnk*(N−k)n[W]=WNN北京邮电大学电信工程学院北京邮电大学电信工程学院561分解定理分解定理设x(n)为给定的N点序列，则：证明：NN−1−1N−122N−1knk(2r)k(2r+1)knn=0,1,L,N−1X(k)=∑x(n)W=∑x(2r)W+∑x(2r+1)WX(k)=∑x(n)W,NNNNk=0,1,L,N−1n=0r=0r=0n=0NN假定N为2整数次幂,把x(n)分为偶数序列a(n)和奇−1−122krkkr数序列b(n)，即：=∑x(2r)WN2+WN∑x(2r+1)WN2DFTr=0r=0⎧a(n)=x(2n)a(n)←⎯→⎯A(
5、k)NNN/2−1−1⎨DFT22⎩b(n)=x(2n+1)b(n)←⎯→⎯B(k)=a(r)Wkr+Wkb(r)Wkr其长度为N/2，N/2∑N2N∑N2r=0r=0则：kX(k)=A(k)+WB(k)kN=A(k)+WB(k)N北京邮电大学电信工程学院北京邮电大学电信工程学院78分解定理分解定理NN−1−1NN2N2N∵A(k)、B(k)是由N/2个样点形成的DFT。k=0,1L−1则A(k)=A(+l)=x(2r)Wr(2+l)=x(2r)Wr2⋅Wrl2∑N∑NN2r=02r=022∴X(k)中k的范围为0~N-1，还应进一步考虑N/2~N-1的情况。NNN
6、−1当时k=,+1,L,N−1，2rl22=∑x(2r)WN=A(l)NNr=02令k=+l其中l=0,L,−122同理：N647分为三部分4484B(k)=B(+l)=B(l)k而：2QX(k)=A(k)+WB(k){{N{Nk(+l)l第一第三第二W=W2=−WNNN北京邮电大学电信工程学院北京邮电大学电信工程学院910分解定理分解定理x(0)A(0)x(0)X(0)因此：x(2)A(1)⎧kx(1)X(1)⎪X(k)=A(k)+WNB(k)Nx(4)4点DFTA(2)⎨Nkk=0,1,L,−1x(2)X(2)X(k+)=A(k)−WB(k)2⎪⎩2Nx(6)A
7、(3)x(3)X(3)X(k)与A(k)、B(k)的关系可用信号流图表示出来，即把一个N点的DFT分解为两个N/2点的DFT，而x(1)B(0)W0-1x(4)8X(4)且仅是最后的求和的符号不同。1kx(5)x(3)B(1)W8-1X(5)A(k)A(k)+WNB(k)4点DFTx(5)2-1B(2)W8x(6)X(6)kWB(k)N-1k3A(k)−WNB(k)x(7)B(3)W8-1x(7)X(7)北京邮电大学电信工程学院北京邮电大学电信工程学院11122分解定理分解定理∵DFT的运算量正比于N22k同理：B(k)=E(k)+WF(k)N∴将N点DFT分解
