第三章 離散傅立葉變換 - 重慶三峽學(xué)院

1、第三章 離散傅立葉變換DFTDFT是重要的變換1.分析有限長序列的有用工具2.在信號處理的理論上有重要意義3.在運(yùn)算方法上起核心作用，譜分析、卷積、相關(guān)都可以通DFT在計(jì)算機(jī)（或DSP）上實(shí)現(xiàn)。DFT定義DFT是現(xiàn)代信號處理橋梁DFT要解決兩個問題：一是離散與量化，二是快速運(yùn)算傅氏變換離散量化DFT(FFT)信號處理DFT定義210210( ) ( )( ) 0,1,.1,1( ) ( )( ) 0,1,.1,NjknNnNjknNkX kDFS x nx n ekNx nIDFS X kX k enNN其它周期延拓其它周期延拓2jNNWe令2110021100( )( )( )( )11(

2、)( )( )( )NNjnknkNNnnNNjnknkNNkkX kDFS x nx n ex n Wx nIDFS X kX k eX k WNNx(nT)=x(n)001TFt0T 2T1 2 N 0TNTn0002 0 1 2 3)1()1(0NNNN0k)()(0kxexTjk TfTss120NsFTp220NTDFT定義DFT定義預(yù)備知識1.余數(shù)運(yùn)算表達(dá)式如果1nnmN101Nnm為整數(shù)；則有：1Nnn 1N()NNNmnnnnn1此運(yùn)算表示n被 除，商為 ，余數(shù)為 。是的解，或稱為取余數(shù)， 對 取模值，簡稱取模， 模 。DFT定義例如：7252792259,2591nNnNn5

3、455949,49NnNnDFT定義 含義1nxnxN11x nxnx nN先取模值，后進(jìn)行函數(shù)運(yùn)作。( )= ( )，視作將 ( )周期延拓DFT定義( )( )x nx n有限長序列與周期序列的關(guān)系 ( )()Nmx nx nmNxnxx周期序列 (n)是有限長序列 (n)的周期延拓。( )01( )0 x nnNx n其它( )( )( )Nx nx n Rn 或( )( )x nx n有限長序列與周期序列的主值序列DFT定義如：N-1nx(n)0.n)(nx0N-1DFT定義10)()()(NnnkNWnxnxDFSkX10)(1)()(NknkNWkXNkXIDFSnx 從上式可知，

4、DFS,IDFS的求和只限定在n=0到n=N-1,及k=0到N-1的主值區(qū)間 進(jìn)行。 因此可得到新的定義，即有限序的離散傅氏變換(DFT)的定義。DFT定義( )( )( )( )( )( )NNX kX k Rkx nx n Rn或：1010)(1)()()()()(NknkNNnnkNWkXNkXIDFTnxWnxnxDFTkX, 0kN-1, 0nN-1DFT定義DFT的物理含義1010( ) ( )( )( ) ( )( ) 0,1.1NnnNknNnX zZT x nx n zX kDFT x nx n WkN 0,1,.1 0,1,.1kkkkNkkN2jNj2=NX( )=X(z

5、)|z=e或X( )=X(e)|( )DFTZNDTFT-)Nx nj即：的是x(n)的 變換在單位圓上的 點(diǎn)等間隔采樣；或X(k)為x(n)的X(e在區(qū)間0,2 上的 點(diǎn)等間隔采樣。DFT定義N=8N=16()jX e( )X k( )X kDFT的性質(zhì)線性1122( )( )N( )( )DFT x nX kDFT x nXk1、兩序列都是 點(diǎn)時(shí)，如果：1212( )( )( )( )DFT ax nbx naX kbXk則有：12122( )( )N Nx nx n、和的長度不等12max,NNN N選擇為變換長度，短者進(jìn)行補(bǔ)零達(dá)到 點(diǎn)。DFT的性質(zhì)序列的圓周移位( )x n一個有限長序

6、列的圓周移位定義為： ( )mNNxnxnmRn這里包含三層意思： ( )( )Nx nx nxn（1）、先將進(jìn)行周期延拓2()Nx nmxnm（ ）、再進(jìn)行移位： 3( )mNNxnxnmRn（ ）、最后取主值序列：DFT的性質(zhì)n)(nx0N-1nNnxnx)()(0周期延拓nNnxnx2)2(0左移2n)()2(nRnxNN0取主值N-1DFT的性質(zhì)圓周位移的含義( )N( )( )x nx nx n由于我們?nèi)≈髦敌蛄?，即只觀察n=0到n=N-1這一主值區(qū)間，當(dāng)某一抽樣從從此區(qū)間一端移出時(shí)，與它相同值的抽樣又從此區(qū)間的另一端進(jìn)來。如果把排等分的圓周圓周移列在一個上，序列的移位就相當(dāng)于在圓上

