數(shù)字信號處理第三章離散傅里葉變換ppt課件

1、第三章第三章 離散傅里葉變換離散傅里葉變換(DFT)(DFT)及其快速算法及其快速算法(FFT)(FFT) 3.1 離散傅里葉變換的定義及物理意義 3.2 DFT的主要性質 3.3 頻域采樣 3.5 DFT(FFT)應用舉例 3.4 DFT的快速算法快速傅里葉變換(FFT) 傅 里 葉 變 換 ： 建 立 以 時 間t 為 自 變 量 的 “ 信 號 ” 與 以 頻 率 f為 自 變 量 的 “ 頻 率 函 數(shù) ”(頻譜) 之 間 的 某 種 變 換 關 系 . 所 以 “ 時 間 ” 或 “ 頻 率 ” 取 連 續(xù) 還 是 離 散 值 , 就 形 成 各 種 不 同 形 式 的 傅 里 葉

2、變 換 對 。 傅里葉變換的幾種形式傅里葉變換的幾種形式3.1 3.1 離散傅里葉變換的定義及物理意義離散傅里葉變換的定義及物理意義 模擬域 FT、LT 數(shù)字域 FT、ZT 數(shù)字域 DFT返回返回DFT 的圖形解釋的圖形解釋Z變換、 DTFT、DFT 的取值范圍四種傅立葉變換四種傅立葉變換 離散傅立葉變換DFT實現(xiàn)了信號首次在頻域表示的離散化，使得頻域也能夠用計算機進行處理。并且這種DFT變換可以有多種實用的快速算法。使信號處理在時、頻域的處理和轉換均可離散化和快速化。因而具有重要的理論意義和應用價值，是本課程學習的一大重點。 本節(jié)主要介紹返回返回p 3.1.1 DFT定義p 3.1.2 DF

3、T與ZT、FT、DFS的關系p 3.1.3 DFT的矩陣表示3.1.1 DFT3.1.1 DFT定義定義設序列x(n)長度為M，定義x(n)的N點DFT為式中，N稱為離散傅里葉變換區(qū)間長度，要求N M。為書寫簡單，令 ，因此通常將N點DFT表示為定義X(k)的N點離散傅里葉逆變換(IDFT)為 21j0( )DFT ( )( )e, 0, 1, , 1Nk nNNnX kx nx nkN 10( )DFT ( )( ), 0, 1, , 1Nk nNNnX kx nx n WkN2jeNNW 101( )IDFT( )( ), 0, 1, , 1Nk nNNkx nX kX k WnNN長度為

4、N的離散序列返回返回回到本節(jié)回到本節(jié)例3.1： ，分別計算x(n)的8點、16點DFT。解: x(n)的8點DFT為 x(n)的16點DFT為8( )( )x nR n 277j888008, 0( )( )e0,1, 2, 3, 4, 5, 6, 7k nk nnnkX kR n Wk 2j8781616162j1601611e( )11ekkk nkknWX kWW7j16sin2e , 0,1,2,15sin16kkkk返回返回回到本節(jié)回到本節(jié) 是是 在頻率區(qū)間上的等間隔采樣在頻率區(qū)間上的等間隔采樣( )X k()jX e返回返回回到本節(jié)回到本節(jié)3.1.2 DFT3.1.2 DFT與與Z

5、TZT、FTFT、DFSDFS的關系的關系 DFT有明確的物理意義，我們可以通過比較序列的DFT、FT、ZT，并將DFT與周期序列的DFS聯(lián)系起來，得到DFT的物理意義。 DFT和FT、ZT之間的關系 假設序列的長度為M，NM將N點DFT和FT、ZT的定義重寫如下 101jj010( )ZT ( )( )(e)FT ( )( )e( )DFT ( )( ), 0,1,1MnnMnnMknNNnX zx nx n zXx nx nX kx nx n WkN返回返回回到本節(jié)回到本節(jié)比較前面三式，得到 ，k=0, 1, 2, , N-1 ，k=0, 1, 2, , N-1 結論：(1)序列的N點DF

6、T是序列傅里葉變換在頻率區(qū)間0，2上的N點等間隔采樣，采樣間隔為2 /N。 (2)序列的N點DFT是序列的Z變換在單位圓上的N點等間隔采樣，頻率采樣間隔為2 /N。 2je( )( )kNzX kX zj2( )(e)kNX kX返回返回回到本節(jié)回到本節(jié) DFT與z變換2X(ej)X(k)ok1N00 ImjZ Re Z1234567(N-1)2Nk=0 DFT與DTFT變換 序列序列x(n)的的N點點DFT是是 x(n)的的Z變換在單位圓上的變換在單位圓上的N點等點等間隔采樣；間隔采樣； X(k)為為x(n)的傅立葉變換的傅立葉變換 在區(qū)間在區(qū)間 上的上的N點等間隔采樣。這就是點等間隔采樣。

7、這就是DFT的物理意義。的物理意義。0, 2 ()jX e變量周期分辨率2N2f、ssf、NfskN返回返回回到本節(jié)回到本節(jié)DFTDFT和和DFSDFS之間的關系：之間的關系： 周期延拓周期延拓 取主值取主值 有限長序列有限長序列 周期序列周期序列 主值區(qū)序列主值區(qū)序列有限長序列有限長序列周期序列周期序列主值區(qū)間序列主值區(qū)間序列( )0,1, 2,1x nnM()()Nmxnxnm N 0001nNnmNn0( )Nnn( )( )( )NNNxnxn Rn ,( )( )NNMxnx n( )Nx n返回返回回到本節(jié)回到本節(jié)8( )x n4( )x n返回返回回到本節(jié)回到本節(jié)周期序列DFS:

