数字信号处理数字信号处理 (6).pdf

《数字信号处理数字信号处理 (6).pdf》由会员分享，可在线阅读，更多相关《数字信号处理数字信号处理 (6).pdf（49页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、数字信号处理 参考书籍 高新波,阔永红,田春娜.数字信号处理.高等教育出版社,2014.史林,赵树杰.数字信号处理.科学出版社.2007.Alan V.Oppenheim,Ronald W.Schafer.Discrete-Time Signal Processing.电子工业出版社,2011.高西全,丁玉美.数字信号处理及其习题解答.西电出版社,2008.Vinay K.Ingle,John G.Proakis.Digital Signal Processing Using MATLAB.Northeastern University,1996.运算量运算量 复数乘法复数乘法 复数加法复数加

2、法 10()()NnkNnX kx n W()X k一个()NX k个(DFT)N点N2N1N(1)N N()()()()ajb cjdacbdj adcb实数乘法实数乘法 实数实数加法加法 一次复乘 4 2 一次复加 2 ()X k一个()NX k个4N22(1)2(21)NNN24N2(21)NN()()()()ajbcjdacj bd实数乘法实数乘法 实数实数加法加法 (DFT)N点 当N较大时，计算量太大，所以在快速傅里叶变换快速傅里叶变换(Fast Fourier Transform,FFT)出现以前，直接用DFT算法进行谱分析和信号的实时处理是不切实际的 直到1965年库利(J.W

3、.Cooley)和图基(J.W.Tukey)发表的“An algorithm for the machine calculation of complex Fourier series.Math.Comp.,Vol.19(April 1965),pp.297301”以后，研究人员相继改进了DFT快速算法，情况才发生了根本的改变 降低运算量的途径降低运算量的途径 把N点DFT分解为几个较短的DFT，可使乘法次数大大减少，另外，利用旋转因子WmN的周期性周期性、对称性对称性和可约性可约性来减少DFT的运算次数 利用这些性质提出：基2FFT、基4FFT、分裂基FFT、DHT等快速傅立叶变换算法 22

4、()jm lNjmm lNmNNNNWeeW2NmmN mN mmmNNNNNNWWWWWW/,/,/mm nNN nWWN n m n为整数周期性周期性 对称性对称性 可约性可约性 此外，此外，还有还有复合数快速傅里叶变换算法复合数快速傅里叶变换算法，使用于，使用于N为复合数的情况，即为复合数的情况，即N可表示为若干因子之乘积可表示为若干因子之乘积 基基2算法是这种方法的一个特例算法是这种方法的一个特例 如果序列的长度如果序列的长度N不是不是2M，且，且N又是素数，如果求又是素数，如果求准确的准确的N点点DFT，可用，可用线性调频线性调频Z变换变换(Chirp-Z变变换换)方法求方法求FFT

5、.012,LNr rr第五章 快速傅里叶变换(FFT)5.1 基2FFT算法 5.1.1 时域抽取基时域抽取基2FFT算法算法 5.1.2 频域抽取基频域抽取基2FFT算法算法 5.2 IDFT的快速算法 5.3 实序列的FFT算法 依次分解为短序列并结合旋转因子特性计算依次分解为短序列并结合旋转因子特性计算 基2时间抽取(Decimation in time)DIT-FFT 基2频率抽取(Decimation in frequency)DIF-FFT(2)()0,1,1(21)2xrNx nrxr (2)()0,1,1(21)2XmNX kmXm 奇偶分组奇偶分组 第五章 快速傅里叶变换(F

6、FT)5.1 基2FFT算法 5.1.1 时域抽取基时域抽取基2FFT算法算法 5.1.2 频域抽取基频域抽取基2FFT算法算法 5.2 IDFT的快速算法 5.3 实序列的FFT算法 1.算法原理算法原理 设序列点数 ，L为正整数。若不满足，则补零，使 N 为2的整数幂的FFT算法称为基-2 FFT算法 将序列 按n的奇偶分两组 2LN 12(2)()(2+1)()xrx rxrx r0,1,/2 1rN()x n5.1.1 时域抽取基2FFT算法 10()DFTNnkNnX kx nx n W旋转因子可约性旋转因子可约性 2 111210()()DFT()NkrNrXkx r Wx r2

