數字信號處理離散傅里葉變換PPT學習教案

1、會計學1 數字信號處理離散傅里葉變換數字信號處理離散傅里葉變換 2 第1頁/共38頁 3 離散傅里葉變換定義離散傅里葉變換定義 計算機只能處理計算機只能處理有限長離散序列有限長離散序列，因而，因而 無法直接利用無法直接利用ZT與與FT進行數值計算。進行數值計算。 針對有限長序列針對有限長序列, 還有一種更有用的數還有一種更有用的數 學變換學變換, 即離散傅里葉變換（即離散傅里葉變換（Discrete Fourier Transform），使數字信號處理），使數字信號處理 可以在頻域采用數字運算的方法進行，可以在頻域采用數字運算的方法進行， 大大增加了數字信號處理的靈活性。大大增加了數字信號處理

2、的靈活性。 第2頁/共38頁 4 DFT的實質：有限長序列傅里葉變換的的實質：有限長序列傅里葉變換的 有限點離散采樣，有限點離散采樣，即即頻域離散化。頻域離散化。 DFT有多種快速算法有多種快速算法(Fast Fourier Transform), 因此不僅在理論上有重要因此不僅在理論上有重要 意義意義, 在各種數字信號處理算法中亦起在各種數字信號處理算法中亦起 著核心作用。從而使信號的實時處理和著核心作用。從而使信號的實時處理和 設備的簡化得以實現。設備的簡化得以實現。 第3頁/共38頁 5 N-1 kn N n=0 X(k)= DFTx(n) =x(n)W, k =0, 1,. , N -

3、1 X(k)的的離散傅里葉逆變換離散傅里葉逆變換為：為： N-1 -kn N n=0 1 x(n)=IDFTX(k)=X(k)W, n=0, 1, ., N-1 N 第4頁/共38頁 6 對式中，對式中，N稱為稱為DFT變換變換 區(qū)間長度，區(qū)間長度，NM。通常稱上述二式為離。通常稱上述二式為離 散傅里葉變換對。為了敘述簡潔，常常用散傅里葉變換對。為了敘述簡潔，常常用 DFTx(n)N和和IDFTX(k)N分別表示分別表示 N點離散傅里葉變換和點離散傅里葉變換和N點離散傅里葉逆點離散傅里葉逆 變換。變換。 2 -j N N W= e 第5頁/共38頁 7 ) ) , 0,1.,7k k 4 73

4、 knkn 8 88 k n=0n=0 8 1-W X(k)=x(n)W=W= 1-W 1-(- = 1-(- sin() sin() 2 2 -j4k-j4k-jkjk-jk-jkjk-jk 8 8222222 2 2 -jk-jkjk-jk-jk-jkjk-jk 88888888 3 3 -jk-jk 8 8 eeeeeeee eeeeeeee k k 2 2 e e k k 8 8 第6頁/共38頁 8 （2）設變換區(qū)間）設變換區(qū)間N=16 時，則：時，則： ) ) , 0,1.,15k k 4 153 knkn 16 1616 k n=0n=0 16 1 -W X(k) =x(n)W=