8、有限長序列的DFT:對比二者發(fā)現(xiàn)： 是 的主值區(qū)序列，條件NM1010()()()()NknNNNnMknNnXkD F Sxnxn Wxkn W 1010( )0( )( )1)NknNnMknnX kDFT x nx n WNx n Wk( )X k( )X k( )()( )( )( )NmX kX kmNX kX k Rk返回返回回到本節(jié)回到本節(jié)( )NxnnN0N2N( )X k02NNkN01N 0nk)(nx)(kXDFSDFT2N返回返回回到本節(jié)回到本節(jié)DFTDFT與與DFSDFS之間的關系之間的關系: :有限長序列x(n)的DFT變換X(k)，就是x(n)的周期延拓序列 的D

9、FS系數(shù)的主值序列()()()()()()()()()()NNNNNx nx n RnxnxnXkXkRkXkXkNM:()():()()D F Tx nXkD F Sx nXk)(nx)(kX返回返回回到本節(jié)回到本節(jié)DFSDFS與與FTFT之間的關系之間的關系: : 周期延拓序列 的頻譜特性由其傅里葉級數(shù)的 系數(shù) 確定，幅度相差一個常數(shù)因子 。 DFT的 是 的主值區(qū)序列，所以x(n)的 DFT表示的是 周期序列的頻譜特性。10( )( )( )MknNNnX kDFS xnx n Wk22()( )( ) ()jNkX eFT xnX kkNN ( )X k( )X k2N( )X k)(

10、nx)(nx返回返回回到本節(jié)回到本節(jié)3.1.3 DFT3.1.3 DFT的矩陣表示的矩陣表示周期序列 的DFS以及有限長序列x(n)的DFT如下可以發(fā)現(xiàn)它們右邊的函數(shù)形式一樣，但k的定義域不同，X(k)只是 的主值區(qū)序列，或者說X(k)以N為周期進行周期延拓即是 ，用后面兩式表示二者的關系： ( )Nxn 101010( )DFS( )( )( ) ( )DFT ( )( ), 0, 1, , 1Mk nNNNnMk nNnMk nNNnX kxnxn Wx n WkX kx nx n WkN -( )X k( )X k返回返回回到本節(jié)回到本節(jié)式(3.1.5)(3.1.8)說明了DFT和DFS

11、之間的關系。這些關系式成立的條件是N M，即DFT的變換區(qū)間N不能小于x(n)的長度M。如果該條件不滿足，按照式(3.1.5)將x(n)進行延拓時， 中將發(fā)生時域混疊，由式(3.1.8)得到的X(k)不再是x(n)的DFT，這時以上講的DFS和DFT之間的關系不再成立。 ( )()mX kX kmN( )( )( )NX kX k Rk(3.1.7)(3.1.8)( )Nxn返回返回回到本節(jié)回到本節(jié)也可以表示成矩陣形式式中，X是N點DFT頻域序列向量:x是時域序列向量:DN稱為N點DFT矩陣，定義為 10( )DFT ( )( ), 0, 1, , 1Nk nNNnX kx nx n WkNN

12、XD xT(0) (1) (2) (1)XXX NX NXT (0) (1) (2) (1)xxx Nx Nx121242(1)12(1)(1)(1)1111111NNNNNNNNNNNNNNNNWWWWWWWWWD(3.1.12)返回返回回到本節(jié)回到本節(jié)也可以表示為矩陣形式: 稱為N點IDFT矩陣，定義為從式(3.1.12)和式(3.1.14)，我們可以發(fā)現(xiàn) 101( )IDFT( )( ), 0, 1, , 1Nk nNNkx nX kX k WnNN1NxD X1ND12(1)1242(1)(1)2(1)(1)(1)11111111NNNNNNNNNNNNNNNNWWWWWWNWWWD(

13、3.1.14)1*1NNNDD返回返回回到本節(jié)回到本節(jié)3.2 DFT3.2 DFT的主要性質的主要性質與序列的FT類似，DFT也有許多重要的性質。其中一些性質本質上與FT的相應性質相同，但是某些其他性質稍微有些差別。返回返回p 線性性質 p DFT的隱含周期性 p 循環(huán)移位性質 p 復共軛序列的DFT p DFT的共軛對稱性 p 循環(huán)卷積定理循環(huán)卷積定理p 離散巴塞伐爾定理離散巴塞伐爾定理 線性性質線性性質 設有限長序列設有限長序列 的長度分別為的長度分別為 ， ，a a和和b b為常數(shù)。為常數(shù)。那么那么式中式中 ， 。12( )( )x nxn和12NN和12( )( )( )x nax n

14、bxn12( )( )( ) , 0, 1, 2, , 1X kaXkbXkkN12 max, NNN11( )DFT( ) ,NXkx n22( )DFT( )NXkx n返回返回回到本節(jié)回到本節(jié)0, 2 DFTDFT的隱含周期性的隱含周期性 在第一節(jié)中，在第一節(jié)中，DFTDFT和和IDFTIDFT只定義了只定義了X(k)X(k)和和x(n)x(n)在變換區(qū)在變換區(qū)間上間上 的的N N個值。如果使個值。如果使DFTDFT中中k k的取值域為的取值域為-，就會發(fā)，就會發(fā)現(xiàn)現(xiàn) X(k)X(k)是以是以N N為周期的，即為周期的，即 X(k + mN) = X(k) X(k + mN) = X(k

15、) 稱稱X(k)X(k)的這一特性為的這一特性為DFTDFT的隱含周期性。的隱含周期性。 物理意義：物理意義：X(k)X(k)為為 在區(qū)間在區(qū)間 上的上的N N點等間隔采點等間隔采樣。樣。 以以22為周期，為周期，X(k)X(k)以以N N為周期。為周期。()jX e()jX e返回返回回到本節(jié)回到本節(jié)循環(huán)移位性質循環(huán)移位性質 有限長序列的循環(huán)移位有限長序列的循環(huán)移位 設序列設序列x(n)x(n)的長度為的長度為M M，對，對x(n)x(n)以以N NN MN M為周期進為周期進行周行周期延拓，得到期延拓，得到定義定義x(n)x(n)的循環(huán)移位序列為的循環(huán)移位序列為上式表示將序列上式表示將序列

16、x(n)x(n)以以N N為周期進行周期延拓，再左移為周期進行周期延拓，再左移m m個個單位并取主值序列，單位并取主值序列， 就得到就得到x(n)x(n)的循環(huán)移位序列的循環(huán)移位序列y(n)y(n)。下圖中下圖中(a)(a)、(b)(b)、(c)(c)和和(d)(d)分別描述了分別描述了x(n)x(n)、 、 和和y(n)y(n)。圖中。圖中M=6M=6，N=8N=8，m=2m=2。 ( )( )NNxnx n( )()( )()( )NNNNy nxnm Rnx nmRn( )Nxn()Nxnm返回返回回到本節(jié)回到本節(jié)序列的循環(huán)移位過程示意圖返回返回回到本節(jié)回到本節(jié) 循環(huán)移位性質 設序列x(

17、n)長度為M，x(n)的循環(huán)移位序列為 ， N M那么 復共軛序列的DFT 假設用 表示x(n)的復共軛序列，長度為N，且 ，那么 ， k=0,1,2,N-1 式中， 。同樣：( )()( )NNy nx nmRn ( )DFT ( )( )k mNNY ky nWX k( )x n( )DFT ( )NX kx nDFT( )()x nXNk()(0)X NX()()ND F TxNnXk返回返回回到本節(jié)回到本節(jié)DFTDFT的共軛對稱性的共軛對稱性上一章介紹了序列上一章介紹了序列FTFT的共軛對稱性，的共軛對稱性，DFTDFT也有類似的共也有類似的共軛軛對稱性質。但對稱性質。但FTFT中的共

18、軛對稱是指對坐標原點的共軛對中的共軛對稱是指對坐標原點的共軛對稱，在稱，在DFTDFT中指的是對變換區(qū)間的中心，即中指的是對變換區(qū)間的中心，即N/2N/2點的共軛點的共軛對對稱。稱。 有限長共軛對稱序列和共軛反對稱序列有限長共軛對稱序列和共軛反對稱序列 假設有限長序列假設有限長序列 滿足下式滿足下式 ， n=0,1,2, n=0,1,2,N-1 ,N-1 則稱則稱 為共軛對稱序列。為共軛對稱序列。 假設有限長序列假設有限長序列 滿足下式滿足下式 ， n=0,1,2, n=0,1,2,N-1 ,N-1 則稱其為共軛反對稱序列。則稱其為共軛反對稱序列。 ep( )xn*epep( )()xnxNn

19、ep( )xnop( )xn*opop( )() xnxNn 返回返回回到本節(jié)回到本節(jié)任一有限長序列x(n)都可以用它的共軛對稱分量和共軛反對稱分量之和表示，即將上式中的n用N-n代替，并兩邊取共軛，得到 由上面兩式得到 和 與原序列x(n)的關系為 epop( )( )( )x nxnxn*epopepop()()()( )( )xNnxNnxNnxnxnep( )xnop( )xn*ep1( ) ( )()2xnx nxNn*op1( ) ( )()2xnx nxNn返回返回回到本節(jié)回到本節(jié) DFT的共軛對稱性質假設序列x(n)長度為N，其N點DFT用X(k)表示。 將序列x(n)分成實部

20、和虛部，相應x(n)的DFT分成共軛對稱和共軛反對稱兩部分。即式中， ，那么 riepop( )( )j ( )( )( )( )x nx nx nX kXkXkri( )Re ( )( )Im ( )x nx nx nx n，epr( )DFT( )NXkx nopi( )DFTj ( )NXkx n返回返回回到本節(jié)回到本節(jié) 將序列x(n)分成共軛對稱和共軛反對稱兩部分，相應x(n)的DFT分成實部和虛部兩部分，即式中， ， ，那么epopri( )( )( )( )( )j( )x nxnxnX kXkX kr( ) Re( )XkX k=i( )Im( )X kX krep( )DFT(

21、 )NXkxniopj( )DFT( )NX kxn返回返回回到本節(jié)回到本節(jié) 實信號DFT的特點設x(n)是長度為N的實序列，其N點DFT用X(k)表示，我們從的結論可知道X(k)具有共軛對稱性質，即如果將X(k)寫成極坐標形式 ，由共軛對稱性質，說明X(k)的模關于 k = N/2點偶對稱 ，利用DFT的共軛對稱性質可以減小實序列的DFT計算量：a) 利用計算一個復序列的N點DFT，很容易求得兩個不同 的實序列的N點DFT；b) 實序列的2N點DFT，可以用復序列的N點DFT得到。 ( )()X kXNkj ( )( )( ) ekX kX k( )() X kX Nk( )()kNk 返回