7、122220()()DFT()NkrNrXkx r Wx r12(2)()(2+1)()xrx rxrx r0,1,/2 1rN2()222(2)2jkrkrNNjkrkrNNWeeW前前N/2点的点的DFT 2 12 12(21)00(2)(21)NNkrkrNNrrxr WxrW2 12 1221200()()NNkrkkrNNNrrx r WWx r W2 12 1122200()()NNkrkkrNNNrrx r WWx r W12()(),0,1,/2 1kNX kW XkkN()()knknNNn evenn oddx n Wx n W12()()()kNX kXkW Xk01kN

8、021kN？2NkN12(),()X kXk22()()2NXkXk(/2)12(/2)(/2)(/2)k NNX kNX kNWX kN又 后半个序列的求法如下：/2N12(/2)()()kNX kNX kW Xk0/2 1kN12()()()kNX kX kW Xk01kN021kN？2NkN利用周期性求 X(k)的后半部分 是以 为周期的 11()()2NX kX k/2k2NkNkNNNNWWWW 12()()()kNX kX kW Xk12(/2)()()kNX kNX kW Xk隐含周期性隐含周期性 旋转因子对称性旋转因子对称性 0/2 1kN蝶形蝶形单元需要单元需要 一次复数乘法

9、一次复数乘法 两次复数加法两次复数加法 12()()()kNX kX kW Xk12(/2)()()kNX kNX kW Xk0/21kN()x n(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)xN/2点点DFT N/2点点DFT 1(0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)X0NW1NW2NW3NW N点点DFT的一次时域抽取分解图的一次时域抽取分解图(N=8)N/2点DFTWN0N/2点DFTWN1WN2WN3x(0)X1(0)x(2)x(4)x(6)x(1)x(3)x(5)x

10、(7)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)12()()()kNX kX kW Xk12(/2)()()kNX kNX kW Xk0/2 1kN/2/2/4NNN仍为偶数，进一步分解：1314(2)()(21)()xlx lxlx l0,1,/4 1lN，k13/24k13/24()(k)()()()()4NNX kXWXkNX kXkWXk0,1,14Nk，331341()()(2)()()(21)XkDFT x lDFT xlXkDFT x lDFT xl0,1,/4 1lN，其中 同理 其中

11、25/2625/26()()W()()()W()4kNkNXkXkXkNXkXkXk0,1,14Nk，552662()()(2)()()(21)XkDFT x lDFT xlXkDFT x lDFT xl0,1,/4 1lN，二次分解二次分解 /4 1/4 12(21)11/21/200/4 1/4 13/4/24/4003/24()(2)(21)()()()(),0/41NNklklNNllNNklkklNNNllkNXkxl WxlWx l WWxl WXkWXkkN13/24()()(),0/4 1kNX kXkWXkkN13/24(/4)()(),0/4 1kNX kNXkWXkkN2

12、5/26()()(),0/4 1kNXkXkWXkkN25/26(/4)()(),0/4 1kNXkNXkWXkkN5.1.1 时域抽取基2FFT算法 31()(2),0/4 1x lxllN 41()(21),0/4 1x lxllN/4 133/430()()DFT()NklNlXkx l Wx l/4 144/440()()DFT()NklNlXkx l Wx l52()(2),0/4 1x lxllN 62()(21),0/4 1x lxllN/4 155/450()()DFT()NklNlXkx l Wx l/4 166/460()()DFT()NklNlXkx l Wx l(0)x

13、(4)x(2)x(6)xN/4点DFT3(0)x3(1)x4(0)x4(1)x(0)X(1)X(2)X(3)X(1)x(5)x(3)x(7)x5(0)x5(1)x6(0)x6(1)x(4)X(5)X(6)X(7)X0NW1NW2NW3NWN/4点DFTN/4点DFTN/4点DFT1(0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)X02NW12NW02NW12NWN点离散傅里叶变换的二次时域抽取运算流图(N8)N点离散傅里叶变换的三次时域抽取运算流图(N8)(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)x1(0)x2(0)x1(1)x2(1)x1(2)

