大連理工大學(xué)信號(hào)8離散傅里葉變換與快速傅里葉變換

1、2021-11-11大連理工大學(xué)1Part III數(shù)字信號(hào)處理數(shù)字信號(hào)處理大連理工大學(xué)碩士研究生校管課程大連理工大學(xué)碩士研究生校管課程信號(hào)處理與數(shù)據(jù)分析信號(hào)處理與數(shù)據(jù)分析電子信息與電氣工程學(xué)部電子信息與電氣工程學(xué)部邱天爽邱天爽2013年年11月月2021-11-11大連理工大學(xué)2第第8章章離散傅里葉變換與快速傅里葉離散傅里葉變換與快速傅里葉變換變換大連理工大學(xué)碩士研究生校管課程大連理工大學(xué)碩士研究生校管課程信號(hào)處理與信號(hào)處理與數(shù)據(jù)分析數(shù)據(jù)分析電子信息與電氣工程學(xué)部電子信息與電氣工程學(xué)部邱天爽邱天爽2013年年11月月 內(nèi)容概要內(nèi)容概要 8.1 8.1 離散傅里葉變換（離散傅里葉變換（DFTDF

2、T） 8.2 8.2 離散傅里葉變換的性質(zhì)離散傅里葉變換的性質(zhì) 8.3 8.3 與與DFTDFT相關(guān)的幾個(gè)問(wèn)題相關(guān)的幾個(gè)問(wèn)題 8.4 8.4 快速傅里葉變換（快速傅里葉變換（FFTFFT） 8.5 FFT8.5 FFT的應(yīng)用的應(yīng)用 推薦教材：程佩青，數(shù)字信號(hào)處理教程（第三推薦教材：程佩青，數(shù)字信號(hào)處理教程（第三版），清華大學(xué)出版社，版），清華大學(xué)出版社，201120112021-11-11大連理工大學(xué)48.1 離散傅里葉變換（離散傅里葉變換（DFTDFT）2021-11-11大連理工大學(xué)5 0. 為什么要學(xué)習(xí)離散傅里葉變換（為什么要學(xué)習(xí)離散傅里葉變換（DFT）？）？數(shù)字信號(hào)處理，要求信號(hào)是數(shù)字

3、化的，也希望頻譜或頻率響應(yīng)也是數(shù)字化的。實(shí)際應(yīng)用中的信號(hào)總是有限時(shí)寬的、且為非周期的。希望信號(hào)頻譜也是有限頻寬、且非周期的?？疾烨懊娼榻B的4種傅里葉級(jí)數(shù)或傅里葉變換，沒有任何一種能夠滿足這種需求。因此，發(fā)展新的傅里葉變換方法以適應(yīng)數(shù)字信號(hào)處理實(shí)際應(yīng)用的要求稱為數(shù)字信號(hào)處理理論的一個(gè)重要任務(wù)。這就為DFT的發(fā)展提供了需求和動(dòng)力2021-11-11大連理工大學(xué)6 1. 已學(xué)過(guò)的幾種傅里葉級(jí)數(shù)和傅里葉變換已學(xué)過(guò)的幾種傅里葉級(jí)數(shù)和傅里葉變換 （1）FS： 連續(xù)、周期連續(xù)、周期 ； 離散、非周期；離散、非周期； （2）DFS： 離散、周期；離散、周期； 離散、周期；離散、周期； ( )x tka x n

4、ka002jj2jj11( )ed( )ed( )eektktTkTTktktTkkkkax ttx ttTTx taa002jj2jj11( )e( )e( )eeknknNknNnNknknNkkkNkNax nx nNNx naa2021-11-11大連理工大學(xué)7 （3）FT： 連續(xù)、非周期連續(xù)、非周期 ； 連續(xù)、非周期；連續(xù)、非周期； （4）DTFT： 離散、非周期；離散、非周期； 連續(xù)、周期；連續(xù)、周期； ( )x t x n(j )Xj(e )Xjj(j )( )ed1( )(j )ed2ttXx ttx tX jjjj2(e ) e1 (e )ed2nnnXx nx nX2021

5、-11-11大連理工大學(xué)8 分析：分析：注意到，在注意到，在DFSDFS中，時(shí)間序列中，時(shí)間序列 是周期性的，周期是周期性的，周期為為N N。另一方面，周期為另一方面，周期為N N的序列只有的序列只有N N點(diǎn)點(diǎn)獨(dú)立樣本獨(dú)立樣本，其余的，其余的都重復(fù)。都重復(fù)。 DFS中，實(shí)際上只用了中，實(shí)際上只用了 的的N點(diǎn)數(shù)據(jù)。點(diǎn)數(shù)據(jù)。這樣，這樣，可以把可以把N N點(diǎn)長(zhǎng)的非周期序列看成周期為點(diǎn)長(zhǎng)的非周期序列看成周期為N N的序列的序列的一個(gè)周期。的一個(gè)周期。 x n x n2021-11-11大連理工大學(xué)9 離散傅里葉變換（離散傅里葉變換（DFTDFT） 【假設(shè)假設(shè)】 設(shè)設(shè) 為有限長(zhǎng)序列，點(diǎn)數(shù)為為有限長(zhǎng)序列，