22、返回回到本節(jié)回到本節(jié)a) 設 是實序列，長度均為N，用它們構成一個復序列 對上式進行N點DFT，得到利用的結論可以得到這樣只計算一個N點DFT，得到X(k)，用上面兩式容易得到兩個實序列的N點DFT。 12( )( )x nx n和12( )( )j( )x nx nx nepop( )DFT ( )( )( )X kx nXkXk*11ep1( )DFT( )( )( )()2NX kx nXkX kXNk*22op1( )DFT( )j( ) ( )()2jNXkx nXkX kXNk (3.2.18)(3.2.19)返回返回回到本節(jié)回到本節(jié)b) 通過復序列的N點DFT得到實序列的2N點D

23、FT。設 是一個長度為2N的實序列，首先分別用 中的偶數(shù)點和奇數(shù)點形成兩個長度為N的新序列 ，即 再由 構造長度為N的復序列x(n)，即計算x(n)的N點DFT，因為 均是實序列，利用式(3.2.18)和式(3.2.19)得到 。最后由 以得到實序列v(n)的2N點DFT，即V(k)。 ( )v n12( )( )x nx n和( )v n1( )(2 )x nvn2( )(21)x nvn01nN 01nN 12( )( )x nx n和12( )( )j( )x nx nx n01nN 12( )( )x nx n和12( )( )X kXk和12( )( )X kXk和返回返回回到本節(jié)回