7、旋轉(zhuǎn)，故稱為。當(dāng)圍著圓周觀察幾圈時(shí)，看到的就是周期序列位。DFT的性質(zhì)12345n=0N=6左移順時(shí)DFT的性質(zhì) ( ) 01,( )( )( )( )mNNmkmmNNNx nnNxnxnmRnXkDFT xnDFT xnmRnWX k有限長序列，若則： 2( ) 01,( ) ( )( )( )jnlnlNNNNX kkNX kDFT x nDFT xklRnW x nex n同樣：有限長序列，若則：IDFT的性質(zhì) 共扼對稱性 1.周期序列共軛對稱分量與共軛反對稱分量 周期為N的周期序列的共軛對稱分量與共軛反對 稱分量分別定義為*11( ) ( )() ( )() 2211( ) ( )(

8、) ( )() 22eNNoNNxnx nxnxnxNnxnx nxnxnxNn*( )( )( ) ( )() ( )()eoeeoox nx nx nx nxnx nxn 同樣有：DFT的性質(zhì)2.有限長序列的圓周共軛對稱分量與圓周共軛反對稱分量 有限長序列的圓周共軛對稱分量與圓周共軛反對稱分量分別定義為*1( )( )( ) ( )() ( )21( )( )( ) ( )() ( )2epeNNNNopoNNNNxnx n Rnx nxNnRnxnxn Rnx nxNnRn( )( )( )( )( )( )( )( )( )( ) ( )( )( )NeoNeNoNepopx nx n

9、 Rnx nx n Rnx n Rnx n Rnx nxnxn由于： 所以有：N即：長為 的有限長序列可以分解為兩個長度相同的分量。DFT的性質(zhì)3、共扼對稱特性之一*( ) ( )( )()( )()( )NNNNX kDFT x nDFT xnXkRkXNkRk如果，則1*011*001()*0( )( )( )( )( )( )( )( )( )()( )NnkNNnNNnkNnnkNNNNNnnNN k nNNNNnDFT x nx n WRkx n WRkx n WWRkx n WRkXNkRk證明：DFT的性質(zhì)4、共扼對稱特性之二*( ) ( )()( )( )NNX kDFT x