6、點(diǎn)數(shù)為N，可將其看作周期，可將其看作周期為為N的周期序列的周期序列 的一個(gè)周期；而把的一個(gè)周期；而把 看作看作是是 的周期延拓，即：的周期延拓，即： 稱稱 是是 的主值序列。的主值序列。 記為：記為： 表示表示“ “ 對(duì)對(duì) 取余數(shù)取余數(shù)”，或，或 對(duì)對(duì) 取模值。取模值。( )x n( )x n( )x n( )x n( ) 01 ( )0 x nnNx nn，（主值），其他( )x n( )x n( )()( )Nx nx nNx n模( )Nx nnnNN( )()rx nx nrN2021-11-11大連理工大學(xué)10 【例例8.1】 設(shè)設(shè) 為周期為周期 的序列，求的序列，求 兩數(shù)對(duì)兩數(shù)對(duì)

7、的余數(shù)。的余數(shù)。 【解解】 因?yàn)椋阂驗(yàn)椋?，故：，故： 因?yàn)椋阂驗(yàn)椋?，故：，故： 這樣：這樣：( )x n9N N25,5nn 252 97n 9(25)75( 1)94n 9( 5)499(25)(25)(7)( 5)( 5)(4)xxxxxx2021-11-11大連理工大學(xué)11 DFT的定義：的定義： 【定義定義】式中，式中，211j00211j00( )DFT ( )( )e( ),0,1,11( )IDFT( )( )e( ),0,1,1NNknknNNnnNNknknNNkkX kx nx nx n WkNx nX kX kX k WnNN2jeNNW離散，離散，非非周期周期 離散

8、離散非非周期周期 二者均隱二者均隱含含周期周期性性( )x n( )X k22jj e, eknknknknNNNNWW002jj2jj11( )e( )e( )eeknknNknNnNknknNkkkNkNax nx nNNx naaDFS：2021-11-11大連理工大學(xué)12 定義定義加窗函數(shù)加窗函數(shù) 則則DFT定義式改寫為：定義式改寫為： 即即DFT是是DFS的一個(gè)周期的一個(gè)周期。1 01 1 01 ( )( )0 0 NNnNkNR nR knk ，或，其它，其它1010( )( )( )( )( )1( )( )( )( )( )NnkNNNnNnkNNNkX kx n WRkX k

9、 Rkx nX k WRnx n RnN2021-11-11大連理工大學(xué)13 DFT的圖形解釋的圖形解釋2021-11-11大連理工大學(xué)14 說(shuō)明（參考上頁(yè)圖）說(shuō)明（參考上頁(yè)圖） (a) 長(zhǎng)度為長(zhǎng)度為T的連續(xù)時(shí)間信號(hào)，其頻譜為的連續(xù)時(shí)間信號(hào)，其頻譜為 。 (b) 時(shí)域采樣信號(hào)：時(shí)域采樣信號(hào)： ，其頻譜仍為，其頻譜仍為同周期脈沖序列。同周期脈沖序列。 (c) 采樣，連續(xù)時(shí)間信號(hào)離散化，頻譜周期性延拓。采樣，連續(xù)時(shí)間信號(hào)離散化，頻譜周期性延拓。 (d) 頻域采樣信號(hào)。頻域采樣信號(hào)。 (e) 頻域采樣的結(jié)果，頻譜離散化，信號(hào)周期性延拓。頻域采樣的結(jié)果，頻譜離散化，信號(hào)周期性延拓。 (j )X( )(

10、)SSnp tTtnT2021-11-11大連理工大學(xué)15 DFTDFT與與DTFTDTFT及及z z變換的關(guān)系變換的關(guān)系設(shè)設(shè) 長(zhǎng)為長(zhǎng)為N N點(diǎn)，則：點(diǎn)，則：其中：其中： 定義在整個(gè)定義在整個(gè)z z平面；平面； 僅在僅在z z平面單位圓平面單位圓上取值；上取值； 是單位圓上是單位圓上N個(gè)等個(gè)等間距點(diǎn)上取值間距點(diǎn)上取值 是是 的主值周期。的主值周期。( )x nj11j001jje021jj20( )( )( )( e )(e )( )e( )( )( )e(e )NNnnnnNnznNnkNknNX zx n zx n rXx nX zX kx nX( )X zj(e)X( )X k( )X

11、kka( )( )kNX ka Rk2021-11-11大連理工大學(xué)168.2 離散傅里葉變換的性質(zhì)離散傅里葉變換的性質(zhì)2021-11-11大連理工大學(xué)17 【線性性質(zhì)線性性質(zhì)】 若：若： 則：則： 【序列的圓周位移性質(zhì)序列的圓周位移性質(zhì)】 將將 延拓為延拓為 ，將，將 位移，取主值區(qū)間上的位移，取主值區(qū)間上的序列值序列值。即：即： 圓周位移：圓周位移： 若：若： 則：則：1122DFT( )( ), DFT( )( )x nX kx nXk1212DFT( )( )( )( )ax nbx naX kbXk( )x n( )x n( )x n( )()( )()( )mNNNxnx nmRn

12、x nm Rn( )DFT( )( )mkmmNXkxnWX kDFT( )( )x nX k2021-11-11大連理工大學(xué)18 【圓周位移的圖形解釋圓周位移的圖形解釋】左移左移=順時(shí)針旋轉(zhuǎn)順時(shí)針旋轉(zhuǎn)右移右移=逆時(shí)針旋轉(zhuǎn)逆時(shí)針旋轉(zhuǎn)2021-11-11大連理工大學(xué)19 【對(duì)偶性對(duì)偶性】 若：若： 則：則： 【帕色伐爾定理帕色伐爾定理】 若：若： 則：則：DFT( )( )x nX kDFT( )()( )()( )NNNNX nNxkRkNxNkRkDFT( )( )x nX k11*001( )( )( )( )NNnnx n y nX k YkN2021-11-11大連理工大學(xué)20 【圓周