14、x2(2)x1(3)x2(3)x()x n1()x n2()xn1(0)x1(2)x1(1)x1(3)x3(0)x3(1)x4(0)x4(1)x2(0)x2(2)x2(1)x2(3)x5(0)x5(1)x6(0)x6(1)x3()xn4()xn5()xn6()xn3(0)x3(1)x4(0)x4(1)x5(0)x5(1)x6(0)x6(1)x00(0)x01(0)x02(0)x03(0)x04(0)x05(0)x06(0)x07(0)xkNW2kNW4kNW00(0)X01(0)X02(0)X03(0)X04(0)X05(0)X06(0)X07(0)X3()Xk4()Xk5()Xk6()Xk1

15、()Xk2()Xk()X kN N个个1 1点点DFTDFT (0)x(1)x(4)x(5)x(2)x(3)x(6)x(7)xN点点DIT-FFT运算流图运算流图(N8)(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)x(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)X0NW1NW2NW3NW0NW2NW0NW2NW0NW0NW0NW0NW分析：分析：N点点DIT-FFT 包含包含 M级蝶形运算，每一级包含级蝶形运算，每一级包含N/2个碟形单元个碟形单元 一个蝶形单元需要一个蝶形单元需要 一次复数乘法，两次复数加法一次复数乘法，两次复数加法 2log22MNNCMN

16、A22log2NCMNN DIT-FFT与直接计算与直接计算DFTDFT运算量比较运算量比较 直接计算直接计算 需要需要N 2次复数乘次复数乘法法 N(N-1)次复次复数加法数加法 DIT-FFT 2log22MNNCMNA22log2NCMNN2222(/2)loglogNNRNNN复数乘法复数乘法 复数加法复数加法 复数乘法加速倍数复数乘法加速倍数 加速加速 MATLAB快速傅里叶变换调用格式快速傅里叶变换调用格式：Xk=fft(xn,N)N点离散傅里叶变换的三次时域抽取运算流图(N8)运算规律运算规律 1.1.原位计算原位计算：运算过程无需增加新的存储单元：运算过程无需增加新的存储单元

17、运算规律运算规律 2.2.旋转因子的变化规律和蝶形节点间距旋转因子的变化规律和蝶形节点间距 对对 N=2M 基基2DIT-FFT算法，各级蝶形算法，各级蝶形运算旋转运算旋转因子和蝶形节点间距为因子和蝶形节点间距为 第一级蝶形运算(L=1)旋转因子为 ，蝶形节点间距为1 第二级蝶形运算(L=2)旋转因子为 、，蝶形节点间距为2 第三级蝶形运算(L=3)旋转因子为 、，蝶形节点间距为4 第M 级蝶形运算(L=M)旋转因子为 、，蝶形节点间距为 N/2 0NW0NW4NNW8NNW0NW28NNW38NNW0NW1NW2NW(2 1)NNWDFTDFT 运算规律运算规律 3.3.输入序列的倒序输入序

18、列的倒序 自然序自然序 倒序倒序 输入序列的倒序输入序列的倒序 210()x n n n0101010001101121(0)x n n21(1)x n n2(00)x n2(10)x n2(01)x n2(11)x n(000)x(100)x(010)x(110)x(001)x(101)x(011)x(111)x0n1n2n二进制倒序树状图二进制倒序树状图(N8)第五章 快速傅里叶变换(FFT)5.1 基2FFT算法 5.1.1 时域抽取基时域抽取基2FFT算法算法 5.1.2 频域抽取基频域抽取基2FFT算法算法 5.2 IDFT的快速算法 5.3 实序列的FFT算法()x n2MNM为正

19、整数()nx n按序列号 的自然排序将前后对半分 10()DFTNnkNnX kx nx n W 2 1102+NNnknkNNnn Nx n Wx n W2 12 1(2)00()()2NNknk n NNNnnNx n Wx nW2 120()()2NkNknNNnNx nWx nW2221-1NjkkNNNjkWekevenekodd 2 1202 1202()()2()DFT=21()()2NrnNnNnrnNNnNXrx nx nWkevenX kx nNXrx nx nWWkodd 1x n 2xn5.1.2 频域抽取基2FFT算法 2 121102 122202DFT()DFT=