24、到本節(jié)實序列實序列2N2N點的點的DFTDFT，拆分重組為，拆分重組為N N點復序列點復序列DFTDFT例如例如 是實序列，長度為是實序列，長度為2N2N拆分拆分重組重組N N點點DFTDFT( )v n12( )(2 )( )(21)01x nvnx nvnnN12( )( )( )01x nx njx nnN21112(21)222000( )( )(2 )(21)NNNknk nknNNNnnnV kv n Wvn WvnW122( )( )kNXkWXk1112200( )( )NNknkknNNNnnx n WWxn W122( )( )021kNNNXkWXkkN返回返回回到本節(jié)回

25、到本節(jié)循環(huán)卷積定理循環(huán)卷積定理時域循環(huán)卷積定理是時域循環(huán)卷積定理是DFTDFT中很重要的定理，具有很強的中很重要的定理，具有很強的實用實用性。已知系統(tǒng)輸入和系統(tǒng)的單位脈沖響應，計算系統(tǒng)的性。已知系統(tǒng)輸入和系統(tǒng)的單位脈沖響應，計算系統(tǒng)的輸輸出，以及出，以及FIRFIR濾波器用濾波器用FFTFFT實現(xiàn)等，都是該定理的重要應實現(xiàn)等，都是該定理的重要應用。用。1. 1. 兩個有限長序列的循環(huán)卷積兩個有限長序列的循環(huán)卷積 設序列設序列h(n)h(n)和和x(n)x(n)的長度分別為的長度分別為N N和和M M。h(n)h(n)與與x(n)x(n)的的L L點循點循環(huán)卷積定義為環(huán)卷積定義為式中，式中，L

26、L稱為循環(huán)卷積的長度，稱為循環(huán)卷積的長度，LmaxNLmaxN，MM。 為了區(qū)別線性卷積，用為了區(qū)別線性卷積，用 表示循環(huán)卷積，用表示循環(huán)卷積，用 表示表示L L點循點循環(huán)卷積，即環(huán)卷積，即 x(n) x(n)。 1c0( )( ) ()( )LLLmy nh m x nmRnc( )( )y nh nLL返回返回回到本節(jié)回到本節(jié)有限長序列循環(huán)卷積的矩陣形式上式中右邊第一個矩陣稱為x(n)的L點循環(huán)矩陣，它的特點是：(a)第一行是x(n)的L點循環(huán)倒相。x(0)不動，后面其它反轉180放在他的后面。(b)第二行是第一行向右循環(huán)移一位；(c)第三行是第二行向右循環(huán)移一位；依次類推。) 1()2(

27、) 1 ()0()0() 3()2() 1() 3()0() 1 ()2()2() 1()0() 1 () 1 ()2() 1()0() 1()2() 1 ()0(LhhhhxLxLxLxxxxxxLxxxxLxLxxLyyyycccc返回返回回到本節(jié)回到本節(jié)例3.2： 計算下面給出的兩個長度為4的序列h(n)與x(n)的4點和8點循環(huán)卷積。解: 按照式(3.2.21)寫出h(n)與x(n)的4點循環(huán)卷積矩陣形式為 ( )(0), (1), (2), (3)1,2,0,1( )(0), (1), (2), (3)2,2,1,1h nhhhhx nxxxxc( )( )y nh n( )x nc

28、ccc(0)211216(1)221127(2)122106(3)112215yyyy 返回返回回到本節(jié)回到本節(jié)h(n)與x(n)的8點循環(huán)卷積矩陣形式為 c( )( )y nh n( )x ncccccccc(0)1220000112(1)2622000011(2)0512200001(3)15112200000401122000(4)0011220001(5)00011220(6)0100001122(7)00yyyyyyyy 返回返回回到本節(jié)回到本節(jié)2. DFT的時域循環(huán)卷積定理 設h(n)和x(n)長度分別為N和M，yc(n)為序列h(n)和x(n)的L點循環(huán)卷積，即 x(n) 那么

29、式中時域循環(huán)卷積定理表明，DFT將時域循環(huán)卷積關系，變換成頻域的相乘關系。用時域循環(huán)卷積定理計算兩個序列循環(huán)卷積運算的方框圖如下圖所示 c( )( )y nh ncc( )DFT( )( )( ), 0,1,2,1LY ky nH k X kkL( )DFT ( ) , ( )DFT ( )LLH kh nX kx n圖3.2.3 用DFT計算兩個有限長序列L點循環(huán)卷積運算的方框圖 L返回返回回到本節(jié)回到本節(jié)3. DFT的頻域循環(huán)卷積定理設h(n)和x(n)長度分別為N和M，并且 ，那么 式中，LmaxN, M。DFT： 時域循環(huán)卷積 頻域乘積離散巴塞伐爾定理 設長度為N的序列x(n)的N點D

30、FT為X(k)，那么 ( )( ) ( )mynh n x n( )DFT ( ) , ( )DFT ( )LLH kh nX kx n1( )DFT( )( )mmLYkynH kL( )X k101 ( )()( )LLLjH j XkjRkL1122001( )( )NNnkx nX kNL返回返回回到本節(jié)回到本節(jié)3.3 3.3 頻域采樣頻域采樣時域和頻域的對偶原理時域和頻域的對偶原理 對時間序列對時間序列x(n)x(n)的連續(xù)頻譜的連續(xù)頻譜函數(shù)在頻域等間隔采樣，則采樣得到的離散頻譜對應的時函數(shù)在頻域等間隔采樣，則采樣得到的離散頻譜對應的時域域序列必然是原時間序列序列必然是原時間序列x(

31、n)x(n)的周期延拓序列。的周期延拓序列。 而且僅對時域有限長序列，當滿足頻域采用定理時，而且僅對時域有限長序列，當滿足頻域采用定理時，才才能由頻域離散采樣恢復原來的連續(xù)頻譜函數(shù)或原時間序能由頻域離散采樣恢復原來的連續(xù)頻譜函數(shù)或原時間序列）。列）。 時域采樣時域采樣 頻域周期延拓頻域周期延拓 時域周期延拓時域周期延拓 頻域采樣頻域采樣本節(jié)討論：頻域采樣定理、頻率采樣條件、頻域內插公式本節(jié)討論：頻域采樣定理、頻率采樣條件、頻域內插公式。 返回返回頻域采樣與頻域采樣定理頻域采樣與頻域采樣定理設任意序列設任意序列x(n)x(n)的的Z Z變換為變換為而且而且X(z)X(z)的收斂域包含單位圓。以的

32、收斂域包含單位圓。以2 2/N/N為采樣間隔，為采樣間隔，在單在單位圓上對位圓上對X(z)X(z)進行等間隔采樣得到進行等間隔采樣得到 實質上，實質上， 是對是對x(n)x(n)的頻譜函數(shù)的頻譜函數(shù) 的等間隔采樣的等間隔采樣。因。因為為 以以2 2為周期，所以為周期，所以 是以是以N N為周期的頻域為周期的頻域序列。序列。 ( )( )nnX zx n z 2j21je0( )( )( )ekNNk nNNznXkX zx n( )NXk( )NXkj(e)Xj(e)X返回返回回到本節(jié)回到本節(jié)根據(jù)離散傅里葉級數(shù)理論， 必然是一個周期序列的DFS系數(shù)。經(jīng)推導，我們能夠得到上式說明頻域采樣 所對應

33、 的時域周期序列是原序列x(n)的周期延拓序列，延拓周期為N。根據(jù)DFT與DFS之間的關系知道，分別截取 和 的主值序列 那么 和 構成一對DFT ( )NXk( )Nxn ( )IDFS( )()NNixnXkx niN( )NXk( )Nxn( )Nxn( )NXk ( )( )( )()( ) NNNNixnxn Rnx niN Rn2j e( )( )( )( ),0,1,2,1kNNNNzXkXk RkX zkN( )Nxn( )NXk( )DFT( )NNNXkxn( )IDFT( )NNNxnXk(3.3.3)(3.3.4)(3.3.5)(3.3.6)返回返回回到本節(jié)回到本節(jié)(3

34、.3.3)式表明 是對X(z)在單位圓上的N點等間隔采樣，即對 在頻率區(qū)間0，2上的N點等間隔采樣。(3.3.3)式(3.3.6)式說明， 對應的時域有限長序列 就是原序列x(n)以N為周期的周期延拓序列的主值序列。綜上所述，可以總結出頻域采樣定理:如果原序列x(n)長度為M，對 在頻率區(qū)間0，2上等間隔采樣N點，得到 ，則僅當采樣點數(shù)NM時，才能由頻域采樣 恢復 ，否則將產(chǎn)生時域混疊失真，不能由 恢復原序列x(n)。定理告誡我們，只有當時域序列x(n)為有限長時，以適當?shù)牟蓸娱g隔對其頻譜函數(shù) 采樣，才不會丟失信息。j(e)X( )NXk( )NXk( )Nxn( )IDFT( )NNx nX