13、共軛對(duì)稱性圓周共軛對(duì)稱性】 若：若： 則：則：DFT( )DFT Re( )jIm( )x nx nx n*ep*op*1 DFT( )()( )=()( )2 DFT( )( )( )13 DFT Re ( )( )( )()( )214 DFT jIm ( )( )( )()( )25( )()( ), ( ) NNNNNNNNNNNNNNx nXkR kXNkR kxnR nX kx nXkX kXNkR kx nXkX kXNkR kX kXNkR kx n若* real6( )()( ) ( ) imagenaryNNX kXNkR kx n， 若2021-11-11大連理工大學(xué)21

14、 【滿足圓周共軛對(duì)稱性的序列滿足圓周共軛對(duì)稱性的序列】2021-11-11大連理工大學(xué)22 【圓周卷積和性質(zhì)圓周卷積和性質(zhì)】 若：若： 若：若： 則：則：1122DFT( )( ), DFT( )( )x nX kx nXk12( )( )( )Y kX kXk11201210( )IDFT( )( ) ()( ) ( ) ()( )NNNmNNNmy nY kx m xn mR nx m xn mR n2021-11-11大連理工大學(xué)23【圓周卷積和圖示圓周卷積和圖示】 把主值周期左邊一個(gè)把主值周期左邊一個(gè)周期的數(shù)據(jù)反折到主周期的數(shù)據(jù)反折到主值區(qū)間。值區(qū)間。 右移，最右邊的移右移，最右邊的移

15、至最左邊至最左邊2021-11-11大連理工大學(xué)24 【圓周相關(guān)性質(zhì)圓周相關(guān)性質(zhì)】 若：若： 若：若： 則：則：DFT( )( ), DFT( )( )x nX ky nY k*( )( )( )xyRkX k Yk1*01*0( )IDFT( )( ) ()( ) ( )()( )NxyxyNNnNNNnrmRky n x nmRmx n ynmRm2021-11-11大連理工大學(xué)25 有限長(zhǎng)序列的線性卷積和圓周卷積有限長(zhǎng)序列的線性卷積和圓周卷積 （1）線性卷積）線性卷積 非零值區(qū)間：非零值區(qū)間： ，其中，其中 和和 分別為分別為兩序列的長(zhǎng)度。兩序列的長(zhǎng)度。 其中，其中， 的非的非0區(qū)間為區(qū)

16、間為 ； 的非的非0區(qū)間為區(qū)間為 線性卷積的長(zhǎng)度：線性卷積的長(zhǎng)度： 1112120( )( )()( )()Nlmmy nx m x nmx m x nm120,2NN121NNN1N2N1( )x m101mN2()x nm201nmN2021-11-11大連理工大學(xué)26 （2）圓周卷積）圓周卷積 將將 看成看成L點(diǎn)序列，點(diǎn)序列， ，不足補(bǔ)，不足補(bǔ)0. 則則 結(jié)論：結(jié)論： L點(diǎn)圓周卷積點(diǎn)圓周卷積 是線性卷積以是線性卷積以L為周期的周期為周期的周期延拓序列的主值序列。延拓序列的主值序列。 若若 ，則，則L點(diǎn)圓周卷積能代表線性卷積。點(diǎn)圓周卷積能代表線性卷積。 12( )( )( )y nx nx

17、 n12( ),( )x nx n12,LNLN11221212( ), 01( ), 01( ),( )0, 10, 1x nnNx nnNx nx nNnLNnL1120( )( )()( )()( )LLLlLmry nx m xnmR ny nrlR n( )y n121LNN2021-11-11大連理工大學(xué)27 離散傅里葉變換的逆變換離散傅里葉變換的逆變換逆變換與正變換的區(qū)別：逆變換與正變換的區(qū)別： 有系數(shù)有系數(shù) 指數(shù)有負(fù)號(hào)指數(shù)有負(fù)號(hào)具體應(yīng)用時(shí)：具體應(yīng)用時(shí)： 10101IDFT( )( ),0,1,1DFT( )( ),0,1,1NnkNkNnkNnx nX kX k WnNNX k

18、x nx k WkN1/ NnknkNNWW *1*011( )DFT( )NnkNnx nXk WXkNN2021-11-11大連理工大學(xué)288.3 與與DFT有關(guān)的幾個(gè)問(wèn)題有關(guān)的幾個(gè)問(wèn)題2021-11-11大連理工大學(xué)29 1.1.頻率分辨率及頻率分辨率及DFTDFT參數(shù)的選擇參數(shù)的選擇 分辨率分辨率 時(shí)間分辨率時(shí)間分辨率：通過(guò)時(shí)窗所看到時(shí)間的寬度：通過(guò)時(shí)窗所看到時(shí)間的寬度； 頻率分辨率頻率分辨率：通過(guò)頻窗所看到頻率的寬度：通過(guò)頻窗所看到頻率的寬度；或能或能將信號(hào)中兩個(gè)靠的很近的頻譜分開的能力。將信號(hào)中兩個(gè)靠的很近的頻譜分開的能力。 頻率分辨率分析頻率分辨率分析 設(shè)信號(hào)設(shè)信號(hào) ，時(shí)長(zhǎng)為，時(shí)

