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

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

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

3、T與ZT、FT、DFS的關(guān)系p 3.1.3 DFT的矩陣表示3.1.1 DFT3.1.1 DFT定義定義設(shè)序列x(n)長(zhǎng)度為M，定義x(n)的N點(diǎn)DFT為式中，N稱(chēng)為離散傅里葉變換區(qū)間長(zhǎng)度，要求N M。為書(shū)寫(xiě)簡(jiǎn)單，令 ，因此通常將N點(diǎn)DFT表示為定義X(k)的N點(diǎ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長(zhǎng)度為

4、N的離散序列返回返回回到本節(jié)回到本節(jié)例3.1： ，分別計(jì)算x(n)的8點(diǎn)、16點(diǎn)DFT。解: x(n)的8點(diǎn)DFT為 x(n)的16點(diǎn)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的關(guān)系的關(guān)系 DFT有明確的物理意義，我們可以通過(guò)比較序列的DFT、FT、ZT，并將DFT與周期序列的DFS聯(lián)系起來(lái)，得到DFT的物理意義。 DFT和FT、ZT之間的關(guān)系 假設(shè)序列的長(zhǎng)度為M，NM將N點(diǎn)DFT和FT、ZT的定義重寫(xiě)如下 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 結(jié)論：(1)序列的N點(diǎn)DF

6、T是序列傅里葉變換在頻率區(qū)間0，2上的N點(diǎn)等間隔采樣，采樣間隔為2 /N。 (2)序列的N點(diǎn)DFT是序列的Z變換在單位圓上的N點(diǎ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點(diǎn)點(diǎn)DFT是是 x(n)的的Z變換在單位圓上的變換在單位圓上的N點(diǎn)等點(diǎn)等間隔采樣；間隔采樣； X(k)為為x(n)的傅立葉變換的傅立葉變換 在區(qū)間在區(qū)間 上的上的N點(diǎn)等間隔采樣。這就是點(diǎn)等間隔采樣。

7、這就是DFT的物理意義。的物理意義。0, 2 ()jX e變量周期分辨率2N2f、ssf、NfskN返回返回回到本節(jié)回到本節(jié)DFTDFT和和DFSDFS之間的關(guān)系：之間的關(guān)系： 周期延拓周期延拓 取主值取主值 有限長(zhǎng)序列有限長(zhǎng)序列 周期序列周期序列 主值區(qū)序列主值區(qū)序列有限長(zhǎng)序列有限長(zhǎng)序列周期序列周期序列主值區(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、有限長(zhǎng)序列的DFT:對(duì)比二者發(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之間的關(guān)系之間的關(guān)系: :有限長(zhǎng)序列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之間的關(guān)系之間的關(guān)系: : 周期延拓序列 的頻譜特性由其傅里葉級(jí)數(shù)的 系數(shù) 確定，幅度相差一個(gè)常數(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以及有限長(zhǎng)序列x(n)的DFT如下可以發(fā)現(xiàn)它們右邊的函數(shù)形式一樣，但k的定義域不同，X(k)只是 的主值區(qū)序列，或者說(shuō)X(k)以N為周期進(jìn)行周期延拓即是 ，用后面兩式表示二者的關(guā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)說(shuō)明了DFT和DFS

11、之間的關(guān)系。這些關(guān)系式成立的條件是N M，即DFT的變換區(qū)間N不能小于x(n)的長(zhǎng)度M。如果該條件不滿足，按照式(3.1.5)將x(n)進(jìn)行延拓時(shí)， 中將發(fā)生時(shí)域混疊，由式(3.1.8)得到的X(k)不再是x(n)的DFT，這時(shí)以上講的DFS和DFT之間的關(guān)系不再成立。 ( )()mX kX kmN( )( )( )NX kX k Rk(3.1.7)(3.1.8)( )Nxn返回返回回到本節(jié)回到本節(jié)也可以表示成矩陣形式式中，X是N點(diǎn)DFT頻域序列向量:x是時(shí)域序列向量:DN稱(chēng)為N點(diǎ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é)也可以表示為矩陣形式: 稱(chēng)為N點(diǎ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的主要性質(zhì)的主要性質(zhì)與序列的FT類(lèi)似，DFT也有許多重要的性質(zhì)。其中一些性質(zhì)本質(zhì)上與FT的相應(yīng)性質(zhì)相同，但是某些其他性質(zhì)稍微有些差別。返回返回p 線性性質(zhì) p DFT的隱含周期性 p 循環(huán)移位性質(zhì) p 復(fù)共軛序列的DFT p DFT的共軛對(duì)稱(chēng)性 p 循環(huán)卷積定理循環(huán)卷積定理p 離散巴塞伐爾定理離散巴塞伐爾定理 線性性質(zhì)線性性質(zhì) 設(shè)有限長(zhǎng)序列設(shè)有限長(zhǎng)序列 的長(zhǎng)度分別為的長(zhǎng)度分別為 ， ，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個(gè)值。如果使個(gè)值。如果使DFTDFT中中k k的取值域?yàn)榈娜≈涤驗(yàn)?，就會(huì)發(fā)，就會(huì)發(fā)現(xiàn)現(xiàn) X(k)X(k)是以是以N N為周期的，即為周期的，即 X(k + mN) = X(k) X(k + mN) = X(k

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

16、x(n)x(n)以以N N為周期進(jìn)行周期延拓，再左移為周期進(jìn)行周期延拓，再左移m m個(gè)個(gè)單位并取主值序列，單位并取主值序列， 就得到就得到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)移位過(guò)程示意圖返回返回回到本節(jié)回到本節(jié) 循環(huán)移位性質(zhì) 設(shè)序列x(

17、n)長(zhǎng)度為M，x(n)的循環(huán)移位序列為 ， N M那么 復(fù)共軛序列的DFT 假設(shè)用 表示x(n)的復(fù)共軛序列，長(zhǎng)度為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的共軛對(duì)稱(chēng)性的共軛對(duì)稱(chēng)性上一章介紹了序列上一章介紹了序列FTFT的共軛對(duì)稱(chēng)性，的共軛對(duì)稱(chēng)性，DFTDFT也有類(lèi)似的共也有類(lèi)似的共軛軛對(duì)稱(chēng)性質(zhì)。但對(duì)稱(chēng)性質(zhì)。但FTFT中的共

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

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

20、和虛部，相應(yīng)x(n)的DFT分成共軛對(duì)稱(chēng)和共軛反對(duì)稱(chēng)兩部分。即式中， ，那么 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)分成共軛對(duì)稱(chēng)和共軛反對(duì)稱(chēng)兩部分，相應(yīng)x(n)的DFT分成實(shí)部和虛部?jī)刹糠郑词街校?， ，那么epopri( )( )( )( )( )j( )x nxnxnX kXkX kr( ) Re( )XkX k=i( )Im( )X kX krep( )DFT(

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

22、返回回到本節(jié)回到本節(jié)a) 設(shè) 是實(shí)序列，長(zhǎng)度均為N，用它們構(gòu)成一個(gè)復(fù)序列 對(duì)上式進(jìn)行N點(diǎn)DFT，得到利用的結(jié)論可以得到這樣只計(jì)算一個(gè)N點(diǎn)DFT，得到X(k)，用上面兩式容易得到兩個(gè)實(shí)序列的N點(diǎ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) 通過(guò)復(fù)序列的N點(diǎn)DFT得到實(shí)序列的2N點(diǎn)D

23、FT。設(shè) 是一個(gè)長(zhǎng)度為2N的實(shí)序列，首先分別用 中的偶數(shù)點(diǎn)和奇數(shù)點(diǎn)形成兩個(gè)長(zhǎng)度為N的新序列 ，即 再由 構(gòu)造長(zhǎng)度為N的復(fù)序列x(n)，即計(jì)算x(n)的N點(diǎn)DFT，因?yàn)?均是實(shí)序列，利用式(3.2.18)和式(3.2.19)得到 。最后由 以得到實(shí)序列v(n)的2N點(diǎn)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é)實(shí)序列實(shí)序列2N2N點(diǎn)的點(diǎn)的DFTDFT，拆分重組為，拆分重組為N N點(diǎn)復(fù)序列點(diǎn)復(fù)序列DFTDFT例如例如 是實(shí)序列，長(zhǎng)度為是實(shí)序列，長(zhǎng)度為2N2N拆分拆分重組重組N N點(diǎn)點(diǎ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)卷積定理時(shí)域循環(huán)卷積定理是時(shí)域循環(huán)卷積定理是DFTDFT中很重要的定理，具有很強(qiáng)的中很重要的定理，具有很強(qiáng)的實(shí)用實(shí)用性。已知系統(tǒng)輸入和系統(tǒng)的單位脈沖響應(yīng)，計(jì)算系統(tǒng)的性。已知系統(tǒng)輸入和系統(tǒng)的單位脈沖響應(yīng)，計(jì)算系統(tǒng)的輸輸出，以及出，以及FIRFIR濾波器用濾波器用FFTFFT實(shí)現(xiàn)等，都是該定理的重要應(yīng)實(shí)現(xiàn)等，都是該定理的重要應(yīng)用。用。1. 1. 兩個(gè)有限長(zhǎng)序列的循環(huán)卷積兩個(gè)有限長(zhǎng)序列的循環(huán)卷積 設(shè)序列設(shè)序列h(n)h(n)和和x(n)x(n)的長(zhǎng)度分別為的長(zhǎng)度分別為N N和和M M。h(n)h(n)與與x(n)x(n)的的L L點(diǎn)循點(diǎn)循環(huán)卷積定義為環(huán)卷積定義為式中，式中，L

26、L稱(chēng)為循環(huán)卷積的長(zhǎng)度，稱(chēng)為循環(huán)卷積的長(zhǎng)度，LmaxNLmaxN，MM。 為了區(qū)別線性卷積，用為了區(qū)別線性卷積，用 表示循環(huán)卷積，用表示循環(huán)卷積，用 表示表示L L點(diǎn)循點(diǎn)循環(huán)卷積，即環(huán)卷積，即 x(n) x(n)。 1c0( )( ) ()( )LLLmy nh m x nmRnc( )( )y nh nLL返回返回回到本節(jié)回到本節(jié)有限長(zhǎng)序列循環(huán)卷積的矩陣形式上式中右邊第一個(gè)矩陣稱(chēng)為x(n)的L點(diǎn)循環(huán)矩陣，它的特點(diǎn)是：(a)第一行是x(n)的L點(diǎn)循環(huán)倒相。x(0)不動(dòng)，后面其它反轉(zhuǎn)180放在他的后面。(b)第二行是第一行向右循環(huán)移一位；(c)第三行是第二行向右循環(huán)移一位；依次類(lèi)推。) 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： 計(jì)算下面給出的兩個(gè)長(zhǎng)度為4的序列h(n)與x(n)的4點(diǎn)和8點(diǎn)循環(huán)卷積。解: 按照式(3.2.21)寫(xiě)出h(n)與x(n)的4點(diǎn)循環(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點(diǎn)循環(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的時(shí)域循環(huán)卷積定理 設(shè)h(n)和x(n)長(zhǎng)度分別為N和M，yc(n)為序列h(n)和x(n)的L點(diǎn)循環(huán)卷積，即 x(n) 那么

29、式中時(shí)域循環(huán)卷積定理表明，DFT將時(shí)域循環(huán)卷積關(guān)系，變換成頻域的相乘關(guān)系。用時(shí)域循環(huán)卷積定理計(jì)算兩個(gè)序列循環(huán)卷積運(yù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計(jì)算兩個(gè)有限長(zhǎng)序列L點(diǎn)循環(huán)卷積運(yùn)算的方框圖 L返回返回回到本節(jié)回到本節(jié)3. DFT的頻域循環(huán)卷積定理設(shè)h(n)和x(n)長(zhǎng)度分別為N和M，并且 ，那么 式中，LmaxN, M。DFT： 時(shí)域循環(huán)卷積 頻域乘積離散巴塞伐爾定理 設(shè)長(zhǎng)度為N的序列x(n)的N點(diǎ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 頻域采樣頻域采樣時(shí)域和頻域的對(duì)偶原理時(shí)域和頻域的對(duì)偶原理 對(duì)時(shí)間序列對(duì)時(shí)間序列x(n)x(n)的連續(xù)頻譜的連續(xù)頻譜函數(shù)在頻域等間隔采樣，則采樣得到的離散頻譜對(duì)應(yīng)的時(shí)函數(shù)在頻域等間隔采樣，則采樣得到的離散頻譜對(duì)應(yīng)的時(shí)域域序列必然是原時(shí)間序列序列必然是原時(shí)間序列x(

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

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

33、 的時(shí)域周期序列是原序列x(n)的周期延拓序列，延拓周期為N。根據(jù)DFT與DFS之間的關(guān)系知道，分別截取 和 的主值序列 那么 和 構(gòu)成一對(duì)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)式表明 是對(duì)X(z)在單位圓上的N點(diǎn)等間隔采樣，即對(duì) 在頻率區(qū)間0，2上的N點(diǎn)等間隔采樣。(3.3.3)式(3.3.6)式說(shuō)明， 對(duì)應(yīng)的時(shí)域有限長(zhǎng)序列 就是原序列x(n)以N為周期的周期延拓序列的主值序列。綜上所述，可以總結(jié)出頻域采樣定理:如果原序列x(n)長(zhǎng)度為M，對(duì) 在頻率區(qū)間0，2上等間隔采樣N點(diǎn)，得到 ，則僅當(dāng)采樣點(diǎn)數(shù)NM時(shí)，才能由頻域采樣 恢復(fù) ，否則將產(chǎn)生時(shí)域混疊失真，不能由 恢復(fù)原序列x(n)。定理告誡我們，只有當(dāng)時(shí)域序列x(n)為有限長(zhǎng)時(shí)，以適當(dāng)?shù)牟蓸娱g隔對(duì)其頻譜函數(shù) 采樣，才不會(huì)丟失信息。j(e)X( )NXk( )NXk( )Nxn( )IDFT( )NNx nX

35、kj(e)X( )NXk( )NXk( )NXkj(e)X返回返回回到本節(jié)回到本節(jié)返回返回回到本節(jié)回到本節(jié)2. 2. 頻域內(nèi)插公式頻域內(nèi)插公式 所謂頻域內(nèi)插公式，就是用頻域采樣所謂頻域內(nèi)插公式，就是用頻域采樣 表示表示X(z)X(z)和和 。頻域內(nèi)插公式是頻域內(nèi)插公式是FIRFIR數(shù)字濾波器的頻率采樣結(jié)構(gòu)和頻率采樣數(shù)字濾波器的頻率采樣結(jié)構(gòu)和頻率采樣設(shè)計(jì)法的理論依據(jù)。設(shè)計(jì)法的理論依據(jù)。設(shè)序列設(shè)序列x(n)x(n)的長(zhǎng)度為的長(zhǎng)度為M M，在，在Z Z平面單位圓上對(duì)平面單位圓上對(duì)X(z)X(z)的采樣點(diǎn)數(shù)的采樣點(diǎn)數(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)稱(chēng)為用 表示X(z)的z域內(nèi)插公式。 稱(chēng)為z域內(nèi)插函數(shù)。將 帶入(c)式并化簡(jiǎn)，得到用 表示 的內(nèi)插公式和內(nèi)插函數(shù) :式(3.3.12)和式(3.3.13)將用于FIR數(shù)字濾波器的頻率采樣設(shè)計(jì)法的誤差分析。 ( )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、 內(nèi)插公式：212 ()20kikNkNiikN l保證了各采樣點(diǎn)上保證了各采樣點(diǎn)上的值與原序列的頻的值與原序列的頻譜相同；譜相同；l采樣點(diǎn)之間為采樣采樣點(diǎn)之間為采樣值與對(duì)應(yīng)點(diǎn)的內(nèi)插值與對(duì)應(yīng)點(diǎn)的內(nèi)插公式相乘，并疊加公式相乘，并疊加而成。而成。返回返回回到本節(jié)回到本節(jié)3.4 DFT3.4 DFT的快速算法的快速算法快速傅里葉快速傅里葉變換變換(FFT)(FFT)l DFT使計(jì)算機(jī)在頻域處理信號(hào)成為可能，但是當(dāng)N很大時(shí)，直接計(jì)算N點(diǎn)DFT的計(jì)算量非常大。l 快速傅里葉變換FFT，F(xiàn)ast Fourier Transform可使實(shí)現(xiàn)DFT的運(yùn)算量下降幾個(gè)數(shù)量級(jí)，從而使數(shù)字信號(hào)處理的速度大大提高，工程

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

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

41、旋轉(zhuǎn)因子的周期性和對(duì)稱(chēng)性：旋轉(zhuǎn)因子的周期性和對(duì)稱(chēng)性： 的周期性：的周期性： 的對(duì)稱(chēng)性：的對(duì)稱(chēng)性：mNW 22j()jeem l Nmm l NmNNNNWW*()N mmNNWWmNW2NmmNNWW 返回返回回到本節(jié)回到本節(jié)快速傅里葉變換就是不斷地將長(zhǎng)序列的DFT分解為短序列的DFT，并利用 的周期性和對(duì)稱(chēng)性及其一些特殊值來(lái)減少DFT運(yùn)算量的快速算法。 時(shí)間域抽?。侯l率域抽取：(2 )( )0,1,1(21)2xrNx nrxrmNW 基基2時(shí)間抽取時(shí)間抽取(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ū)間長(zhǎng)度變換區(qū)間長(zhǎng)度N=2MN=2M，M M為自然數(shù)。為自然數(shù)。 DIT-FFTDIT-FFT算法算法 序列序列x(n)x(n)的的N N點(diǎn)點(diǎ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)，因?yàn)?，所以上式可寫(xiě)成上式說(shuō)明，按n的奇偶性將x(n)分解為兩個(gè)N/2長(zhǎng)的序列x1(l)和x2(l)，則N點(diǎn)DFT可分解為兩個(gè)N/2點(diǎn)DFT來(lái)計(jì)算。用X1(k)和X2(k)分別表示x1(l)和x2(l)的N/2點(diǎn)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點(diǎn)DFT的計(jì)算分解為計(jì)算兩個(gè)N/2點(diǎn)離散傅里葉變換X1(k)和X2(k)，再計(jì)算式(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é)蝶形圖 蝶形圖及運(yùn)算功能 8點(diǎn)DF

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

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

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

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

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

50、的輸入數(shù)據(jù)）。 11()( )()pLLLNAJBAJAJB W11( )( )()pLLLNA JAJAJB W12; 0,1,21; 1,2,MLLpJJLM返回返回回到本節(jié)回到本節(jié)用實(shí)數(shù)運(yùn)算完成上述蝶形運(yùn)算，可按下面的算法進(jìn)行：設(shè)式中，下標(biāo)R表示取實(shí)部，I表示取虛部。那么設(shè) 那么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)為自然順序，但為了適應(yīng)原位計(jì)為自然順序，但為了適應(yīng)原位計(jì)算，其輸入序列不是按算，其輸入序列不是按x(n)x(n)的自然順序排序，這種經(jīng)過(guò)的自然順序排序，這種經(jīng)過(guò)M-1M-1次次偶奇抽選后的排序稱(chēng)為序列偶奇抽選后的排序稱(chēng)為序列x(n)x(n)的倒序倒位）。的倒序倒位）。 因而，在運(yùn)算之前應(yīng)先對(duì)序列因而，在運(yùn)算之前應(yīng)先對(duì)序列x(n)x(n)進(jìn)行倒序。進(jìn)行倒序。由于由于N = 2MN = 2M，因此順序數(shù)

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

53、數(shù)十進(jìn)制數(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級(jí)開(kāi)場(chǎng)，逐級(jí)進(jìn)行，共進(jìn)行M級(jí)運(yùn)算。在進(jìn)行第L級(jí)運(yùn)算時(shí)，依次求出B=2L-1個(gè)不同的旋轉(zhuǎn)因子，每求出一個(gè)旋轉(zhuǎn)因子，就計(jì)算完它對(duì)應(yīng)的所有2M-L個(gè)蝶形。這樣，我們可用三重循環(huán)程序?qū)崿F(xiàn)DIT-FFT運(yùn)算，程序框圖如右 程序運(yùn)行后，數(shù)組A中存放的是x(

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

55、上式兩邊同時(shí)取共軛，得到這樣，可以先將X(k)取共軛，然后直接調(diào)用FFT子程序，或者送入FFT專(zhuān)用硬件設(shè)備進(jìn)行FFT運(yùn)算，最后對(duì)FFT結(jié)果取共軛并乘以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)應(yīng)用舉例應(yīng)用舉例 DFT因?yàn)榫哂锌焖偎惴‵FT，應(yīng)用非常廣泛，限于篇幅，這里僅介紹DFT在線性卷積和頻譜分析兩方面的應(yīng)用。本節(jié)主要論述：返回返回p 3.5.1 用DFTFFT計(jì)算兩個(gè)

56、有限長(zhǎng)序列的線性卷積p 3.5.2 用DFT計(jì)算有限長(zhǎng)序列與無(wú)限長(zhǎng)序列的線性卷積p 3.5.3 用DFT對(duì)序列進(jìn)行譜分析3.5.1 3.5.1 用用DFT(FFT)DFT(FFT)計(jì)算兩個(gè)有限長(zhǎng)序列的計(jì)算兩個(gè)有限長(zhǎng)序列的線性卷積線性卷積 當(dāng)h(n)或x(n)序列較長(zhǎng)時(shí)，直接計(jì)算線性卷積的時(shí)間會(huì)很長(zhǎng)，滿足不了實(shí)時(shí)處理的要求?？捎肍FT將時(shí)域卷積變換為頻域相乘來(lái)計(jì)算線性卷積，達(dá)到快速實(shí)時(shí)要求。 下面求出線性卷積結(jié)果和循環(huán)卷積結(jié)果相等的條件： 設(shè)h(n)長(zhǎng)度為N，x(n)長(zhǎng)度為M，yc(n)和y(n)分別表示h(n)與x(n)的L點(diǎn)循環(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)對(duì)比，方括號(hào)部分就是移位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)說(shuō)

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