信号分析与处理 教学课件 作者 杨西侠 柯晶 3-4FFT.ppt

《信号分析与处理 教学课件 作者 杨西侠 柯晶 3-4FFT.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、3.6.1DFT运算的特点1.DFT计算工作量将x(n)与WNnK两两相乘再取和即可得到X(k)。每计算一个X(k)值需要进行N次复数相乘，和N1次复数相加。对于N个X(k)点，应重复N次上述运算。因此，要完成全部DFT运算共需N2次复数乘法和N(N1)次复数加法。例如N=4，需N2=16次乘法和N(N1)=12次加法。例如N=10，需N2=100次乘法和N(N1)=99次加法。而N=1024，就需要1048576次乘法运算。3.6快速傅里叶变换（FFT）1随着N值加大，运算工作量将迅速增长，按照这种规律，如果在N较大的情况下，要求对于信号进行实时

2、处理，所需的运算速度就难以实现。为了改进算法，减少运算工作量。考虑系数WnK的周期性与对称性，合理安排重复出现的相乘运算，将使计算工作量显著减少。2.改进思路1）Wnk的周期性WNnk=WN(n+lN)(k+mN)例N=4W46=W42W49=W41等等2）Wnk的对称性WN(nk+N/2)=WNnkWNN/2=12例N=4W43=W41W42=W40等等------周期性----对称性W矩阵与x(n)相乘过程中，存在着不必要的重复计算。33.6.2基2按时间抽取的FFT算法（时析型）1.原理把N点DFT运算分解为两组N/2点的DFT运算，然后取和

3、。对序列x(n)取N点DFT，假定N是2的整数次方N=2M把x(n)取N点DFT运算按n为偶数和奇数分解为两部分以符号2r表示偶数n，以符号2r+1示奇数n，r=0,1,…，N/214式中WN2转换为WN/2，且记g(r)=x(2r)，h(r)=x(2r+1)。一个N点的DFT已被分解为两个N/2点的DFT。注意G(k)和H(k)只有N/2个点，r=0,1,…,N/21，而X(k)需要N个点，k=0,1,…,N1，如果以G(k)，H(k)表达全部X(k)，应利用G(k)与H(k)的两个重复周期。5G(k+N/2)=G(k)H(k+N/2)=H(k)W

4、N(k+N/2)=WNN/2WNk=WNk全部关系式X(k)=G(k)+WNkH(k)k=0,1,…，N/21X(k+N/2)=G(k+N/2)WNkH(k+N/2)=G(k)WNkH(k)x(n)n=0,1…N1x(2r)=g(r)r=0,1…N/21x(2r+1)=h(r)r=0,1…N/21G(k)N/2点DFTN/2点DFTH(k)WNkWNkX(k)X(k+N/2)6基本运算单元呈蝴蝶形蝶形运算单元包括两次复数乘法和两次复数加法G(k)H(k)WNkWNkX(k)X(k+N/2)X(k)=G(k)+WNkH(k)X(k+N/2

5、)=G(k)WNkH(k)可简化为一次复数乘法和两次复数加法7X(1)X(3)以N=4为例说明X(0)=G(0)+W40H(0)k=0X(1)=G(1)+W41H(1)k=N/21=1X(2)=G(0)W40H(0)X(3)=G(1)W41H(1)x(0)x(2)N/2点DFT(n偶)G(0)G(1)W40W40W41W41X(0)X(2)x(1)x(3)H(0)H(1)N/2点DFT(n奇)8结论：由G(k)、H(k)获得X(k)的过程中，共包含N/2个蝶形结运算，因此，共需N/2次复数乘法和N次复数加减法。当N=4时，为2次乘、4次加。为了

6、从x(n)求出G(k)、H(k)，按n的奇偶分别组合两个N/2点的DFT运算，得G(0)=x(0)+W20x(2)G(1)=x(0)W20x(2)H(0)=x(1)+W20x(3)H(1)=x(1)W20x(3)按照同样原理，把这些运算也化成蝶形图。9很明显，左半图的流程图，仍然由N/2个蝶形结组成，因此，运算量还是N/2次乘，N次加法。这样为完成全部的运算，共需次乘法2N/2=4和2N=8次加法；而直接进行N=4的DFT全部运算量为N2=16次乘和N(N-1)=12次加。经分组简化后构成的快速算法其运算工作量显著减少。X(1)X(3)x(0)x(2

7、)G(0)G(1)W40W40W41W41X(0)X(2)x(1)x(3)H(0)H(1)W20W20W20W2010对于N=22=4的情况，只进行了一次奇偶分解。把全部运算过程分为两级蝶形流程图。对于N=2M的任意情况，需要把这种奇偶分解逐级进行下去。当N=23=8，分组运算的方框图如图示。N点组合相加x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)N/4点DFTN/4点DFTN/4点DFT偶N/2点DFTN/2点DFTN/4点DFT奇奇偶奇X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)11W20W80x(0)x

8、(4)x(2)x(6)x(1)x(5)x(3)x(7)W20W20