19、長(zhǎng)為T秒，其傅里葉變換的秒，其傅里葉變換的 頻率分辨率為頻率分辨率為： 將將 抽樣為抽樣為 ，采樣點(diǎn)數(shù)：，采樣點(diǎn)數(shù)：( )Tx t(j )TX1/ (Hz)fT ( )Tx t( )Mxn1,sssTMfTT2021-11-11大連理工大學(xué)30經(jīng)過(guò)經(jīng)過(guò)DTFT（假設(shè)用矩形窗），（假設(shè)用矩形窗），頻率分辨率仍為頻率分辨率仍為：序列長(zhǎng)度對(duì)分辨率的影響：序列長(zhǎng)度對(duì)分辨率的影響： 由于由于 ，故若，故若 不變，會(huì)引起不變，會(huì)引起 ； 這相當(dāng)于使數(shù)據(jù)長(zhǎng)度這相當(dāng)于使數(shù)據(jù)長(zhǎng)度 ，或，或 。 若若T不能不能增加，則可：增加，則可：對(duì)對(duì) 的分點(diǎn)加密（插值）；的分點(diǎn)加密（插值）；在在 后面補(bǔ)后面補(bǔ)0 0。11ss

20、ffMMTT sffM ,sMff ()sTTMTM ( )X k( )Mxn2021-11-11大連理工大學(xué)31 說(shuō)明：說(shuō)明： 以上方法（頻域插值或時(shí)域補(bǔ)以上方法（頻域插值或時(shí)域補(bǔ)0）可使）可使 ，但不能改善分辨率但不能改善分辨率，原因是，原因是M（或（或T）未變。）未變。 在信號(hào)處理的實(shí)際應(yīng)用中，往往在信號(hào)處理的實(shí)際應(yīng)用中，往往M和和T不能不能改變了；改變了； 這時(shí)需要發(fā)展新的信號(hào)處理方法來(lái)改善分辨這時(shí)需要發(fā)展新的信號(hào)處理方法來(lái)改善分辨率，例如現(xiàn)代譜估計(jì)等。率，例如現(xiàn)代譜估計(jì)等。f 2021-11-11大連理工大學(xué)32 舉例舉例 【例例8.2】 設(shè)設(shè) 的最高頻率的最高頻率 ，采樣頻率，采樣

21、頻率 設(shè)信號(hào)時(shí)長(zhǎng)設(shè)信號(hào)時(shí)長(zhǎng) ，即采樣得的信號(hào)點(diǎn)數(shù)為，即采樣得的信號(hào)點(diǎn)數(shù)為256點(diǎn)點(diǎn)。對(duì)對(duì) 做做DFT時(shí)，時(shí)， 。 【解解】：( )x t3Hzcf 10Hz, 0.1ssfTs25.6Ts( )x n?f 100.0390625Hz256sffM 2021-11-11大連理工大學(xué)33 【例例8.3】 條件同條件同【例例8.1】，若：，若： 且：且： 問(wèn)：用問(wèn)：用DFT求頻譜時(shí)，可否分辨這三個(gè)頻率。求頻譜時(shí)，可否分辨這三個(gè)頻率。 【解解】：因：因： 故：不能分辨故：不能分辨 ，可以分辨，可以分辨 。 若加長(zhǎng)數(shù)據(jù)，即令若加長(zhǎng)數(shù)據(jù)，即令N=1024，T=10240.1=102.4s 則：則： 故：可

22、以分辨故：可以分辨 。 見程序演示見程序演示 【fenbian.m】( )x t( )x n123( )sin(2)sin(2)sin(2)x tf tf tf t1232Hz 2.02Hz 2.07Hzfff，210.02Hz0.039Hzfff 2f3f100.01Hz1024sffN 210.02Hz0.01Hzfff 2f2021-11-11大連理工大學(xué)34 在應(yīng)用中需要注意的問(wèn)題：在應(yīng)用中需要注意的問(wèn)題：若信號(hào)最高頻率為若信號(hào)最高頻率為 ，則需滿足：，則需滿足： 根據(jù)需要的根據(jù)需要的 來(lái)選擇數(shù)據(jù)長(zhǎng)度來(lái)選擇數(shù)據(jù)長(zhǎng)度N： 對(duì)應(yīng)的時(shí)間長(zhǎng)度：對(duì)應(yīng)的時(shí)間長(zhǎng)度： cf2scfffsfNfssNT

23、NTf2021-11-11大連理工大學(xué)35 2.2.信號(hào)補(bǔ)信號(hào)補(bǔ)0 0問(wèn)題問(wèn)題 補(bǔ)零不能提高分辨率，因?yàn)檠a(bǔ)零未對(duì)原始信號(hào)增加補(bǔ)零不能提高分辨率，因?yàn)檠a(bǔ)零未對(duì)原始信號(hào)增加新信息；新信息； 但補(bǔ)零可使數(shù)據(jù)但補(bǔ)零可使數(shù)據(jù)N為為2的整次冪，以便的整次冪，以便FFT的使用；的使用； 補(bǔ)零可對(duì)補(bǔ)零可對(duì) 插值；插值； 插值有助于緩解頻譜泄漏。插值有助于緩解頻譜泄漏。 【例例】見程序演示見程序演示 【buling.m】( )X k2021-11-11大連理工大學(xué)36 應(yīng)用舉例應(yīng)用舉例 【例例8.48.4】：補(bǔ)補(bǔ)0 0的效果的效果三個(gè)信號(hào)頻率：三個(gè)信號(hào)頻率：1232.67Hz 3.75Hz 6.75Hzfff，