35、kj(e)X( )NXk( )NXk( )NXkj(e)X返回返回回到本節(jié)回到本節(jié)返回返回回到本節(jié)回到本節(jié)2. 2. 頻域內插公式頻域內插公式 所謂頻域內插公式，就是用頻域采樣所謂頻域內插公式，就是用頻域采樣 表示表示X(z)X(z)和和 。頻域內插公式是頻域內插公式是FIRFIR數(shù)字濾波器的頻率采樣結構和頻率采樣數(shù)字濾波器的頻率采樣結構和頻率采樣設計法的理論依據(jù)。設計法的理論依據(jù)。設序列設序列x(n)x(n)的長度為的長度為M M，在，在Z Z平面單位圓上對平面單位圓上對X(z)X(z)的采樣點數(shù)的采樣點數(shù)為為N N，且滿足頻域采樣定理，且滿足頻域采樣定理NMNM）。則有）。則有 ( )X

36、kj(e)X10( )( )NnnX zx n z2j, e( )( )0,1,2, ,1kNzX kX zkN 101( )IDFS ( )( ), 0,1,2,1NknNNkx nX kX k WnNN(3.3.7)(3.3.8)返回返回回到本節(jié)回到本節(jié)將式(3.3.8)代入式(3.3.7)得到式中， 。令那么 11111000011( )( ) ( )()NNNNk nnknNNnkknX zX k WzX kWzNN 11011( )1Nk NNNkNkWzX kNWz 1k NNW1101( )( )1NNkNkzX kX zNWz111( )1NkkNzzNWz10( )( )(

37、)NkkX zX kz(3.3.9a)(3.3.9b)(3.3.11)所以返回返回回到本節(jié)回到本節(jié)式(3.3.9a)和式(3.3.11)稱為用 表示X(z)的z域內插公式。 稱為z域內插函數(shù)。將 帶入(c)式并化簡，得到用 表示 的內插公式和內插函數(shù) :式(3.3.12)和式(3.3.13)將用于FIR數(shù)字濾波器的頻率采樣設計法的誤差分析。 ( )X k( )kzjez( ) j(e)X( )X k1j02(e)( )NkXX kkN j1 /21 sin(/2)( )esin(/2)NNN (3.3.12)(3.3.13)返回返回回到本節(jié)回到本節(jié)102 ()( ) ()NjkX eX kkN