10、nDFT xnRnXk如果，則1*0(1)1*001*0*()( )()( )()( )( )( )( )()( ) ( ()( )( )NnkNNNNNnNNnknkNNNnnNnkNnNNNNDFT xnRnxnRn WxnWx n Wx n WXkx nXkRkxnRnXk證利用周期性）明：可知：DFT的性質(zhì)5、共扼對稱特性之三*( ) ( )Re ( )1( )() ( )( )2NNNepX kDFT x nDFTx nXkXNkRkXk如果，則*1Re ( ) ( )( )21Re ( ) ( )( )21( )()( )21( )() ( )( )2NNNNNepx nx nx

11、nDFTx nDFT x nDFT x nX kXNkRkXkXNkRkXk證明：*DFTDFT復(fù)數(shù)序列實(shí)部的該序列的圓周共軛對稱分量。DFT的性質(zhì)6、共扼對稱特性之四*( ) ( ) Im ( )1( )() ( )( )2NNNopX kDFT x nDFTjx nXkXNkRkXk如果，則*1Im ( ) ( )( )21 Im ( ) ( )( )21( )()( )21( )() ( )( )2NNNNNopjx nx nx nDFT jx nDFT x nDFT x nX kXNkRkXkXNkRkXk證明：*jDFTDFT復(fù)數(shù)序列虛部乘以 的該序列的圓周共軛反對稱分量。DFT的性

12、質(zhì)7、共扼對稱特性之五、六Re( )( )Im( )( )epopX kDFT xnjX kDFT xn同樣，可證明：，8.X(k)圓周共軛對稱分量與圓周共軛反對稱分量的對稱性(1)( )( )( )epopX kXkXk、*(2)( )()()( )()( )(3)( )()()( )()( )epepepNNepNNopopopNNopNNXkXkXkRkXNkRkXkXkXkRkXNkRk 、 DFT的性質(zhì)9.實(shí)、虛序列的對稱特性 當(dāng)x(n)為實(shí)序列時(shí)，根據(jù)特性之三，則 X(k)=Xep(k)又據(jù)Xep(k)的對稱性：*( )()( )epepNNXkXNkRk 當(dāng)x(n)為純虛序列時(shí)，

13、根據(jù)特性之四，則 X(k)=Xop(k)又據(jù)Xop(k)的對稱性：*( )(N)( )opopNNXkXkRk*( )()( )NNX kXNkRk*( )(N)( )NNX kXkRk DFT的性質(zhì)圓周卷積和1、時(shí)域卷積定理12112212( )( )N( )( )( )( )( )( )( )x nx nDFT x nX kDFT x nXkY kX kXk設(shè)和均為長度為 的有限長序列，且有：，。如果：，則有： )()()()(11021nxnRmnxmxkYIDFTnyNNmNN)(2nx)()()(21012nxnRmnxmxNNmNN)(1nx證明：相當(dāng)于將 作周期卷積和后，再取主值

14、序列。將 周期延拓則：12( ),( )x n x n( )y k12( )( )Y kX k Xk（ ）11201120( ) ( )()()()NmNNNmy nIDFS Y kx m xnmx mxnm在主值區(qū)間 ，所以：)()(, 1011mxmxNmN )()()()()(11021nxnRmnxmxnRnynyNNmNNN)(2nx同樣可證：)()()()(21012nxnRmnxmxnyNNmNN)(2nx2.時(shí)域圓周卷積過程N(yùn)-10n)(1nxN-10)(2nx)(0)(22mRmxmxNN0m)(12mRmxNN0m)(22mRmxNN0m)(32mRmxNN0m1)6(0)

15、5(1)4(220001010111101)()3()()3(300000010111111)()2()()2(310000000111111)()1()() 1 (210100000011111)()0()()0(607721607721607721607721yyymRmxmxymRmxmxymRmxmxymRmxmxymmmm0233211N-1nN)(2nx)()(1nxny最后結(jié)果：五.有限長序列的線性卷積與圓周卷積1.線性卷積 的長度為 的長度為 它們線性卷積為)(1nx) 10(11NnN)(2nx) 10(22NnNmNmlmnxmxmnxmxny1021211)()()()(

16、)( 的非零區(qū)間為)(1mx101Nm的非零區(qū)間為)(2mx102Nmn兩不等式相加得2021NNn也就是 不為零的區(qū)間)(nyl例如)(1nx1012n)(2nx1nm)(2mx -1-2-3111)0(lym)1 (2mx21111) 1 (lym)2(2mx3111111)2(ly)(1mx1012mm)3(2mx3111111)3(lyn)(nyl2101)5(, 2)4(llyy同樣314523321)(1mx1012m2.用圓周卷積計(jì)算線性卷積圓周卷積是線性卷積的周期延拓序列的主值序列.的長度為 , 的長度為 ,先構(gòu)造長度均為L長的序列, 即將 補(bǔ)零點(diǎn);然后再對它們進(jìn)行周期延拓 ，即 所以得到周期卷積：)(1nx1N)(2nx2N)(),(21nxnxLLnxnx)(,)(2110