24、2021-11-11大連理工大學(xué)37 【例例8.48.4續(xù)續(xù)】由圖由圖(a)(a)，不能看出有幾個(gè)頻率；，不能看出有幾個(gè)頻率；由圖由圖(b)(b)，補(bǔ)，補(bǔ)N N個(gè)個(gè)0 0，仍不明顯；，仍不明顯；由圖由圖(c)(c)，補(bǔ)，補(bǔ)7N7N個(gè)個(gè)0 0，效果比較顯著，基本可以分辨，效果比較顯著，基本可以分辨三個(gè)信號(hào)頻率；三個(gè)信號(hào)頻率；由圖由圖(d)(d)，補(bǔ)，補(bǔ)29N29N個(gè)個(gè)0 0，效果明顯。，效果明顯。2021-11-11大連理工大學(xué)38 3. 信號(hào)的時(shí)寬與頻寬問(wèn)題信號(hào)的時(shí)寬與頻寬問(wèn)題 信號(hào)的時(shí)寬與頻寬不可能同時(shí)縮小，也不可能同時(shí)擴(kuò)大信號(hào)的時(shí)寬與頻寬不可能同時(shí)縮小，也不可能同時(shí)擴(kuò)大（例：（例：FT的比

25、例變換性質(zhì)）的比例變換性質(zhì)） ； 信號(hào)的時(shí)寬與頻寬也不能同時(shí)為有限值信號(hào)的時(shí)寬與頻寬也不能同時(shí)為有限值（例：矩形）（例：矩形）； 時(shí)寬和頻寬的測(cè)量方法：時(shí)寬和頻寬的測(cè)量方法： 方法方法1： 要求：要求： 是實(shí)對(duì)稱、非遞增的信號(hào)。有：是實(shí)對(duì)稱、非遞增的信號(hào)。有： 方法方法2： 不定原理：不定原理： uncertainty principle ( )iz t/211/2( )/ (0),( )d /(0)ssffnTWx nxFWX ffX( )x n/2/22222222222/2/2()| ( )| /| ( )| ,()|( )| d /|( )| dssssffffnnTWnx nx nF

26、WfX ffX ff2214TW FW111TW FW 2021-11-11大連理工大學(xué)39 4. 二維傅里葉變換二維傅里葉變換 二維二維DTFT： 二維二維DFT121 11 212121 11 2jjj12jjjj12122(e,)(,)ee1(,)(e,e)eedd(2 )jnnnnnnXex n nx n nX 121 12 212121 12 2122211jj12121122002211jj121211220012( ,)(,)ee,0,1,0,11(,)( ,)ee,0,1,0,1NNn kn kNNnnNNn kn kNNkkX k kx n nkNkNx n nX k knN

27、nNN N 2021-11-11大連理工大學(xué)40 5. 頻譜泄漏問(wèn)題頻譜泄漏問(wèn)題 頻譜泄漏的含義：頻譜泄漏的含義：截?cái)嘈盘?hào)的能量擴(kuò)散到無(wú)窮寬的截?cái)嘈盘?hào)的能量擴(kuò)散到無(wú)窮寬的頻帶中去，稱為頻譜泄漏。頻帶中去，稱為頻譜泄漏。 頻譜泄漏的原因：頻譜泄漏的原因： 在實(shí)際應(yīng)用中，觀測(cè)信號(hào)總是要限制在一定的時(shí)在實(shí)際應(yīng)用中，觀測(cè)信號(hào)總是要限制在一定的時(shí)間范圍內(nèi)。間范圍內(nèi)。 這相當(dāng)于信號(hào)這相當(dāng)于信號(hào) 與矩形窗函數(shù)與矩形窗函數(shù) 相乘。相乘。 時(shí)域乘積對(duì)應(yīng)于頻域卷積，卷積的結(jié)果使時(shí)域乘積對(duì)應(yīng)于頻域卷積，卷積的結(jié)果使 的頻譜的頻譜 發(fā)生了變化發(fā)生了變化 。 1( )x n( )w n1( )x nj1(e )Xj2(

28、e )X2021-11-11大連理工大學(xué)41 頻譜泄漏的圖示：頻譜泄漏的圖示：2021-11-11大連理工大學(xué)42頻譜泄漏的危害頻譜泄漏的危害泄漏的危害：泄漏的危害：使頻譜的分辨率下降；使頻譜的分辨率下降； 在頻譜中引入虛假的頻率分量（由窗引起）。在頻譜中引入虛假的頻率分量（由窗引起）。減小泄漏的方法：減小泄漏的方法： 取更長(zhǎng)的數(shù)據(jù)，即增加窗寬；取更長(zhǎng)的數(shù)據(jù)，即增加窗寬；數(shù)據(jù)不要突然截?cái)啵床灰匦未?，加各種緩變數(shù)據(jù)不要突然截?cái)?，即不要矩形窗，加各種緩變窗，使窗旁瓣的能量更小。窗，使窗旁瓣的能量更小。 2021-11-11大連理工大學(xué)43 6. 柵欄效應(yīng)柵欄效應(yīng) 概念：概念：因因DFT的譜是限

29、制在離散點(diǎn)上的頻譜，是一的譜是限制在離散點(diǎn)上的頻譜，是一種限制為基頻種限制為基頻 整數(shù)倍處的譜，而不是連續(xù)的頻整數(shù)倍處的譜，而不是連續(xù)的頻譜。就像通過(guò)譜。就像通過(guò)“柵欄柵欄”觀看景象一樣，只能在離散觀看景象一樣，只能在離散點(diǎn)處看到真實(shí)景象，稱為柵欄效應(yīng)。點(diǎn)處看到真實(shí)景象，稱為柵欄效應(yīng)。 02021-11-11大連理工大學(xué)44 減小柵欄效應(yīng)的方法減小柵欄效應(yīng)的方法 增加頻域采樣點(diǎn)數(shù)增加頻域采樣點(diǎn)數(shù)N； 在不改變時(shí)域數(shù)據(jù)的情況下，補(bǔ)在不改變時(shí)域數(shù)據(jù)的情況下，補(bǔ)0； 頻率采樣為頻率采樣為 ，隨著，隨著N增大，導(dǎo)致采樣點(diǎn)增大，導(dǎo)致采樣點(diǎn)更近，譜線更密。更近，譜線更密。 2kN2021-11-11大連理

