离散傅里叶变换.pptx

《离散傅里叶变换.pptx》由会员分享，可在线阅读，更多相关《离散傅里叶变换.pptx（61页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、现在学习的是第1页，共61页现在学习的是第2页，共61页现在学习的是第3页，共61页计算DFT复数运算量10)()1(NnnNWnxX现在学习的是第4页，共61页利用 的固有对称性和周期性改善DFT的运算效率knNWknNW的对称性：nkNknNWW*)(knNW的周期性：)()(kNnNkNnNknNWWW1)()(22kjkNNjkNNeeW因为：1,1,0Nk1)()(22njNnNjNnNeeW1,1,0Nn由此可得出：nkNknNNkNnNWWW)()(1sincos)(222/jeWNNjNNkNNkNWW)(2现在学习的是第5页，共61页nkNW 的特性*()()()nknkN

2、n kn N kNNNNWWWW对称性()()nkN n kn N kNNNWWW周期性 nkmnkNmNWW可约性/nknk mNN mWW0/2(/2)11Nk NkNNNNWWWW 特殊点：2jnknkNNWeNknkNNWWnNnkNNWW2jmnkmNe221NjjNee 现在学习的是第6页，共61页时间抽取基-2FFT算法Decimation-in-Time(DIT)现在学习的是第7页，共61页一、算法原理一、算法原理n设输入序列长度为N=2M(M为正整数，将该序列按时间顺序的奇偶分解为越来越短的子序列，称为基2按时间抽取的FFT算法。也称为Coolkey-Tukey算法。n其中基

3、数2-N=2M，M为整数。若不满足这个条件，可以人为地加上若干零值（加零补长）使其达到 N=2M。现在学习的是第8页，共61页1、算法推导 12221xrx rxrxr0,1,.,/2 1rN将序列x(n)按n的奇偶分成两组：N为2的整数幂的FFT算法称基-2FFT算法。现在学习的是第9页，共61页 111000NNNnknknkNNNnnnX kx n Wx n Wx n Wn为偶数n为奇数/2 1/2 121200221NNrkrkNNrrxr WxrW /2 1/2 1221200NNrkrkkNNNrrx rWWxrW /2 1/2 11/22/200NNrkkrkNNNrrx r W

4、Wxr W 12kNXkW Xk,0,1,./2 1r kN现在学习的是第10页，共61页12/1,0)()()21NkDFTNkXWkXkXkN中的前半部分点又合成（现在学习的是第11页，共61页1212()()()()()()2kNkNX kX kW XkNX kX kW Xk0,1,.,/21kN 121122,/222XkXkNNNXkXkXkXk是以为周期的/22NkNkkNNNNWWWW 又现在学习的是第12页，共61页12/012/022/2)2/(2/2212/012/012/1)2/(2/11)2/(2/2/)()()()2()()()()2(NrNrrkNkNrNNrNrr

5、kNkNrNNkrNrkNkXWrxWrxkNXkXWrxWrxkNXWW后半部的k值所对应的X1(k),X2(k)则完全重复了前半部分的k值所对应的X1(k),X2(k)的值。)()()(212/)2/kXWkXkXWWWWkNkNkNNNkNN后半部分：又（现在学习的是第13页，共61页频域中的N个点频率成分为：)()()2/()()()(2121kXWkXNkXkXWkXkXkNkN后半部分：前半部分：?结论：只要求出（0N/2-1）区间内的各个整数k值所对应的X1(k),X2(k)值，即可以求出(0N-1)整个区间内全部X(k)值，这就是FFT能大量节省计算的关键。现在学习的是第14页

6、，共61页v由于N=2L，因此N/2仍为偶数，可以依照上面方法进一步把每个N/2点子序列，再按输入n的奇偶分解为两个N/4点的子序列，按这种方法不断划分下去，直到最后剩下的是2点DFT，两点DFT实际上只是加减运算加减运算。现在学习的是第15页，共61页例子：求 N=23=8点FFT变换)()()2/()()()(2121kXWkXNkXkXWkXkXkNkN12/,0Nk先将N=8DFT分解成2个4点DFT：可知：时域上：x(0),x(2),x(4),x(6)为偶子序列 x(1),x(3),x(5),x(7)为奇子序列 频域上：X(0)X(3)，由X(k)给出 X(4)X(7),由X(k+N

7、/2)给出现在学习的是第16页，共61页2、蝶形结即蝶式计算结构也即为蝶式信号流图上面频域频域中前/后半部分表示式可以用蝶形信号流图表示。X1(k)X2(k)kNW)()(21kXWkXkN)()(21kXWkXkN作图要素：作图要素：(1)左边两路为输入左边两路为输入(2)右边两路为输出右边两路为输出(3)中间以一个小圆表示加、中间以一个小圆表示加、减运算（右上路为相加输出、减运算（右上路为相加输出、右下路为相减输出右下路为相减输出)(4)如果在某一支路上信号需要进行相乘运如果在某一支路上信号需要进行相乘运算，则在该支路上标以箭头，将相乘的系算，则在该支路上标以箭头，将相乘的系数标在箭头旁。