5、W= 1 -W 1 -(- = 1 -(- sin() sin() 2 2 - -j j4 4k k- -j jk kj jk k- -j jk k 1 16 64 44 44 4 2 2 - -j jk k- -j jk kj jk k- -j jk k 1 16 61 16 61 16 61 16 6 3 3 - -j jk k 1 16 6 e ee ee ee e e ee ee ee e k k 4 4 e e k k 1 16 6 第7頁/共38頁 9 X(n)的幅頻特性曲線的幅頻特性曲線(FT曲線曲線) X(n)的的8點點DFT曲線曲線 X(n)的的16點點DFT曲線曲線 第8頁

6、/共38頁 10 結論結論: 由此例可見，由此例可見，x(n)的離散傅里葉變換結果與的離散傅里葉變換結果與 變換區(qū)間長度變換區(qū)間長度N的取值有關。在后面，對的取值有關。在后面，對DFT與與 Z變換和傅里葉變換的關系及變換和傅里葉變換的關系及DFT的物理意義進的物理意義進 行討論后，上述問題就會得到解釋。行討論后，上述問題就會得到解釋。 第9頁/共38頁 11 DFT與傅里葉變換和與傅里葉變換和Z變換的關系變換的關系 設序列設序列x(n)的長度為的長度為M，其，其Z變換和變換和 N(NM)點點DFT分別為：分別為： 1 0 1 0 ( )ZT ( )( ) ( )DFT ( )( )0,1,1

7、M n n M kn NN n X zx nx n z X kx nx nWkN 第10頁/共38頁 12 上二式表明序列上二式表明序列x(n)的的N點點DFT是是x(n)的的Z 變換在單位圓上的變換在單位圓上的N點等間隔采樣。點等間隔采樣。X(k)為為 x(n)的傅里葉變換。的傅里葉變換。 j 2 ( )(e )|0,1,1 k N X kXkN 比較上面二式可得關系式比較上面二式可得關系式 2 j e ( )( )0,1,1 k N z X kX zkN 或或 第11頁/共38頁 13 DFT是是 X(ej)在區(qū)間在區(qū)間0, 2上的上的N點等間點等間 隔采樣。這就是隔采樣。這就是DFT的物

8、理意義的物理意義。 DFT的變換區(qū)間長度的變換區(qū)間長度N不同，表示對不同，表示對 X(ej)在區(qū)間在區(qū)間0, 2上的采樣間隔和采樣上的采樣間隔和采樣 點數不同，所以點數不同，所以DFT的變換結果不同。的變換結果不同。 DFT的物理意義的物理意義 第12頁/共38頁 14 kn N W DFT的隱含周期性的隱含周期性 在在DFT變換對中，變換對中，x(n)與與X(k)均為有限長序列，但均為有限長序列，但 由于由于的周期性，使的周期性，使DFT和和IDFT式中的式中的X(k)隱隱 含周期性，且周期均為含周期性，且周期均為N。對任意整數。對任意整數m，總有，總有 在在DFT式中，式中，X（k)滿足：

9、滿足： () , kkmN NN NWWk m 為整數,為自然數， 11 () 00 ()( )( )( ) NN kmN nkn NN nn X kmNx n Wx n WX k 第13頁/共38頁 15 實際上，任何周期為實際上，任何周期為N的周期序列都可的周期序列都可 以看做長度為以看做長度為N的有限長序列的有限長序列x(n)的周期延的周期延 拓序列，而拓序列，而x(n)則是的一個周期，即則是的一個周期，即 ( )() m x nx nmN ( )( )( ) N x nx nRn ( )x n ( )x n 第14頁/共38頁 16 一般稱周期序列中從一般稱周期序列中從n=0到到N1

10、的第一個周期為的主值區(qū)間，而主的第一個周期為的主值區(qū)間，而主 值區(qū)間上的序列稱為的主值序列。值區(qū)間上的序列稱為的主值序列。 因此因此x(n)與的上述關系可敘述為：與的上述關系可敘述為： 是是x(n)的周期延拓序列，的周期延拓序列，x(n)是的主是的主 值序列。值序列。 )( nx )( nx )( nx )( nx )( nx )( nx 第15頁/共38頁 17 為了以后敘述簡潔，當為了以后敘述簡潔，當N大于等于序列大于等于序列x(n)的的 長度時，將式長度時，將式 用如右形式表示：用如右形式表示： 式中式中x(n) N表示表示x(n)以以N為周期的周期延拓序為周期的周期延拓序 列，列，(n

11、)N表示模表示模N對對n求余，即如果求余，即如果 n=MN+n1 0n1N1, M為整數為整數 則則(n)N=n1 ( )( )Nx nx n ( )() m x nx nmN 第16頁/共38頁 18 8 8, ( )( )Nx nx n 8 8 (8)(8)(0) (9)(9)(1) xxx xxx 第17頁/共38頁 19 如果如果x(n)的長度為的長度為N，且，則可，且，則可 寫出的離散傅里葉級數表示式寫出的離散傅里葉級數表示式 N nxnx)()( 111 000 ( )( )( )( ) NNN knknkn NNNN nnn X kx n Wx nWx n W 11 00 11

12、( )( )( ) NN knkn NN kk x nX k WX k W NN )( nx 式中式中 ( )( )( ) N X kX k Rk 即即X(k)為的主值序列為的主值序列。 ( )X k 第18頁/共38頁 20 因此可知，有限長序列因此可知，有限長序列x(n)的的N點離散傅里葉變換點離散傅里葉變換 X(k)正好是正好是x(n)的周期延拓序列的周期延拓序列x(n)N的離散傅里葉的離散傅里葉 級數系數的主值序列，即級數系數的主值序列，即 。后面要討論的頻域采樣理論將會加深對這一關系。后面要討論的頻域采樣理論將會加深對這一關系 的理解。我們知道，周期延拓序列頻譜完全由其離的理解。我們

13、知道，周期延拓序列頻譜完全由其離 散傅里葉級數系數確定，因此，散傅里葉級數系數確定，因此，X(k)實質上實質上 是是x(n)的周期延拓序列的周期延拓序列x(n) N的頻譜特性，這就是的頻譜特性，這就是N 點點DFT的物理意義。的物理意義。 ( )X k )()( )(kRkXkX N ( )X k 第19頁/共38頁 21 第20頁/共38頁 22 第21頁/共38頁 23 循環(huán)移位過程示意圖循環(huán)移位過程示意圖 第22頁/共38頁 24 ( ) km N WX k 第23頁/共38頁 25 （3）頻域循環(huán)移位定理，如果）頻域循環(huán)移位定理，如果 X(k)=DFTx(n), 0kN-1 Y(k)=

14、X(k+l)NRN(k) 則則 y(n)=IDFTY(k) n ( ) l N Wx n 第24頁/共38頁 26 1 12 0 ( ) ( )( ) ()( ) N NN m x nIDFT X kx m xn mR n 1 21 0 ( ) ( )( ) ()( ) N NN m x nIDFT X kx m x n mR n 或或 上式所表示的運算稱為上式所表示的運算稱為x1(n)與與x2(n)的循環(huán)卷積。的循環(huán)卷積。 第25頁/共38頁 27 循環(huán)卷積過程中，循環(huán)卷積過程中， 要求對要求對x2(m)循環(huán)反轉循環(huán)反轉 ， 循環(huán)移位，循環(huán)移位， 特別是兩個特別是兩個N長的序列的循長的序列的

15、循 環(huán)卷積長度仍為環(huán)卷積長度仍為N。 顯然與一般的線性卷顯然與一般的線性卷 積不同，積不同， 故稱之為循環(huán)卷積，故稱之為循環(huán)卷積， 記為記為 12 1 12 0 ( )( )( ) ( )()( ) N NN m x nx nx n x m xnmRn 第26頁/共38頁 28 12 21 ( ) ( ) ( )( ) ( )( ) X kDFT x n X kXk XkX k 由于由于 所以所以 12 21 ( )( )( )( ) ( )( ) x nIDFT X kx nx n x nx n 即循環(huán)卷積亦滿足交換律。即循環(huán)卷積亦滿足交換律。 第27頁/共38頁 29 12 1 12 0

16、21 1 21 0 1 ( ) ( )( )( ) 1 ( )()( ) 1 ( )( )( ) 1 ( )()( ) N NN l N NN l X kDFT x nX kXk N X l XklRk N X kXkX k N Xl XklRk N 或 第28頁/共38頁 30 直接計算循環(huán)卷積較麻煩。計算機中采直接計算循環(huán)卷積較麻煩。計算機中采 用矩陣相乘或快速傅里葉變換（用矩陣相乘或快速傅里葉變換（FFT） 的方法計算循環(huán)卷積。下面介紹用矩陣的方法計算循環(huán)卷積。下面介紹用矩陣 計算循環(huán)卷積的公式。計算循環(huán)卷積的公式。 第29頁/共38頁 31 (0)(1)(2)(1) (1)(0)(1)

17、(2) (2)(1)(0)(3) (1)(2)(3)(0) xx Lx Lx xxx Lx xxxx x Lx Lx Lx 當n = 0, 1, 2, , L1時，由x(n)形成的序列 為： x(0), x(1), , x(L1)。循環(huán)移位后可 得下面的矩陣： 第30頁/共38頁 32 上面矩陣稱為上面矩陣稱為x(n)的的L點點“循環(huán)卷積矩陣循環(huán)卷積矩陣”，其特點，其特點 是是: （1） 第第1行是序列行是序列x(0), x(1), , x(L1)的的 循環(huán)倒相序列。注意，如果循環(huán)倒相序列。注意，如果x(n)的長度的長度ML，則需，則需 要在要在x(n)末尾補末尾補LM個零后，再形成第一行的循

18、環(huán)個零后，再形成第一行的循環(huán) 倒相序列。倒相序列。 （2） 第第1行以后的各行均是前一行向右循環(huán)移行以后的各行均是前一行向右循環(huán)移 1位形成的。位形成的。 （3） 矩陣的各主對角線上的序列值均相等。矩陣的各主對角線上的序列值均相等。 有了上面介紹的循環(huán)卷積矩陣，就可以寫出有了上面介紹的循環(huán)卷積矩陣，就可以寫出 y(n)c的矩陣形式如下的矩陣形式如下: 第31頁/共38頁 33 c c c c (0)(0)(1)(2)(1)(0) (1)(1)(0)(1)(2)(1) (2)(2)(1)(0)(3)(2) (1)(1)(2)(3)(0)(1) yxx Lx Lxh yxxx Lxh yxxxxh y Lx Lx Lx LxhL 第32頁/共38頁 34 按照上式，可以在計算機上用矩陣相乘的方法按照上式，可以在計算機上用矩陣相乘的方法 計算兩個序列的循環(huán)卷積，這