30、工大學(xué)45 7. 頻率混疊問(wèn)題頻率混疊問(wèn)題 由采樣定理：由采樣定理： 若采樣定理不滿足，則產(chǎn)生混疊，即頻率響應(yīng)周期若采樣定理不滿足，則產(chǎn)生混疊，即頻率響應(yīng)周期延拓分量互相重疊。延拓分量互相重疊。 若信號(hào)的頻譜無(wú)限寬，則需要抗混疊濾波器進(jìn)行預(yù)若信號(hào)的頻譜無(wú)限寬，則需要抗混疊濾波器進(jìn)行預(yù)處理。處理。 可選占信號(hào)能量可選占信號(hào)能量98%左右的頻帶寬度的左右的頻帶寬度的 作為信作為信號(hào)的最高頻率，從而進(jìn)一步確定采樣頻率號(hào)的最高頻率，從而進(jìn)一步確定采樣頻率 。 max2sffmaxfsf2021-11-11大連理工大學(xué)468.4 快速傅里葉變換（快速傅里葉變換（FFTFFT）2021-11-11大連理工

31、大學(xué)47 0. 引言：引言： 【DFTDFT算法的計(jì)算量算法的計(jì)算量】 N點(diǎn)點(diǎn)DFT的復(fù)乘法次數(shù)的復(fù)乘法次數(shù)： ；加法次數(shù)：加法次數(shù)： 若若 ，則復(fù)乘法次數(shù)，則復(fù)乘法次數(shù)1048576次，次， 折合實(shí)數(shù)乘折合實(shí)數(shù)乘法法4194304次。次。10102( )( ),0,1,1( )( ),0,1,1NnkNnNnkNkjNNX kx n WkNx nX k WnNWe2N(1)N N 1024N 2021-11-11大連理工大學(xué)48 【FFTFFT算法的出現(xiàn)算法的出現(xiàn)】 1965年，庫(kù)利（年，庫(kù)利（J.W.Cooley）和圖基（）和圖基（J.W.Tukey）在在Mathematics of Co

32、mputation上發(fā)表論文，提出上發(fā)表論文，提出了一種了一種DFT的快速計(jì)算法。的快速計(jì)算法。 后來(lái)又經(jīng)過(guò)不斷完善和發(fā)展，形成后來(lái)又經(jīng)過(guò)不斷完善和發(fā)展，形成FFT。 FFT算法的計(jì)算量：算法的計(jì)算量： FFT出現(xiàn)，才使傅里葉變換的理論方法得以方便地出現(xiàn)，才使傅里葉變換的理論方法得以方便地實(shí)現(xiàn)。實(shí)現(xiàn)。 可以說(shuō)，可以說(shuō)，F(xiàn)FT有力地推動(dòng)了傅里葉理論方法的發(fā)展。有力地推動(dòng)了傅里葉理論方法的發(fā)展。 22log2NNN2021-11-11大連理工大學(xué)49 【DFTDFTFFTFFT的一個(gè)特例的一個(gè)特例】定義定義 矩陣：矩陣： 定義信號(hào)矢量與頻譜矢量定義信號(hào)矢量與頻譜矢量NW000001210242(1

33、)012(1)(1)(1)NnkNNNNNNWWWWWWWWWWWWWWWWWWTT(0)(1)(1) (0)(1)(1)NNXXX Nxxx NXx10( )( ),0,1,1NnkNnX kx n WkN2021-11-11大連理工大學(xué)50這樣，這樣，離散傅里葉變換（離散傅里葉變換（DFT）可以寫成矩陣形式，）可以寫成矩陣形式，如下：如下： 的特點(diǎn)與性質(zhì)：的特點(diǎn)與性質(zhì)： 利用上述周期性和對(duì)稱性，利用上述周期性和對(duì)稱性，4點(diǎn)點(diǎn)DFT可以寫為：可以寫為： NNNXW xNW0/21,1;NNNWW /2,NrrNrrNNNNWWWW 1111(0)1111(0)(1)11(1)(2)1111(

34、2)(3)11(3)XxXWWxXxXWWx2jeNNW2021-11-11大連理工大學(xué)51 將上述矩陣的第將上述矩陣的第2列與第列與第3列交換，有列交換，有 這樣，有：這樣，有：1111(0)1111(0)(1)11(2)(2)1111(1)(3)11(3)XxXWWxXxXWWx11(0) (0)(2) (1)(3)(1) (0)(2) (1)(3)(2) (0)(2) (1)(3)(3) (0)(2) (1)(3)NNXxxxxXxxxxWXxxxxXxxxxW2021-11-11大連理工大學(xué)52比較計(jì)算量：比較計(jì)算量：DFT算法的計(jì)算量：算法的計(jì)算量： 次復(fù)數(shù)乘法；次復(fù)數(shù)乘法；FFT算