38、 內插公式：212 ()20kikNkNiikN l保證了各采樣點上保證了各采樣點上的值與原序列的頻的值與原序列的頻譜相同；譜相同；l采樣點之間為采樣采樣點之間為采樣值與對應點的內插值與對應點的內插公式相乘，并疊加公式相乘，并疊加而成。而成。返回返回回到本節(jié)回到本節(jié)3.4 DFT3.4 DFT的快速算法的快速算法快速傅里葉快速傅里葉變換變換(FFT)(FFT)l DFT使計算機在頻域處理信號成為可能，但是當N很大時，直接計算N點DFT的計算量非常大。l 快速傅里葉變換FFT，F(xiàn)ast Fourier Transform可使實現(xiàn)DFT的運算量下降幾個數(shù)量級，從而使數(shù)字信號處理的速度大大提高，工程

39、應用成為可能。l 人們已經(jīng)研究出多種FFT算法，它們的復雜度和運算效率各不相同。l 本章主要介紹最基本的基2 FFT算法及其編程方法。 返回返回3.4.1 3.4.1 直接計算直接計算DFTDFT的特點及減少運算量的的特點及減少運算量的基本途徑基本途徑DFTDFT計算量：計算量： 長度為長度為NN的序列的序列x(n)x(n)的的NN點點DFTDFT為為 計算計算X(k)X(k)的每一個值需要計算的每一個值需要計算NN次復數(shù)乘法和次復數(shù)乘法和N-1N-1次復次復數(shù)數(shù)加法，那么計算加法，那么計算X(k)X(k)的的NN個值需要個值需要N2N2次復數(shù)乘法和次復數(shù)乘法和(N-(N-1)1)NN次復數(shù)加

40、法運算。當次復數(shù)加法運算。當N1N1時，時，NN點點DFTDFT的復數(shù)乘法和復的復數(shù)乘法和復數(shù)加數(shù)加法運算次數(shù)均與法運算次數(shù)均與N2N2成正比。成正比。 ( )DET ( )NX kx n 10( ) 0, 1, , 1Nk nNnx n WkN返回返回回到本節(jié)回到本節(jié)減少運算量方法：減少運算量方法：長序列分為短序列：長序列分為短序列： 由于由于N點點DFT的運算量隨的運算量隨N2增長，因而，當增長，因而，當N較大時，較大時， 減少運算量的途徑之一就是將減少運算量的途徑之一就是將N點點DFT分解為幾個較分解為幾個較 短的短的DFT進行計算，則可大大減少其運算量。進行計算，則可大大減少其運算量。

41、旋轉因子的周期性和對稱性：旋轉因子的周期性和對稱性： 的周期性：的周期性： 的對稱性：的對稱性：mNW 22j()jeem l Nmm l NmNNNNWW*()N mmNNWWmNW2NmmNNWW 返回返回回到本節(jié)回到本節(jié)快速傅里葉變換就是不斷地將長序列的DFT分解為短序列的DFT，并利用 的周期性和對稱性及其一些特殊值來減少DFT運算量的快速算法。 時間域抽?。侯l率域抽?。?2 )( )0,1,1(21)2xrNx nrxrmNW 基基2時間抽取時間抽取(Decimation in time)DIT-FFT算法算法基基2頻率抽取頻率抽取(Decimation in frequency)D

42、IF-FFT算法算法(2 )( )0,1,1(21)2XmNX kmXm返回返回回到本節(jié)回到本節(jié)3.4.2 3.4.2 基基2 DIT-FFT 2 DIT-FFT 算法算法 基基2FFT2FFT要求要求DFTDFT變換區(qū)間長度變換區(qū)間長度N=2MN=2M，M M為自然數(shù)。為自然數(shù)。 DIT-FFTDIT-FFT算法算法 序列序列x(n)x(n)的的N N點點DFTDFT為為 將上面的和式按將上面的和式按n n的奇偶性分解為的奇偶性分解為 10( )DET ( )( ) 0,1,1NknNNnX kx nx nWkN /2 1/2 12(21)00( )( )( )(2 )(21)k nk nN

43、NnnNNk lklNNllX kx n Wx n Wxl WxlW返回返回回到本節(jié)回到本節(jié)令x1(l)=x(2l),x2(l)=x(2l+1)，因為 ，所以上式可寫成上式說明，按n的奇偶性將x(n)分解為兩個N/2長的序列x1(l)和x2(l)，則N點DFT可分解為兩個N/2點DFT來計算。用X1(k)和X2(k)分別表示x1(l)和x2(l)的N/2點DFT，即 2/2k lk lNNWW 21/2 11/22/200( )( )( ) 0,1,1MNklkklNNNllX kx l WWx l WkN /2 111/21/20( )DFT ( )( ) 0,1,12Nk lNNlNX k

44、x lx l Wk(3.4.4)(3.4.5)返回返回回到本節(jié)回到本節(jié)將式(3.4.5)和式(3.4.6)代入式(3.4.4)，并利用X1(k)、X2(k)的隱含周期性可得到 這樣，就將N點DFT的計算分解為計算兩個N/2點離散傅里葉變換X1(k)和X2(k)，再計算式(3.4.7)。 /2 122/22/20( )DFT( )( ) 0,1,12NklNNlNX kx lx l Wk1212( )( )( ) 0,1,12( )( )2kNkNX kX kW XkNkNX kX kW Xk(3.4.6)(3.4.7)2NkkNNWW 返回返回回到本節(jié)回到本節(jié)蝶形圖 蝶形圖及運算功能 8點DF

