1、第三章第三章 離散傅里葉變換離散傅里葉變換主要內容主要內容n離散傅里葉級數離散傅里葉級數DFS）n離散傅里葉變換離散傅里葉變換DFT）n抽樣抽樣z變換變換頻域抽樣理論頻域抽樣理論3.1 引言引言傅里葉變換的幾種形式：傅里葉變換的幾種形式： 時間函數時間函數 頻率函數頻率函數v連續時間、連續頻率連續時間、連續頻率傅里葉變換傅里葉變換v連續時間、離散頻率連續時間、離散頻率傅里葉級數傅里葉級數v離散時間、連續頻率離散時間、連續頻率序列的傅里葉變換序列的傅里葉變換v離散時間、離散頻率離散時間、離散頻率離散傅里葉變換離散傅里葉變換dtetxjXtjaa)()(dejXtxtjaa)(21)( FT3.2

2、 傅里葉變換的幾種可能形式傅里葉變換的幾種可能形式 FS ktjkaejkXtx0)()(000|)()(1)(2/2/0kaTTtjkaTjXdtetxTjkX時域周期化，頻域離散化時域周期化，頻域離散化時域離散化，頻域周期化。時域離散化，頻域周期化。jnnjenxeX)()(deeXnxjnj)(21)(DTFT但是，前三種傅里葉變換對都不適于計算機但是，前三種傅里葉變換對都不適于計算機上運算，因為它們至少在一個域時域或頻域中上運算，因為它們至少在一個域時域或頻域中函數是連續的。函數是連續的。因而，我們感興趣的是時域及頻域都是離散因而，我們感興趣的是時域及頻域都是離散的情況。的情況。若時域

3、離散并周期化，頻域周期化并離散化。若時域離散并周期化，頻域周期化并離散化。四種傅里葉變換形式的歸納四種傅里葉變換形式的歸納 時間函數時間函數頻率函數頻率函數連續和非周期連續和非周期非周期和連續非周期和連續連續和周期連續和周期(T0)非周期和離散非周期和離散(0=2/T0)離散離散(T)和非周期和非周期周期周期(s=2/T)和連續和連續離散離散(T)和周期和周期(T0) 周期周期(s=2/T)和離散和離散(0=2/T0)3.3 離散傅里葉級數離散傅里葉級數DFS ( Discrete Fourier Series ) 連續周期信號連續周期信號:)()(rNnxnx周期序列周期序列 ( r 為整數

4、為整數, N 為周期為周期) ktjkaaaekAtxkTtxtx0)()()()(00002 /jktTke 基頻：次諧波分量：0 ( )( )jknkNx nA k e為周期的周期序列：002 /jknNke基頻：次諧波分量：周期序列的周期序列的DFS正變換和反變換：正變換和反變換：21100( ) ( )( )( )NNjnknkNNnnX kDFS x nx n ex n W2110011( )( )( )( )NNjnknkNNkkx nIDFS X kX k eX k WNN2jNNWe其中：其中：一般性的周期為一般性的周期為N的周期性序列的傅里葉變換的周期性序列的傅里葉變換kkk

5、NjkjkijkNkXNkNeXNkNNeXnxkNNiNneXnx)2()(2)2()(2)2(2)()()2(2)()()(2iiiNnnxiNnxnx)()()()(1022)()()(NnkNnjkNjenxeXkX X kz與 變換的關系： 010 x nnNx nn令其它 x nz對作 變換: 10NnnnnX zx n zx n z 210jkkNNNnkNz WenX kx n WX z 可看作是對可看作是對 的一個周的一個周期期 做做z z變換然后將變換然后將z z變換在變換在z z平面單位圓上按等間隔角平面單位圓上按等間隔角 抽樣得到抽樣得到 X k x n x n2NK=

6、01234567jImRez|z|=1N=8DFSDFS的圖示說明的圖示說明)(nxn0N-N.)(kXk0N-N例：周期序列例：周期序列 展開為展開為DFSDFS，求其系數。，求其系數。nnx6cos)(njnjnjnjeeeenx)11(12212212212221212121)(。其他0)(,62/)(kXNkX1101221221221222121)(nknjnjknjnjeeeekX解：方法解：方法1 1 整理整理x(n)x(n)有有(N=12)(N=12)：rk121rk1211與與DFSDFS定義對比知：在定義對比知：在 和和 時：時： 方法方法2 2 由定義式直接計算，得由定義

7、式直接計算，得 krkrkeeeeeekXkjkjkjkjnnkjnnkj其其它它的的,01211,6121,6112111212121)()11(12212)11(122)1(12212)1(122110)11(122110)1(122 -2 -1 0 1 2 11 12 nN=12nnx6cos)(krkrkkX其它的, 01211, 6121, 6)(-2 -1 0 1 2 11 12 k6( )6x nDFS例：已知序列是周期為 的周期序列， 如圖所示，試求其的系數。10( )( )NnkNnX kx n W解：根據定義求解 560( )nknx n W2226622234566614

8、1210 8610jkjkjkjkjkeeeee(0)60(1)93 3(2)33(3)0(4)33(5)93 3XXjXjXXjXj4( )( ), ( )8( )( )x nR nx nNx nx nDFS例：已知序列將以為周期 進行周期延拓成，求的。解法一：數值解10( )( )NnkNnX kx n W780( )nknx n W222238881jkjkjkeee 380nknW(0)4(1)121(2)0(3)121(4)0(5)121(6)0(7)121XXjXXjXXjXXj 210( )NjknNnX kDFS x nx n e解法二：公式解 2780jknnx n e340

9、jknne222888jkjkjkjkjkjkeeeeee44411jkjkee38sin2sin8jkkek3.4 離散傅里葉級數的性質離散傅里葉級數的性質FS性性1、線性：、線性：其中，其中， 為任意常數為任意常數,a b11( )( )X kDFS x n22( )( )XkDFS x n假假設設1212( )( )( )( )DFS ax nbx naX kbXk那那么么2、序列的移位、序列的移位2 ()( )( )jmkmkNNDFS x nmWX keX k10 ()()NnkNnDFS x nmx nm W證：1()( )Nmk i mNi mx i W inm令10( )( )

10、NmkkimkNNNiWx i WWX k3、調制特性、調制特性( )()nlNDFS Wx nX kl10( )( )NlnlnnkNNNnDFS W x nW x n W證：1()0( )Nl k nNnx n W()X kl4、對偶性、對偶性)()()()(kxNnXDFSkXnxDFS證：證：102)()(NknkNjekXnxN102102)(1)()()(NknkNjNnnkNjekXNnxenxkX102)()(NnknNjenXkxN5、周期卷積和、周期卷積和1210( )()Nmx m x nm12( )( )( )Y kX kXk假假設設1120( ) ( )( )()Nm

11、y nIDFS Y kx m x nm那那么么討論討論: : 周期卷積與線性卷積的區別在于：周期卷積求和周期卷積與線性卷積的區別在于：周期卷積求和只在一周期內進行。只在一周期內進行。( (注意周期信號的線性卷積不存在注意周期信號的線性卷積不存在) )式中的卷積稱為周期卷積式中的卷積稱為周期卷積12( )( )( )y nIDFS X kXk證： 11201( )( )NknNkXk Xk WN1112001( )( )NNmkknNNkmx m WXk WN 11()12001( )( )NNn m kNmkx mXk WN1120( )()Nmx m x nm142512( )( ) ( )

12、(1)( )6( )( )x nR nxnnR nx nxn例：已知序列，分別將序列以周期為 周期延拓成周期序列和，求兩個周期序列的周期卷積和。1120( )( )()Nmy nx m x nm解： 5120( )()mx m x nm0 5 0 5 4 3 2 1 4 3 2 15 4 5 4 3 2 1 0 3 2 1 04 3 4 3 2 1 0 5 2 1 0 53 2 3 2 1 0 5 4 1 0 5 42 1 2 1 0 5 4 3 0 5 4 31 0 1 0 5 4 3 2 5 4 3 21 2 1 2 3 4 5 0 3 4 5 01 1 1 1 1 1 0 0 1 1 0

13、 06 7 0 1 2 3 4 5 -4 -3 -2 -1n m1/xn m2xm21xm22xm23xm24xm25xm2/xn m10 8 6 10 14 12 ( )y n同樣，利用對稱性同樣，利用對稱性 11201( )()NlX l XklN12101( )()NlXl X klN12( )( )( )y nx n x n假假設設10( ) ( )( )NnkNnY kDFS y ny n W那那么么3.5 離散傅里葉變換離散傅里葉變換有限長序列的離散頻域表示有限長序列的離散頻域表示n在進行在進行DFSDFS分析時，時域、頻域序列都是無限分析時，時域、頻域序列都是無限長的周期序列長的

14、周期序列n周期序列實際上只有有限個序列值有意義周期序列實際上只有有限個序列值有意義n長度為長度為N N的有限長序列可以看成周期為的有限長序列可以看成周期為N N的周期的周期序列的一個周期主值序列）序列的一個周期主值序列）n借助借助DFSDFS變換對，取時域、頻域的主值序列可變換對，取時域、頻域的主值序列可以得到一個新的變換以得到一個新的變換DFTDFT，即有限長序列的，即有限長序列的離散傅里葉變換離散傅里葉變換( )()rx nx nrN( )( )( )Nx nx n Rn ( )( )Nx nNx n長度為的有限長序列周期為的周期序列( )x n的主值序列( )x n 的周期延拓另外一種寫

15、法是Nnxnx)()(其中其中 表示對表示對 n 取模取模N 運算運算(或模或模 N的余數的余數)。Nn)()()(1nxnx對周期信號而言對周期信號而言, , 或或 。NNnxnx)()(1ImNnnnmNnnN, 10)(111舉例：設周期為舉例：設周期為 N=6N=6。則有周期序列和求余運算：。則有周期序列和求余運算： 或或 這是因為：這是因為： (19=3(19=36+1)6+1) 同理同理 或或 這是因為：這是因為： (-2=-1(-2=-16+4) 6+4) ) 1 ()19(xx66)1()19(xx) 4() 2(xx66)4()2(xx( )( )NX kXk( )( )(

16、)NX kX k Rk同樣：同樣：X(k)也是一個也是一個N點的有限長序列點的有限長序列有限長序列的有限長序列的DFTDFT定義式定義式10102)()()(NnknNNnknNjWnxenxkX10102)(1)(1)(NkknNNkknNjWkXNekXNnx 1, 0 :Nk 1, 0 :Nn)()(kXnx)()(nxDFTkX)()(kXIDFTnx10( )( )( )( )( )NnkNNNnX kx n WRkX k Rk或 101( )( )( )( )( )NnkNNNkx nX k WRnx n RnN2jNNWe關于離散傅里葉變換關于離散傅里葉變換(DFT)：n序列序列

17、x(n)在時域是有限長的在時域是有限長的(長度為長度為N)，它的離，它的離散傅里葉變換散傅里葉變換X(k)也是離散、有限長的也是離散、有限長的(長度也長度也為為N)。nn為時域變量，為時域變量，k為頻域變量。為頻域變量。n離散傅里葉變換與離散傅里葉級數沒有本質區別，離散傅里葉變換與離散傅里葉級數沒有本質區別，DFT實際上是離散傅里葉級數的主值，實際上是離散傅里葉級數的主值，DFT也隱也隱含有周期性。含有周期性。n離散傅里葉變換離散傅里葉變換(DFT)具有唯一性。具有唯一性。nDFT的物理意義：序列的物理意義：序列x(n)的的Z變換在單位圓上變換在單位圓上的等角距取樣。的等角距取樣。x(n)的的

18、N點點DFT是是 x(n)的的z變換在單位圓上的變換在單位圓上的N點等間隔抽樣；點等間隔抽樣； x(n)的的DTFT在區間在區間0,2上的上的N點等間隔抽樣。點等間隔抽樣。DFTz與序列的DTFT和 變換的關系：10( )( )NnnX zx n z10( )( )NnkNnX kx n W10()( )Njj nnX ex n e2()jkNX e2( )jkkNNz WeX z例例1 1、計算、計算 (N=12)(N=12)的的N N點點DFT.DFT.解：解： )(6cos)(nRnnxNknjnjnjnNnknNeeeWnxkX1221221221101021)()()(21)11(1

19、22110)1(122nkjnnkjee)11(122)11(2)1(122)1(211211121kjkjkjkjeeeekk其它,011, 1,6) 1(110Nk)(6cos)(12nRnnxN=120123111-1nkkkX其它, 011, 1, 6)(k01 231164( )( ),( )816DFTx nR nx n例：已知序列求的 點和點。 DTFTx n解：求的 jj nnX ex n e222222jjjjjjeeeeee32sin 2sin/2je30j nne411jjee 8 8x nDFTN 求的 點 28jkX kX e32 42sin 281 2sin28jk

20、kek38sin2sin8jkkek 16 16x nDFTN 求的點 216jkX kX e3 22 162sin 2161 2sin2 16jkkek316sin4sin16jkkekN=4點的點的DFT？3.6 離散傅里葉變換的性質離散傅里葉變換的性質1、線性、線性, a b為任意常數這里，序列長度及這里，序列長度及DFT點數均為點數均為N若不等，分別為若不等，分別為N1，N2，則需補零使兩序列長度，則需補零使兩序列長度相等，均為相等，均為N，且，且12max,NN N11( ) ( )X kDFT x n22( )( )XkDFT x n假設假設1212( )( )( )( )DFT

21、ax nbx naX kbXk那那么么)()()(kXWnRmnxmkNNN)()()(kRlkXnxWNNnlN( ) ( ) ()x nx nx nm( )mxn周期延拓移位取主值序列()Nx nmv 有限長序列的圓周移位導致頻譜線性相移，而有限長序列的圓周移位導致頻譜線性相移，而對頻譜幅度無影響。對頻譜幅度無影響。v時域序列的調制等效于頻域的圓周移位時域序列的調制等效于頻域的圓周移位2 2、圓周移位、圓周移位)()()(kXWmnxDFSmnxDFSmkNN)()()()(kRmnxDFSnRmnxDFTNNNN)()()(kXWkRkXWmkNNmkN)()()(kXkRkXN其中其中

22、 ；同理可證另一公式。；同理可證另一公式。證：證：21( )cos()()( )2NNNnlDFT x nXklXklRkN21( )sin()()( )2NNNnlDFT x nXklXklRkNj推論：推論：q從圖中兩虛線之間的從圖中兩虛線之間的主值序列的移位情況可主值序列的移位情況可以看出：以看出：q當主值序列左移當主值序列左移m m個個樣本時，從右邊會同時樣本時，從右邊會同時移進移進m m個樣本個樣本q好像是剛向左邊移出好像是剛向左邊移出的那些樣本又從右邊循的那些樣本又從右邊循環移了進來環移了進來q因此取名因此取名“循環移循環移位位”。q顯然，循環移位不同顯然，循環移位不同于線性移位于

23、線性移位 )()()()()(kRkNNxkRkNxnXDFTNNNN假設假設那那么么)()(kXnxDFT證：證：)()()()(KxNnXDFSKXnxDFS)()()()()()(kRkNxkRkxNnRnXDFTNNNN)()()()()(kRkNNxkRkNxnXDFTNNNN3 3、對偶性、對偶性4 4、圓周共軛對稱性、圓周共軛對稱性其中：*( )()1/2 ( )()oox nxnx nxn *1/2 ( )() NNx nxNn共軛反對稱分量：*( )()1/2 ( )()eex nxnx nxn*1/2 ( )() NNx nxNn共軛對稱分量：( )( )( )eox nx

24、 nx n任意周期序列：定義：定義：( )( )( )epopx nxnxn則任意有限長序列：則任意有限長序列：( )( )( )opoNxnx n Rn *1/2 ( )() ( )NNNx nxNnRn圓周共軛反對稱序列：圓周共軛反對稱序列：( )( )( )epeNxnx n Rn *1/2 ( )() ( )NNNx nxNnRn圓周共軛對稱序列：圓周共軛對稱序列：設設N N點復數序列點復數序列 )()(kXnx)()()()()(*kRkNXkRkXnxDFTNNNN證明：證明：)()()()()()()()()(*1010*kRkNXkRkXkRWnxkRWnxnxDFTNNNNN

25、nkNNnNnkNNn 那么那么 同理可證明：同理可證明：)()()(*kXnRnxDFTNN1*0()( )()( )NnkNNNNNnDFT xnRnxnRn W證：*10()NnkNNnxnW*10( )NmkNNmx mW *10NnkNNnxnWmn 令 *10NnkNnx n W序列序列 DFT共軛對稱性共軛對稱性( )( )x nX kRe ( )( )epx nXkIm ( )( )opjx nXk( )Re( )epxnX k( )Im( )opxnjX k序列序列 DFTRe ( )( )( )epx nXkX kIm ( )0( )0opjx nXk( )Re ( )ep

26、xnX k( )Im ( )opxnjX kRe ( ) 0( )0epx nXkIm ( )( )( )opjx nXkX k( )Re ( )epxnX k( )Im ( )opxnjX k實數序列的實數序列的共軛對稱性共軛對稱性純虛數序列的純虛數序列的共軛對稱性共軛對稱性 例：設例：設x1(n)和和x2(n)都是都是N點的實數序列，試點的實數序列，試用一次用一次N點點DFT運算來計算它們各自的運算來計算它們各自的DFT: 11( )( )DFT x nX k22( )( )DFT x nXk解：利用兩序列構成一個復序列12( )( )( )w nx njx n12( ) ( )( )(

27、)W kDFT w nDFT x njx n則12( )( )DFT x njDFT x n12( )( )X kjXk1( )Re ( )x nw n由得11( )( )Re ( )( )epX kDFT x nDFTw nWk*1( )() ( )2NNNWkWNkRk2( )Im ( )x nw n由得221( )( )Im ( )( )opXkDFT x nDFTw nWkj*1( )() ( )2NNNWkWNkRkj五、五、Parseval Theory1010*)()(1)()(NnNkkYkXNnynx210102)(1)(kXNnxNnNk若令若令 y(n) = x(n)表明

28、序列時域、頻域能量相等表明序列時域、頻域能量相等六、圓周卷積和六、圓周卷積和圓周卷積圓周卷積A A：設：設)()()(kYkXkF)()(kFnf那么那么)()()()(10nRmnymxnfNNmN實際上，圓周卷積為周期卷積的主值序列。即實際上，圓周卷積為周期卷積的主值序列。即)()()()()()(nRnfnRnynxnfNN圓周卷積圓周卷積B B：設：設)()()(nynxnf)()(kFnf圓周卷積記為圓周卷積記為)()()(nynxnfN)()()()()(1)(10kYkXkRlkYlXNkFNNlNN圓周卷積過程：1補零2周期延拓3翻褶，取主值序列4圓周移位5相乘相加12( )(

29、 )x nx nN1120( )( )() ( )NNNmy nx m xnmRn1210( )() ( )NNNmx m xnmRn21( )( )x nx nN兩個兩個N N點序列的點序列的N N點圓周卷積得到點圓周卷積得到的結果仍為的結果仍為N N點點序列。序列。 圓周卷積圓周卷積)(nxn0 0N-1N-1)(nyn110 0N-1N-10 0N-1N-1)( my mn=0n=01)1(myn=1n=1)2(myn=2n=2)(nfmmn0 0N-1N-1N-1N-10 00 0N-1N-12 , 1 , 0 , 1 , 2 , 3 , 4 , 3)(nfN=8N=8m N-m 1

30、N-1 2 N-2 N-3 討論討論1:1:圓周卷積的物理意義圖示說明圓周卷積的物理意義圖示說明討論討論2:2:圓周卷積與線性卷積：圓周卷積與線性卷積：1) 1) 設設)10()(Nnnx)10()(MNny有限長有限長(N(N點點) )有限長有限長(M(M點點) )則線性卷積則線性卷積mmnymxnynxnf)()()()()(有限長有限長(N+M-1)(N+M-1)2) 2) 而作長度為而作長度為L L的圓周卷積，即的圓周卷積，即)( )()()()(nRrLnfnRnfnfLrLllLLlnynxnynxnf)()()()()( (周期卷積周期卷積) )其中其中)()()()()()(1

31、0nynxnRmnymxnfLLmLlL那么那么11, 020),()(LnMNMNnnfnfl)()()(nRnfnfLll1MNL1MNL( (補零補零) )存在交疊現象存在交疊現象這就是利用這就是利用DFTDFT計算線性卷積的方法和要求，計算線性卷積的方法和要求，即可以選擇長度大于等于線性卷積的兩序列長度即可以選擇長度大于等于線性卷積的兩序列長度之和的之和的DFTDFT運算計算線性卷積。運算計算線性卷積。121NNNN即 當圓周卷積長度時， 點圓周卷積能代表線性卷積)( nxn0 01 1N=4N=43 3M=6)( nyn0 01 15 5)( nfn0 01 18 8L=6L=6Lmy)0( m0 01 15 5L=6L=6)(6nfn4 45 5L=8L=8m0 01 17 7L=9L=9m0 01 18 8)(8nfn0 02 27 7L=8L=8)(nfLn0 01 18 891 MNL0 0Lmy)0( Lmy)0( 討論討論3:3:周期卷積、圓周卷積與線性卷積周期卷積、圓周卷積與線性卷積 周期卷積與圓周卷積的差別在于：周期卷積是線性周期卷積與圓周卷積的差別在于：周期卷積是線性卷積的周期延拓；而圓周卷積是取周期卷積的主值卷積的周期延拓；