35、法的計(jì)算量：只需算法的計(jì)算量：只需1次復(fù)數(shù)乘法。次復(fù)數(shù)乘法。24162021-11-11大連理工大學(xué)53 1. 直接計(jì)算直接計(jì)算DFTDFT的問(wèn)題和改進(jìn)途徑的問(wèn)題和改進(jìn)途徑 DFT的正變換與逆變換式的差別很小，僅兩點(diǎn)：的正變換與逆變換式的差別很小，僅兩點(diǎn)： 的指數(shù)符號(hào)；乘法因子的指數(shù)符號(hào)；乘法因子 。僅考慮正變換。僅考慮正變換。 【可以用于減小可以用于減小DFTDFT計(jì)算量的特性計(jì)算量的特性】 具有共軛對(duì)稱性：具有共軛對(duì)稱性： 具有周期性：具有周期性： 具有可約性：具有可約性： 并且，并且，NW1/ NnkNW*nknkNNWWnkNWnkNWn N kkN nnkNNNWWW/,nkmnkn

36、knk mNmNNN mWWWW()()/22,1,Nkn N kk N nnkNkNNNNNNWWWWWW 2021-11-11大連理工大學(xué)54 【上述特性的利用上述特性的利用】 DFT運(yùn)算中的有些項(xiàng)可以合并；運(yùn)算中的有些項(xiàng)可以合并； 利用利用 的對(duì)稱性、周期性和可約性，可以將長(zhǎng)序的對(duì)稱性、周期性和可約性，可以將長(zhǎng)序列的列的DFT分解為短序列的分解為短序列的DFT； 越小，越有利于計(jì)算量的減小。越小，越有利于計(jì)算量的減小。 nkNWN2021-11-11大連理工大學(xué)55 2.2.按時(shí)間抽選的基按時(shí)間抽選的基2FFT2FFT算法算法 【算法原理算法原理】：設(shè)序列點(diǎn)數(shù)設(shè)序列點(diǎn)數(shù) ， 為正整數(shù)。為

37、正整數(shù)。 將將 先按先按 的的奇偶分成兩組奇偶分成兩組： 這樣，可將這樣，可將DFT化為：化為： 2LN L( ), (0,1,1)x nnN121 (2 )( )0,1,122 (21)( )x rx rNrx rx r 111000(/2) 1(/2) 1(2r)(2r+1)00(/2) 1(/2) 1221200( )DFT( )( )( )+( )=(2 )+(21)=( )+( )NNNnknknkNNNnnnnnNNkkNNrrNNrkrkkNNNrrX kx nx n Wx n Wx n Wxr WxrWx rWWx rW（ 為偶數(shù)）（ 為奇數(shù)）n2021-11-11大連理工大學(xué)

38、56 按時(shí)間抽選的基按時(shí)間抽選的基2 FFT2 FFT算法（續(xù)）算法（續(xù)） 【算法原理算法原理】（續(xù)）：（續(xù)）： 根據(jù)根據(jù) ，上式表示為：，上式表示為： 其中其中 和和 分別是分別是 和和 的的 點(diǎn)點(diǎn)DFT。 這樣：這樣：22j2j2/2/2=e=eNNNNWW(/2) 1(/2) 11/212/2020( )()()( )kNNrkkrkNrNNNrX kx r WWx rX kWWXk1( )X k2( )Xk1( )x r2( )xr/2N(/2) 1(/2) 111/2/200(/2) 1(/2) 122/2/200( )( )(2 )0,1,12( )( )(21)0,1,12NNr

39、krkNNrrNNrkrkNNrrNX kx r Wxr WkNXkx r WxrWk，2021-11-11大連理工大學(xué)57 按時(shí)間抽選的基按時(shí)間抽選的基2 FFT2 FFT算法（續(xù)算法（續(xù)2 2） 【算法原理算法原理】（續(xù)（續(xù)2 2）：）： 說(shuō)明：說(shuō)明：一個(gè)一個(gè) 點(diǎn)點(diǎn)DFT已分解為兩個(gè)已分解為兩個(gè) 點(diǎn)的點(diǎn)的DFT；再進(jìn)行組合成再進(jìn)行組合成 點(diǎn)點(diǎn)DFT（上頁(yè)（上頁(yè)紅色紅色部分，前半段）。部分，前半段）。 再利用系數(shù)的周期性：再利用系數(shù)的周期性： 則有：則有： （藍(lán)色藍(lán)色部分，后半段）部分，后半段） 這樣，前半段這樣，前半段 和后半段和后半段 的的數(shù)據(jù)都做了數(shù)據(jù)都做了DFT。 頻譜的后半段與前半

40、段相等頻譜的后半段與前半段相等。N/2NN()2/2/2Nr krkNNWW(/2) 1(/2) 1/21/21/2022011( )2( )( )2( )NNr NkrkNNrrx r Wx rNXkX kNXkXWk0,1,12N,12NN2021-11-11大連理工大學(xué)58 按時(shí)間抽選的基按時(shí)間抽選的基2 FFT2 FFT算法（續(xù)算法（續(xù)3 3） 【算法原理算法原理】（續(xù)（續(xù)3 3）：）： 再考慮性質(zhì)：再考慮性質(zhì)： 則前半段：則前半段： 后半段：后半段： 即只要求出前半段即只要求出前半段 和和 ，就可以得到完整，就可以得到完整的的 ，節(jié)省計(jì)算量。，節(jié)省計(jì)算量。 ()22NNkkkNNNN

41、WWWW 2121( )( ),( )( )( ),00,1,122,1,12kNkNNNX kX kW XNX kX kW Xkkkk1( )X k2( )Xk( )X k2021-11-11大連理工大學(xué)59 按時(shí)間抽選的基按時(shí)間抽選的基2 FFT2 FFT算法（續(xù)算法（續(xù)4 4） 【蝶形信號(hào)流圖蝶形信號(hào)流圖】：上述算法可用下面的蝶形流圖表示。上述算法可用下面的蝶形流圖表示。1212( )( )( ),0,1,12( )( ),0,1,122kNkNNX kX kW XkkNNX kX kW Xkk2021-11-11大連理工大學(xué)60 N=8N=8的蝶形信號(hào)流圖：的蝶形信號(hào)流圖：2021-1