20、DFT21NrnNnNrnNnXrx n Wkevenx nX kx nxnXrxn Wkodd 1()()2Nx nx nx n 2()()2nNNxnx nx nW频域抽取基频域抽取基2FFT2FFT算法算法 时域抽取基时域抽取基2FFT2FFT算法算法 1Xk 2Xk x n(2)x nN 1()()2Nx nx nx n 2()()2nNNxnx nx nW()x n(0)x(4)x(1)x(5)x(2)x(6)x(3)x(7)xN/2点DFT N/2点DFT(0)X(2)X(4)X(6)X(1)X(3)X(5)X(7)X1(0)x1(1)x1(2)x1(3)x2(0)x2(1)x2(

21、2)x2(3)x0NW1NW2NW3NW 2 12 12112002 12 1222200221NNrnrnNNnnNNrnrnNNnnXrx n Wx n WXrxn Wxn WX1(n)的N/2点DFT X2(n)的N/2点DFT r=0,1,N/2-1 DFT DFT DFT DFT DFT DFT DFT DFT 3(0)x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)x1(0)x2(0)x1(1)x2(1)x1(2)x2(2)x1(3)x2(3)x()x n0NW1NW2NW3NW5(0)x3(1)x5(1)x4(0)x6(0)x4(1)x6(1)x02NW12NW0

22、2NW12NW04NW04NW04NW04NW00(0)x02(0)x03(0)x04(0)x05(0)x06(0)x07(0)x01(0)x 122()21XrXrkX kXrXrk偶数奇数00(0)X02(0)X03(0)X04(0)X05(0)X06(0)X07(0)X01(0)X3(0)X4(0)X4(1)X5(0)X5(1)X6(0)X7(1)X3(1)X1(0)X1(1)X1(3)X2(0)X2(2)X2(1)X2(3)X1(2)X(0)X(4)X(2)X(6)X(1)X(5)X(3)X(7)XN/4点DFTN/4点DFTN/4点DFTN/4点DFTx(0)x(1)x(2)x(3)

23、x(4)x(5)x(6)x(7)0NW1NW2NW3NWX(0)X(4)X(6)X(1)X(5)X(3)X(7)X(2)0NW0NW2NW2NW2NWx(0)x(1)x(2)x(3)x(5)x(6)x(7)x(4)2NW3NW1NW0NW0NW0NW2NW0NWX(0)X(4)X(2)X(6)X(1)X(5)X(3)X(7)0NW0NW0NW特点分析：特点分析：N N个个1 1点点DFTDFT MM级蝶形运算级蝶形运算 N/2N/2个碟算个碟算 每个蝶算每个蝶算2 2加加1 1乘乘 运算量：运算量：2log22MNNCMNA22log2NCMNN 运算规律运算规律 原位计算原位计算：运算过程无

24、需增加新的存储单元：运算过程无需增加新的存储单元 输入序列的倒序输入序列的倒序 旋转因子的变化规律和蝶形节点间距旋转因子的变化规律和蝶形节点间距 2NWx(0)x(1)x(2)x(3)x(5)x(6)x(7)x(4)2NW3NW1NW0NW0NW0NW2NW0NWX(0)X(4)X(2)X(6)X(1)X(5)X(3)X(7)0NW0NW0NW2NWx(0)x(1)x(2)x(3)x(5)x(6)x(7)x(4)2NW3NW1NW0NW0NW0NW2NW0NWX(0)X(4)X(2)X(6)X(1)X(5)X(3)X(7)0NW0NW0NW仔细观察基2DIF-FFT运算流图和基2DIT-FFT

25、运算流图会发现，将频域抽取法的运算流图反转，并将输入变输出，输出变输入，正好得到时域抽取法的运算流图 按频域抽取算法与按时域抽取算法是两种等价的FFT算法，此外，在基2FFT的基础上，还有变形基2FFT运算流图，原理类似 第五章 快速傅里叶变换(FFT)5.1 基2FFT算法 5.1.1 时域抽取基时域抽取基2FFT算法算法 5.1.2 频域抽取基频域抽取基2FFT算法算法 5.2 IDFT的快速算法 5.3 实序列的FFT算法 1010()()01/(011)NknNnNknNkX kx n Wx nX k WNkNDFTIDFTnN旋转因子指数变极性法旋转因子指数变极性法 直接调用直接调用