45、T一次時域抽取分解運算流圖 返回返回回到本節(jié)回到本節(jié)8點DIT-FFT運算流圖 返回返回回到本節(jié)回到本節(jié)2. DIT-FFT的運算效率 DIT-FFT與DFT所需乘法次數(shù)比較曲線返回返回回到本節(jié)回到本節(jié)由8點DIT-FFT運算流圖可見，N=2M時，其DIT-FFT運算流圖由M級蝶形構成，每級有N/2個蝶形。因而，每級需要N/2次復數(shù)乘法運算和N次復數(shù)加法運算，M級蝶形所需復數(shù)乘法次數(shù)CM(2)和復數(shù)加法次數(shù)CA(2)分別為直接計算N點DFT的復數(shù)乘法次數(shù)為N2，復數(shù)加法次數(shù)為(N-1)N。當N1時，N2/CM(2) 1，所以N越大，DIT-FFT運算效率越高。DIT-FFT算法與DFT所需乘法

46、次數(shù)與N的關系曲線見前頁圖示。 M2(2) log 22NNCMNA2(2) log CNMNN返回返回回到本節(jié)回到本節(jié)例3.3：N=210=1024時，DIT-FFT的運算效率為而當N =211=2048時有 22M 1024204.81024(2)102NCDFT的乘法次數(shù)DIT-FFT的乘法次數(shù)22M222048 372.37(2)112NNNNCMM返回返回回到本節(jié)回到本節(jié)3. DIT-FFT的運算規(guī)律及編程思想 運算規(guī)律： （1原位計算 （2旋轉因子的變化規(guī)律 （3蝶形運算規(guī)律 （4序列的倒序 （5編程思想及程序框圖返回返回回到本節(jié)回到本節(jié)（1 1原位計算原位計算觀察每個蝶形的兩個輸

47、入和兩個輸出觀察每個蝶形的兩個輸入和兩個輸出蝶形的輸出可存入原輸入數(shù)據(jù)所占存儲單元蝶形的輸出可存入原輸入數(shù)據(jù)所占存儲單元利用同一組存儲單元存儲輸入、輸出數(shù)據(jù)的方法，稱利用同一組存儲單元存儲輸入、輸出數(shù)據(jù)的方法，稱為原位址計算。為原位址計算。節(jié)約內存節(jié)約內存節(jié)省尋址的時間節(jié)省尋址的時間返回返回回到本節(jié)回到本節(jié)（2旋轉因子的變化規(guī)律N點DIT-FFT運算流圖中，每級都有N/2個蝶形。每個蝶形都要乘以因子，稱其為旋轉因子，p稱為旋轉因子的指數(shù)。由于各級的旋轉因子和循環(huán)方式都有所不同。為了編寫計算程序，應先找出旋轉因子 與運算級數(shù)的關系。用L表示從左到右的運算級數(shù)L=1,2,M）。pNW返回返回回到本

48、節(jié)回到本節(jié) 由8點DIT-FFT運算流圖可以發(fā)現(xiàn)，第L級共有2L-1個不同的旋轉因子。N=23=8時的各級旋轉因子表示如下: L=1時 L=2時 L=3時 對N=2M的一般情況，第L級的旋轉因子為/42 0LpJJNNWWWJ12 0,1,2,21LpJLNWWJ/22 0,1LpJJNNWWWJ2 0,1,2,3LpJJNNWWWJ返回返回回到本節(jié)回到本節(jié)由于所以這樣，就可按上面兩個式子確定第L級運算的旋轉因子。 2222LML ML MN212 0,1,2,21MLL MpJJLNNNWWWJ2MLpJ實際編程序時，L為最外層循環(huán)變量返回返回回到本節(jié)回到本節(jié)（3 3蝶形運算規(guī)律蝶形運算規(guī)律

49、 設序列設序列x(n)x(n)經(jīng)時域抽選倒序后，存入數(shù)組經(jīng)時域抽選倒序后，存入數(shù)組A A中。中。如果蝶形運算的兩個輸入數(shù)據(jù)相距如果蝶形運算的兩個輸入數(shù)據(jù)相距B B個點，應用原位計個點，應用原位計算，則蝶形運算可表示成如下形式算，則蝶形運算可表示成如下形式: : 式中式中下標下標L L表示第表示第L L級運算，級運算，AL(J)AL(J)則表示第則表示第L L級運算后數(shù)組元級運算后數(shù)組元素素A(J)A(J)的值即第的值即第L L級蝶形的輸出數(shù)據(jù)）。而級蝶形的輸出數(shù)據(jù)）。而AL-1(J)AL-1(J)表示表示第第L L級運算前級運算前A(J)A(J)的值即第的值即第L L級蝶形的輸入數(shù)據(jù)）。級蝶形

50、的輸入數(shù)據(jù)）。 11()( )()pLLLNAJBAJAJB W11( )( )()pLLLNA JAJAJB W12; 0,1,21; 1,2,MLLpJJLM返回返回回到本節(jié)回到本節(jié)用實數(shù)運算完成上述蝶形運算，可按下面的算法進行：設式中，下標R表示取實部，I表示取虛部。那么設 那么1RI()jpLNTAJB WTT1R I( )( )j( )LAJAJAJRR II IR22()cos()sin22()cos()sinTAJBpAJBpNNTAJBpAJBpNNR I( )( )j( )LAJAJAJR I()()j()LAJBAJBAJB RRRI II( )( ), ( )( )AJA

51、JTAJAJT RRRI II()( ), ()( )AJBAJTAJBAJT返回返回回到本節(jié)回到本節(jié)（4 4序列的倒序序列的倒序 DIT-FFT DIT-FFT算法的輸出算法的輸出X(k)X(k)為自然順序，但為了適應原位計為自然順序，但為了適應原位計算，其輸入序列不是按算，其輸入序列不是按x(n)x(n)的自然順序排序，這種經(jīng)過的自然順序排序，這種經(jīng)過M-1M-1次次偶奇抽選后的排序稱為序列偶奇抽選后的排序稱為序列x(n)x(n)的倒序倒位）。的倒序倒位）。 因而，在運算之前應先對序列因而，在運算之前應先對序列x(n)x(n)進行倒序。進行倒序。由于由于N = 2MN = 2M，因此順序數(shù)