42、1-11大連理工大學(xué)61 按時(shí)間抽選的基按時(shí)間抽選的基2FFT2FFT算法（續(xù)算法（續(xù)5 5） 由于由于 仍為偶數(shù)，還可以繼續(xù)分解。仍為偶數(shù)，還可以繼續(xù)分解。將每個(gè)將每個(gè) 的子序列再按照奇部、偶部分解為兩個(gè)的子序列再按照奇部、偶部分解為兩個(gè) 子序列。子序列。例如：例如：將將 分解如下：分解如下： 這樣：/2N/2N/4N1( )x r1314(2 )( )0,1,1(21)( )4xlx lNlxlx l(/4 1)(/4 1)21211/21/200(/4 1)(/4 1)3/4/24/4003/2413/24( )(2 )(21)( )( )0,1,14( )( )( )( )4NNlkl

43、kNNllNNlkklkNNNllkNkNX kxl WxlWx l WWx l WNkXkWXkNXkXkWXk2021-11-11大連理工大學(xué)62 按時(shí)間抽選的基按時(shí)間抽選的基2FFT2FFT算法（續(xù)算法（續(xù)6 6） 這樣：這樣：(/4 1)(/4 1)21211/21/200(/4 1)(/4 1)3/4/24/4003/2413/24( )(2 )(21)( )( )0,1,14( )( )( )( )4NNlklkNNllNNlkklkNNNllkNkNX kxl WxlWx l WWx l WNkXkWXkNXkXkWXk2021-11-11大連理工大學(xué)63 按時(shí)間抽選的基按時(shí)間抽

44、選的基2FFT2FFT算法（續(xù)算法（續(xù)6 6） 對(duì)對(duì) 也可以繼續(xù)分解，有：也可以繼續(xù)分解，有：由由2 2個(gè)個(gè)N/4N/4點(diǎn)點(diǎn)DFTDFT組合的組合的N/2N/2點(diǎn)點(diǎn)DFTDFT：2( )x r25/2625/26( )( )( )0,1,14( )( )4kNkNXkXkWXkNkNXkXkWXk2021-11-11大連理工大學(xué)64 按時(shí)間抽選的基按時(shí)間抽選的基2FFT2FFT算法（續(xù)算法（續(xù)6 6） 將系數(shù)統(tǒng)一為將系數(shù)統(tǒng)一為 ，則一個(gè)，則一個(gè)8點(diǎn)的點(diǎn)的DFT可以分解可以分解為為4個(gè)個(gè)N/4點(diǎn)點(diǎn)DFT，如圖，如圖。一直一直分解分解到到2點(diǎn)數(shù)據(jù)為止點(diǎn)數(shù)據(jù)為止。2/2kkNNWW2021-11-1

45、1大連理工大學(xué)65 【完整的完整的8 8點(diǎn)點(diǎn)FFTFFT流圖流圖】2021-11-11大連理工大學(xué)66 【運(yùn)算量問(wèn)題運(yùn)算量問(wèn)題】 當(dāng)數(shù)據(jù)長(zhǎng)度當(dāng)數(shù)據(jù)長(zhǎng)度 ，需要計(jì)算量：，需要計(jì)算量： 復(fù)數(shù)乘法：復(fù)數(shù)乘法： 復(fù)數(shù)加法：復(fù)數(shù)加法： DFT與與FFT計(jì)算量之比計(jì)算量之比：2LN 2log22FNNmLN2logFaNLNN22222loglog22NNNNNNLN2021-11-11大連理工大學(xué)67 【時(shí)間抽取時(shí)間抽取FFTFFT算法的特點(diǎn)算法的特點(diǎn)】 原位計(jì)算（同址計(jì)算），節(jié)省存儲(chǔ)空間。原位計(jì)算（同址計(jì)算），節(jié)省存儲(chǔ)空間。 倒位序規(guī)律。倒位序規(guī)律。1111( )( )( )( )( )( )rmmm

46、NrmmmNXkXkXj WXjXkXj W2021-11-11大連理工大學(xué)68 【時(shí)間抽取時(shí)間抽取FFTFFT算法的特點(diǎn)算法的特點(diǎn)】 蝶形運(yùn)算兩節(jié)點(diǎn)的距離：蝶形運(yùn)算兩節(jié)點(diǎn)的距離： 第第1段段1 第第2段段2 第第3段段4 第第m段段 12m2021-11-11大連理工大學(xué)69 【按時(shí)間抽選的按時(shí)間抽選的FFTFFT算法的其他形式流圖算法的其他形式流圖】（略）（略）FFTFFT算法按時(shí)間抽取還有許多其他算法，請(qǐng)同學(xué)們自算法按時(shí)間抽取還有許多其他算法，請(qǐng)同學(xué)們自行參考相關(guān)書籍進(jìn)行學(xué)習(xí)。行參考相關(guān)書籍進(jìn)行學(xué)習(xí)。2021-11-11大連理工大學(xué)70 按頻率抽選的基按頻率抽選的基2FFT2FFT算法算法 設(shè)設(shè) ，把，把 換為奇偶分組，有：換為奇偶分組，有： 繼續(xù)以此分解，最后，有：繼續(xù)以此分解，最后，有： 2LN ( )X k11120021122200120( ) ,0,1,12