26、FFTFFT子程序法子程序法1 1 直接调用直接调用FFTFFT子程序法子程序法2 2 5.2 IDFT的快速算法 上述FFT算法流图也可以用于离散傅里叶逆变换(Inverse Discrete Fourier Transform，简称IDFT)。比较DFT和IDFT运算公式：比较上面两式,只要将DFT运算式中的旋转因子 变为 ,即旋转因子指数变极性,作为输入序列,并乘以系数1/N,就成为IDFT的运算公式 1010()()()1()()()NknNnNknNkX kDFT x nx n Wx nIDFT x nX k WNknNWknNW()X k11001()()()()()()NNknk

27、nNNnkX kDFT x nx n Wx nIDFT x nX k WN 所以,如果将基2DIT-FFT或基2DIF-FFT算法中的旋转因子 改为 ,把 作为输入序列,运算结果乘以1/N,就可以用来快速计算IDFT,得到输出序列 x(n)pNWpNW()X kknknNNWW旋转因子指数变极性法旋转因子指数变极性法 2NWX(0)X(1)X(2)X(3)X(5)X(6)X(7)X(4)2NW3NW1NW0NW0NW0NW2NW0NWNx(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)N1N1N1N10NWN0NWN0NWNX0)X(1)X(2)X(3)X(5)X(6)X(7)X

28、(4)121NWx(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)321NW221NW021NW212121212121212121212121021NW021NW021NW021NW021NW021NW221NW221NW频频 域域 抽抽 取取 时时 域域 抽抽 取取 直接调用直接调用FFTFFT子程序子程序法法 直接调用FFT子程序求IFFT,就是将X(k)或者X(k)的变体作为FFT程序的输入，所以我们需要求出x(n)与DFTX(k)的关系 直接调用直接调用FFTFFT子程子程序序 方方法法1 1 101()()01NknNkx nX k WnNN111()()01NknN

29、kx nXk WnNN1111()()DFT()01NknNkx nXk WXknNNN上式两边取共轭得 可用 fft 子程序实现DFT 符合X*(k)的DFT的定义式 因此，将X(k)取共轭后得X*(k)，输入FFT算出DFTX*(k)，对其取共轭，再乘以1/N得x(n)直接调用直接调用FFTFFT子程子程序序 方方法法2 2 10()()()NknNkDFg nX kT X kW11()00111()()()NNk N nkNknNNNkkg NnX k WX k WWNNN1()()01x ng NnnNNX(k)的DFT 01nN根据DFT的时域位移性质得 将X(k)作为FFT的输入，

30、求出g(n)，将g(n)进行移位得g(N-n)，再乘以1/N，得x(n)，即求出X(k)的逆变换 101()()01NknNkX k Wx nnNNx(n)的IDFT的定义式 第五章 快速傅里叶变换(FFT)5.1 基2FFT算法 5.1.1 时域抽取基时域抽取基2FFT算法算法 5.1.2 频域抽取基频域抽取基2FFT算法算法 5.1.3 其他快速算法简介其他快速算法简介 5.2 IDFT的快速算法 5.3 实序列的FFT算法 三种情况：把实序列x(n)看作虚部为零的复序列，直接调用fft；对两个N点的实序列x(n)和h(n)，构成复序列y(n)，即()()(),0,1,1y nx njh

31、n nN对y(n)进行N点FFT，输出Y(k)，则*1()()()()()2,0,1,11()()()()()2epopX kDFT x nYkY kYNkkNH kDFT h njYkY kYNkj 运算时间略多于一个N点FFT，可获得两个N点实序列的FFT 时间浪费 设x(n)为N点实序列，取x(n)的偶数点和奇数点分别作为新构造序列y(n)的实部和虚部，即 1212()(2),()(21),0,1,/21()()(),0,1,/21x nxnx nxnnNy nx njx n nN对y(n)进行N/2点FFT，输出Y(k)，则 1122()()(),0,1,1()()()2epopXkDFT x nYkNkXkDFT xnjYk 根据DIT-FFT的思想及下式，可得到 12()()(),0,1,/2 1kNX kX kW XkkN2221(1)42NMMNNMM运算效率（复乘）：原蝶形/现在 由于x(n)为实序列，所以X(k)具有共轭对称性，X(k)另外N/2点的值为 ()(),1,2,/2 1X NkXk kN 运算速度提高近一倍运算速度提高近一倍