52、可用，因此順序數(shù)可用M M位二進制數(shù)位二進制數(shù)nM-1nM-2nM-1nM-2n1n0n1n0表表示。示。M M次偶奇時域抽選過程如次偶奇時域抽選過程如右圖所示。第一次按最低位右圖所示。第一次按最低位n0n0的的0 0和和1 1將將x(n)x(n)分解為偶奇兩分解為偶奇兩組，第二次又按次低位組，第二次又按次低位n1n1的的0 0、1 1值分別對偶奇組分解；依次值分別對偶奇組分解；依次類推，第類推，第M M次按次按nM-1nM-1位分解，最位分解，最后得到二進制倒序數(shù)。后得到二進制倒序數(shù)。 形成例序的樹狀圖(N = 23) 返回返回回到本節(jié)回到本節(jié)不按順序排列順 序倒 序十進制數(shù)I二進制數(shù)二進制

53、數(shù)十進制數(shù) J012345671 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 10 0 01 0 00 1 01 1 00 0 11 0 10 1 11 1 104261537(0),(1),(2),(7)XXXX(0),(1),(2),(7)xxxx 按順序輸出返回返回回到本節(jié)回到本節(jié)（5編程思想及程序框圖 先從輸入端第1級開場，逐級進行，共進行M級運算。在進行第L級運算時，依次求出B=2L-1個不同的旋轉因子，每求出一個旋轉因子，就計算完它對應的所有2M-L個蝶形。這樣，我們可用三重循環(huán)程序實現(xiàn)DIT-FFT運算，程序框圖如右 程序運行后，數(shù)組A中存放的是x(

54、n)的N點DFT，即X(k)=A(k)。 圖所示。返回返回回到本節(jié)回到本節(jié)4. IDFT的高效算法 上述FFT算法流圖也可以用于IDFT。比較DFT和IDFT的運算公式:只要將DFT運算式中的因子改為，最后乘以1/N，就是IDFT的運算公式。所以，只要將上述的DIT-FFT算法中的旋轉因子改為，最后的輸出再乘以1/N，就可以用來計算IDFT。如果流圖的輸入是X(k)，則輸出就是x(n)。 1010( )DFT ( )( )1( )IDFT( )( )Nk nNnNk nNnX kx nx n Wx nX kX k WN返回返回回到本節(jié)回到本節(jié)我們還可以直接調用FFT子程序計算IFFT ：由于對

55、上式兩邊同時取共軛，得到這樣，可以先將X(k)取共軛，然后直接調用FFT子程序，或者送入FFT專用硬件設備進行FFT運算，最后對FFT結果取共軛并乘以1/N得到序列x(n)。 101( )( )Nk nNkx nX k WN 1*01( )( )Nk nNkx nXk WN *1*011( )( )DFT( )Nk nNkx nXk WXkNN返回返回回到本節(jié)回到本節(jié)3.5 DFT(FFT)3.5 DFT(FFT)應用舉例應用舉例 DFT因為具有快速算法FFT，應用非常廣泛，限于篇幅，這里僅介紹DFT在線性卷積和頻譜分析兩方面的應用。本節(jié)主要論述：返回返回p 3.5.1 用DFTFFT計算兩個

56、有限長序列的線性卷積p 3.5.2 用DFT計算有限長序列與無限長序列的線性卷積p 3.5.3 用DFT對序列進行譜分析3.5.1 3.5.1 用用DFT(FFT)DFT(FFT)計算兩個有限長序列的計算兩個有限長序列的線性卷積線性卷積 當h(n)或x(n)序列較長時，直接計算線性卷積的時間會很長，滿足不了實時處理的要求?？捎肍FT將時域卷積變換為頻域相乘來計算線性卷積，達到快速實時要求。 下面求出線性卷積結果和循環(huán)卷積結果相等的條件： 設h(n)長度為N，x(n)長度為M，yc(n)和y(n)分別表示h(n)與x(n)的L點循環(huán)卷積和線性卷積， ，有 max,LN Mc( )( )y nh

57、n10( )( ) ()( )NLLmx nh m x nmRn10( )( )( )( ) ()Nmy nh nx nh m x nm(3.5.1)(3.5.2)L返回返回回到本節(jié)回到本節(jié)在式(3.5.1)中 因而將上式與式(3.5.2)對比，方括號部分就是移位iL的線性卷積 ，因此得到 ()()Lix nmx n miL 1c0( )( )()( )NLmiy nh mx nmiL Rn 10( ) () ( )NLimh m x nmiLRn ()y niL c( )()( )Liy ny niL Rn(3.5.5)(3.5.3)(3.5.4)返回返回回到本節(jié)回到本節(jié) 式(3.5.5)說

58、明，L點循環(huán)卷積yc(n)等于線性卷積y(n)以L為周期的周期延拓序列的主值序列。 由于y(n)長度為N+M-1，所以，只有當LN+M-1時，式(3.5.5)給出的周期延拓無混疊，才能使yc(n)=y(n)。 LN+M-1是循環(huán)卷積結果和線性卷積結果相等的重要條件。只要滿足該條件，就可以用下圖計算線性卷積。 返回返回回到本節(jié)回到本節(jié)循環(huán)卷積計算線性卷積的運算量：循環(huán)卷積計算線性卷積的運算量：u 小于直接計算線性卷積的運算量u 可預先計算并存儲，乘法的 u 運算次數(shù)可降低：u 又稱快速卷積法32NM20.5 logLL次( ) ( )H kDFT h n返回返回回到本節(jié)回到本節(jié)例例3.43.4106( )( ), ( )( )x nRnh nRn( )