8、数标在箭头旁。(5)当支路上没有箭头及系数当支路上没有箭头及系数时，则该支路的传输比为时，则该支路的传输比为1。现在学习的是第17页，共61页将N=8点分解成2个4点的DFT的信号流图X(4)X(7)同学们自已写4点DFTx(0)x(2)x(4)x(6)4点DFTx(1)x(3)x(5)x(7)08W18W28W38WX(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)X1(0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)偶数序列奇数序列3821282118210821)3()3(3)2()2(2)1()1(1)0()0(0WXXXWXXXWXXXWXXX

9、）（）（）（）（如：x1(r)x2(r)现在学习的是第18页，共61页奇序列、偶序列、)6()2()4()0(:)(1xxxxrx奇序列、偶序列、同理：)7()3()5()1(:)(2xxxxrx1014012()()2(4131，），在此（）奇序列（）偶序列若设：LNLLXLxLXLx1014012()()2(6252，），在此（）奇序列（）偶序列同理：LNLLXLxLXLx现在学习的是第19页，共61页b 求2点的DFT)()4/()()()()()()()4/10)()()12()2()()(62/5262/52242/3142/314/0)12(2/114/022/1111LXWLXN

10、kXLXWLXkXrxLXWLXNkXLLXWLXWLXWLXkXkXrxkNkNkNkNNLkLNNLLkNDFT）也可分解为：同样，（同理：，其中（可分解为：现在学习的是第20页，共61页c 一个2点的DFT蝶形流图2点DFT2点DFTx(0)x(4)x(2)x(6)X3(0)X3(1)X4(0)X4(1)X1(0)X1(1)X1(2)X1(3)04W14W01134413440113441344(0)(0)(0)(1)(1)(1)(2)(0)(0)(3)(1)(1)XXW XXXW XXXW XXXW X其中现在学习的是第21页，共61页d 另一个2点的DFT蝶形流图2点DFT2点DFT

11、x(1)x(5)x(3)x(7)X5(0)X5(1)X6(0)X6(1)X2(0)X2(1)X2(2)X2(3)04W14W01254625460125462546(0)(0)(0)(1)(1)(1)(2)(0)(0)(3)(1)(1)XXW XXXW XXXW XXXW X其中同理：现在学习的是第22页，共61页(3)将N/4（2点）DFT再分解成2个1点的DFT021022120202120230202020231021,0;1,0)4()0()4()0()1()4()0()4()0()0()()(2WWknWWWWWxWxWxWxXWxWxWxWxXWnxkXnknknkNnkNnnkN

12、，其中，则这里用到对称性这是一蝶形结代入上面流图可知：最后剩下两点DFT,它可分解成两个一点DFT，但一点DFT就等于输入信号本身，所以两点DFT可用一个蝶形结表示。取x(0)、x(4)为例。现在学习的是第23页，共61页b 2个1点的DFT蝶形流图1点DFTx(0)1点DFTx(4)X3(0)X3(1)02W进一步简化为蝶形流图：02WX3(0)X3(1)x(0)x(4)4()0()4()0()1()4()0()4()0()0(023023xxxWxXxxxWxX其中：现在学习的是第24页，共61页(4)一个完整N=8的按时间抽取FFT的运算流图x(0)x(4)x(2)x(6)x(1)x(5

13、)x(3)x(7)38W28W18W08W08W08W08W08W08W08W28W28WX(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)12/0NNNWW 其中旋转因子，共有m=0m=1m=2x1(0)x1(1)x1(2)x1(3)x2(0)x2(1)x2(2)x2(3)x3(0)x3(1)x4(0)x4(1)x5(0)x5(1)x6(1)x6(0)现在学习的是第25页，共61页3 按时间抽取FFT算法的特点现在学习的是第26页，共61页算法特点1111()()()()()()rmmmNrmmmNXkXkXj WXjXkXj Wm表示第m级迭代，k，j表示数据所在的行数现在学

14、习的是第27页，共61页180818084,3,2,1WRWRWRWR暂存器x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(0)=x(0)A(1)=x(1)A(2)=x(2)A(3)=x(3)A(4)=x(4)A(5)=x(5)A(6)=x(6)A(7)=x(7)R1R1R1R1R1R2R1R1R2R2R3R4看出：用原位运算结构运算后，A(0)A(7)正好顺序存放X(0)X(7),可

15、以直接顺序输出。现在学习的是第28页，共61页 码位倒序规则现在学习的是第29页，共61页以N=8为例：01234567000001010011100101110111自然顺序二进制码表示码位倒读码位倒置顺序00010001011000110101111104261537看出：码位倒读后的顺序刚好是数据送入计算机内的顺序。现在学习的是第30页，共61页2 102()()x nnn n n2 102()nn n n0 122()nn n n现在学习的是第31页，共61页2log22FNNmLN2logFaNLNN222()2()loglog2FFmDFTNNNmFFTNN现在学习的是第32页，共

16、61页现在学习的是第33页，共61页NN2log2现在学习的是第34页，共61页现在学习的是第35页，共61页频率抽取基-2FFT算法Decimation-in-Frequency(DIF)现在学习的是第36页，共61页N=2M，M将X(k)按k的奇偶分组前，先将输入x(n)按n的顺序分成前后两半。现在学习的是第37页，共61页1/2 1100/2()()()()NNNnknknkNNNnnn NX kx n Wx n Wx n W/2 1/2 1200()2NNNnknkNNnnNx n Wx nW/2 1/20()2NNknkNNnNx nx nWW/2 10()(1)2NknkNnNx

17、nx nW 0,1,.,1kN/21NNW 现在学习的是第38页，共61页k的奇偶将X(k)221krkr0,1,.,/2 1rN/2 120(2)()2NnrNnNXrx nx nW/2 1(21)0(21)()2NnrNnNXrx nx nW/2 1/20()2NnrNnNx nx nW/2 1/20()2NnnrNNnNx nx nWW现在学习的是第39页，共61页12()()2()()2nNNx nx nx nNx nx nx nW0,1,.,12Nn 则X(2r)和X(2r+1)分别是x1(n)和x2(n)的 N/2点DFT，记为X1(k)和X2(k)现在学习的是第40页，共61页x

18、1(0)x1(1)-1x1(2)x1(3)-1x2(0)x2(1)-1x2(2)x2(3)-1N/2点DFTN/2点DFTx(0)x(7)x(1)x(2)x(3)x(4)x(5)x(6)X1(0)=X(0)X2(0)=X(1)X1(1)=X(2)X1(2)=X(4)X1(3)=X(6)X2(1)=X(3)X2(2)=X(5)X2(3)=X(7)1NW0NW2NW3NW现在学习的是第41页，共61页311411/2()()(/4)()()(/4)nNx nx nx nNx nx nx nNW0,1,.,14Nn 313414()(2)()()(21)()XkXkDFT x nXkXkDFT x

19、n0,1,.,14Nk 现在学习的是第42页，共61页x3(0)x3(1)-1-1x4(0)x4(1)N/4点DFTN/4点DFTx1(0)x1(1)x1(2)x1(3)X3(0)=X1(0)=X(0)X4(0)=X1(1)=X(2)X3(1)=X1(2)=X(4)X4(1)=X1(3)=X(6)0/2NW1/2NW现在学习的是第43页，共61页0,1,.,14Nk 525626()(2)()()(21)()XkXkDFT x nXkXkDFT x n522622/2()()(/4)()()(/4)nNx nx nx nNx nx nx nNW0,1,.,14Nn 现在学习的是第44页，共61

20、页现在学习的是第45页，共61页0033223330103322333(0)(0)(0)(1)(0)(1)(4)(1)(0)(1)(0)(1)NXXxWW xxxXXxWW xxxW/4 1133/43/400()()()NlklkNNllXkx l Wx l W0,1k x3(n)，x4(n)，x5(n)，x6(n)，n=0,10044224440104422444(2)(0)(0)(1)(0)(1)(6)(1)(0)(1)(0)(1)NXXxWW xxxXXxWW xxxW/4 1144/44/400()()()NlklkNNllXkx l Wx l W0,1k 现在学习的是第46页，共6

21、1页x1(0)x1(1)x1(2)x1(3)x2(0)x2(1)x2(2)x2(3)x3(0)x3(1)x4(0)x4(1)x5(0)x5(1)x6(0)x6(1)现在学习的是第47页，共61页&DIF与DIT比较1DIF与与DIT两种算法均为原位运算。两种算法均为原位运算。算法是两种等价的与次复加次复乘FFTDITDIFNaNmNFNF22lglg2现在学习的是第48页，共61页&DIF与DIT比较2现在学习的是第49页，共61页快速傅里叶逆变换(IFFT)现在学习的是第50页，共61页以上所讨论的FFT的运算方法同样可用于IDFT的运算，简称为IFFT。即快速付里叶反变换。从IDFT的定义

22、出发，可以导出下列二种利用FFT来计算IFFT的方法。现在学习的是第51页，共61页v 利用FFT计算IFFT的思路1IDFTFFTNWWDFTWnxnxDFTkXWkXNkXIDFTnxnkNnkNNknkNNknkN算法都可以拿来运算或频率抽取抽取）那么以上讨论的时间（将运算结果都除以改成运算中的每个系数只要把3)2()1()()()()(1)()(1010现在学习的是第52页，共61页v 利用FFT计算IFFT的思路2现在学习的是第53页，共61页现在学习的是第54页，共61页10*10*10*10)()()(1()(1)()(1)()(1)(NnnkNnkNNknkNNknkNNkWn

23、xkXkXDFTNWkXNnxWkXNnxWkXNnx比较与取共轭再取共轭）对它取共轭：此为DFT可用FFT程序v 利用FFT计算IFFT的思路3现在学习的是第55页，共61页1*01()()NnkNkx nXk WN*1*011()()()NnkNkx nXk WDFT XkNN101()()NnkNnx nX k WN共轭FFT共轭乘1/N()X k*()Xk()x n直接调用FFT子程序计算IFFT的方法：现在学习的是第56页，共61页快速傅里叶的应用l快速卷积l快速相关现在学习的是第57页，共61页FFTFFT序列相乘序列相乘IFFT()x n()h n()y n()(/2)次乘X k

24、NM次乘N(/2)次乘NM快速卷积现在学习的是第58页，共61页重叠相加法()h nN1N()x nMMMM11NN()ix n()iy n()y n1NMMMM1NM1NMmiimiimiinynhnxnhnxnhnxny000)()()()()()()()()()()(nhnxnyii现在学习的是第59页，共61页FFTFFT序列相乘序列相乘IFFT()x n()h n()y n()()X k H k()Hk共轭共轭()H k快速相关现在学习的是第60页，共61页3.4 与本章内容有关的MATLAB函数),(xhfftfilty)(xfftX),(NxfftX 现在学习的是第61页，共61页