第3章離散傅里葉變換

1、第3章 離散傅里葉變換(DFT) 第第3章章 離散傅里葉變換離散傅里葉變換(DFT) 3.1 離散傅里葉變換的定義及物理意義離散傅里葉變換的定義及物理意義 3.2 離散傅里葉變換的基本性質(zhì)離散傅里葉變換的基本性質(zhì) 3.3 頻率域采樣頻率域采樣 3.4 DFT的應(yīng)用舉例的應(yīng)用舉例 習(xí)題與上機(jī)題習(xí)題與上機(jī)題第3章 離散傅里葉變換(DFT) 傅里葉變換和Z變換是數(shù)字信號處理中常用的重要數(shù)學(xué)變換。對于有限長序列，還有一種更為重要的數(shù)學(xué)變換，即本章要討論的離散傅里葉變換(Discrete Fourier Transform，DFT)。DFT之所以更為重要，是因為其實質(zhì)是有限長序列傅里葉變換的有限點(diǎn)離散采

2、樣，從而實現(xiàn)了頻域離散化，使數(shù)字信號處理可以在頻域采用數(shù)值運(yùn)算的方法進(jìn)行，這樣就大大增加了數(shù)字信號處理的靈活性。更重要的是，DFT有多種快速算法，統(tǒng)稱為快速傅里葉變換(Fast Fourier Transform，F(xiàn)FT)，從而使信號的實時處理和設(shè)備的簡化得以實現(xiàn)。第3章 離散傅里葉變換(DFT) 因此，時域離散系統(tǒng)的研究與應(yīng)用在許多方面取代了傳統(tǒng)的連續(xù)時間系統(tǒng)。所以說，DFT不僅在理論上有重要意義，而且在各種信號的處理中亦起著核心作用。 本章主要討論DFT的定義、物理意義、基本性質(zhì)以及頻域采樣和DFT的應(yīng)用舉例等內(nèi)容。第3章 離散傅里葉變換(DFT) 3.1 離散傅里葉變換的定義及物理意義離

3、散傅里葉變換的定義及物理意義3.1.1 DFT的定義的定義 設(shè)x(n)是一個長度為M的有限長序列，則定義x(n)的N點(diǎn)離散傅里葉變換為10( )DFT ( )( )0,1,1NknNnX kx nx n WkN(3.1.1)2jeNNW第3章 離散傅里葉變換(DFT) X(k)的離散傅里葉逆變換(Inverse Discrete Fourier Transform, IDFT) 為2jeNNW式中，N稱為DFT變換區(qū)間長度。通常稱(3.1.1)式和(3.1.2)式為離散傅里葉變換對。為了敘述簡潔，常常用DFTx(n)N和IDFTX(k)N分別表示N點(diǎn)離散傅里葉變換和N點(diǎn)離散傅里葉逆變換。下面證

4、明IDFTX(k)的唯一性。101( )IDFT( )( )NknNkx nX kX k WN0,1,1nN(3.1.2)第3章 離散傅里葉變換(DFT) 把(3.1.1)式代入(3.1.2)式，有由于110011()001IDFT( )( )1( )NNmkknNNNkmNNk m nNmkX kx m WWNx mWN 為整數(shù)為整數(shù)，iiNnmiiNnmWNNknmkN01110)(所以，在變換區(qū)間上滿足下式：IDFTX(k)=x(n) 0nN1由此可見，(3.1.2)式定義的離散傅里葉逆變換是唯一的。第3章 離散傅里葉變換(DFT) 例例3.1.1 已知序列x(n)=(n)，求它的N點(diǎn)D

5、FT。 解解 單位脈沖序列的DFT很容易由DFT的定義式（2-30）得到： 1001)()(NnNnkNWWnkX k=0, 1, , N-1 (n)的X(k)如圖2-9。這是一個很特殊的例子，它表明對序列(n)來說，不論對它進(jìn)行多少點(diǎn)的DFT，所得結(jié)果都是一個離散矩形序列。 第3章 離散傅里葉變換(DFT) 圖2-9 序列(n)及其離散傅里葉變換 第3章 離散傅里葉變換(DFT) 例例 3.1.2 已知x(n)=cos(n/6)是一個長度N=12的有限長序列， 求它的N點(diǎn)DFT。 解解 由DFT的定義式（2-30） 110)1(122110)1(122110122661211021216co

6、s)(nknjnknjnnkjnjnjnkneeeeeWnkX 利用復(fù)正弦序列的正交特性（2-3）式，再考慮到k的取值區(qū)間，可得 11, 0,011, 16)(kkkkX其他第3章 離散傅里葉變換(DFT) 圖 2-10 有限長序列及其DFT第3章 離散傅里葉變換(DFT) 例例 3.1.3 已知如下X(k):13)(kXk=0 1k9 求其10點(diǎn)IDFT。 解解 X(k)可以表示為 X(k)=1+2(k) 0k9 寫成這種形式后，就可以很容易確定離散傅里葉反變換。 由于一個單位脈沖序列的DFT為常數(shù)： 111( )( )( )( )1x nnX kDFT x n第3章 離散傅里葉變換(DFT

7、) 同樣，一個常數(shù)的DFT是一個單位脈沖序列： x2(n)=1 X2(k)=DFTx2(n)=N(k) 所以 )(51)(nnx第3章 離散傅里葉變換(DFT) 3.1.2 DFT與傅里葉變換和與傅里葉變換和Z變換的關(guān)系變換的關(guān)系 設(shè)序列x(n)的長度為M，其Z變換和N(NM)點(diǎn)DFT分別為比較上面二式可得關(guān)系式 (3.1.3)或1010( )ZT ( )( )( )DFT ( )( )0,1,1MnnMknNNnX zx nx n zX kx nx n WkN2je( )( )0,1,1kNzX kX zkNj2( )(e )|0,1,1kNX kXkN (3.1.4)第3章 離散傅里葉變換

8、(DFT) X(k)也可以看作序列也可以看作序列x(n)的傅里葉變換的傅里葉變換X(ej)在區(qū)間在區(qū)間0, 2上的上的N點(diǎn)等間隔采樣，其采樣間隔為點(diǎn)等間隔采樣，其采樣間隔為N=2/N， 這就是這就是DFT的物理意義的物理意義。顯而易見，DFT的變換區(qū)間長度N不同， 表示對X(ej)在區(qū)間0, 2上的采樣間隔和采樣點(diǎn)數(shù)不同， 所以DFT的變換結(jié)果也不同。 第3章 離散傅里葉變換(DFT) X(ej)在區(qū)間0, 2上的N點(diǎn)等間隔采樣。這就是DFT的物理意義。由此可見，DFT的變換區(qū)間長度N不同，表示對X(ej)在區(qū)間0, 2上的采樣間隔和采樣點(diǎn)數(shù)不同，所以DFT的變換結(jié)果不同。上例中， x(n)=

9、R4(n)，DFT變換區(qū)間長度N分別取8、16時，X(ej)和X(k)的幅頻特性曲線圖如圖3.1.1所示。由此容易得到x(n)=R4(n)的4點(diǎn)DFT為X(k)=DFTx(n)4=4(k)，這一特殊的結(jié)果在下面將得到進(jìn)一步解釋。第3章 離散傅里葉變換(DFT) 圖 3-1 DFT與序列傅里葉變換、Z變換的關(guān)系 第3章 離散傅里葉變換(DFT) knNW3.1.3 DFT的隱含周期性的隱含周期性 前面定義的DFT變換對中，x(n)與X(k)均為有限長序列，但由于的周期性，使(3.1.1)和(3.1.2)式中的X(k)隱含周期性，且周期均為N。對任意整數(shù)m，總有所以(3.1.1)式中，X（k)滿足

10、：(),kk mNNNNWWk m為整數(shù), 為自然數(shù)，11()00( )( )( )()NNknk mN nNNnnX kx n Wx n WX kmN11()0011( )( )( )()NNknk n mNNNkkx nX k WX k Wx nmNNN第3章 離散傅里葉變換(DFT) (3.1.5)(3.1.6)( )()mx nx nmN( )( )( )Nx nx nRn上述關(guān)系如圖3.1.2（a）和（b）所示。一般稱周期序列中從n=0到N1的第一個周期為的主值區(qū)間，而主值區(qū)間上的序列稱為的主值序列。因此x(n)與的上述關(guān)系可敘述為：是x(n)的周期延拓序列，x(n)是的主值序列。)

11、(nx)(nx)(nx)(nx)(nx)(nx實際上，任何周期為N的周期序列都可以看做長度為N的有限長序列x(n)的周期延拓序列，而x(n)則是 的一個周期，即)(nx)(nx第3章 離散傅里葉變換(DFT) 為了以后敘述簡潔，當(dāng)N大于等于序列x(n)的長度時，將(3.1.5)式用如下形式表示：(3.1.7)式中x(n) N表示x(n)以N為周期的周期延拓序列，(n)N表示模N對n求余，即如果n=MN+n1 0n1N1, M為整數(shù)則(n)N=n1 例如，, 則有所得結(jié)果符合圖3.1.2（a）和（b）所示的周期延拓規(guī)律。( )( )Nx nx n88, ( )( )Nx nx n88(8)(8)

12、(0)(9)(9)(1)xxxxxx第3章 離散傅里葉變換(DFT) 圖3.1.2 x(n)及其周期延拓序列第3章 離散傅里葉變換(DFT) )(nx)(nx應(yīng)當(dāng)說明，若x(n)實際長度為M，延拓周期為N，則當(dāng)NM時，(3.1.5)式仍表示以N為周期的周期序列，但(3.1.6)和 (3.1.7)式僅對NM時成立。圖3.1.2（a）中x(n)實際長度M=6，當(dāng)延拓周期N=4時，如圖3.1.2（c）所示。 如果x(n)的長度為M，且，NM，則可寫出的離散傅里葉級數(shù)表示式Nnxnx)()(3.1.8)(3.1.9)111000( )( )( )( )NNNknknknNNNNnnnX kx n Wx

13、 nWx n W110011( )( )( )NNknknNNkkx nX k WX k WNN第3章 離散傅里葉變換(DFT) 式中即X(k)為的主值序列。將(3.1.8)和(3.1.9)式與DFT的定義(3.1.1)和(3.1.2)式相比較可知，有限長序列x(n)的N點(diǎn)離散傅里葉變換X(k)正好是x(n)的周期延拓序列x(n)N的離散傅里葉級數(shù)系數(shù)的主值序列，即。后面要討論的頻域采樣理論將會加深對這一關(guān)系的理解。我們知道，周期延拓序列頻譜完全由其離散傅里葉級數(shù)系數(shù)確定，因此，X(k)實質(zhì)上是x(n)的周期延拓序列x(n) N的頻譜特性，這就是這就是N點(diǎn)點(diǎn)DFT的第二種的第二種物理解釋（物理

14、意義）。物理解釋（物理意義）。( )( )( )NX kX k Rk(3.1.10)( )X k( )X k)()()(kRkXkXN( )X k第3章 離散傅里葉變換(DFT) 例例 3.1.4 有限長序列x(n)為 01)(nx0n4 其余n 求其N=5 點(diǎn)離散傅里葉變換X(k)。 解解 序列x(n)如圖2-12（a）所示。在確定DFT時，我們可以將x(n)看作是一個長度N5的任意有限長序列。首先我們以N=5 為周期將x(n)延拓成周期序列 ，如圖2-12（b）， 的DFS與x(n)的DFT相對應(yīng)。因為在圖2-12（ b）中的序列在區(qū)間0nN-1 上為常數(shù)值，所以可以得出 )(nx011)

15、()/2210)/2(NeeekXNkjkjNnnNkj（k=0, N, 2N, 其他 (2-35)第3章 離散傅里葉變換(DFT) 也就是說，只有在k=0 和k=N 的整數(shù)倍處才有非零的DFS系數(shù) 值。這些DFS系數(shù)如圖2-12（c）所示。為了說明傅里葉級數(shù) 與x(n)的頻譜X(ej)間的關(guān)系，在圖2-12（c）中也畫出了傅里葉變換的幅值|X（ej)|。顯然， 就是X(ej)在頻率k=2k/N 處的樣本序列。按照式（2-29），x(n)的DFT對應(yīng)于取 的一個周期而得到的有限長序列X(k)。這樣，x(n)的5點(diǎn)DFT如圖2-12（d）所示。 )(kx)(kX)(kX)(kX0511)()(5

16、2215052kjkjnnkjeeenxkX k=0, 1, 2, 3, 4 k=0 k=0, 1, 2, 3, 4 第3章 離散傅里葉變換(DFT) 圖 3-3DFT的舉例說明（a） 有限長序列x(n); （b）由x(n)形成的周期N=10的周期序列x(n); （c） DFT的幅值 第3章 離散傅里葉變換(DFT) 圖 3-2 DFT的舉例說明（a） 有限長序列x(n); （b） 由x(n)形成的周期N=5的周期序列; （c） 對應(yīng)于 的傅里葉級數(shù) 和x(n)的傅里葉變換的幅度特性|X(ej)|; （d） x(n)的DFT X(k) )(nx)(kX第3章 離散傅里葉變換(DFT) 【例例3

17、.1.2】 設(shè)x(n)=R4(n)，X(ej)=FTx(n)。分別計算X(ej)在頻率區(qū)間0，2上的16點(diǎn)和32點(diǎn)等間隔采樣，并繪制X(ej)采樣的幅頻特性圖和相頻特性圖。解解 由DFT與傅里葉變換的關(guān)系知道，X(ej)在頻率區(qū)間0，2上的16點(diǎn)和32點(diǎn)等間隔采樣，分別是x(n)的16點(diǎn)和32點(diǎn)DFT。調(diào)用fft函數(shù)求解本例的程序ep312.m如下:第3章 離散傅里葉變換(DFT) % 例3.1.2程序ep312.m% DFT的MATLB計算xn=1 1 1 1; %輸入時域序列向量xn=R4(n)Xk16=fft(xn, 16); %計算xn的16點(diǎn)DFTXk32=fft(xn, 32);

18、%計算xn的32點(diǎn)DFT%以下為繪圖部分（省略，程序集中有）程序運(yùn)行結(jié)果如圖3.1.3所示。第3章 離散傅里葉變換(DFT) 圖3.1.3 程序ep312.m 運(yùn)行結(jié)果 第3章 離散傅里葉變換(DFT) 現(xiàn)在解釋DFTR5(n)5=5(k)。根據(jù)DFT第二種物理解釋可知，DFTR5(n)5表示R5(n)以5為周期的周期延拓序列R5(n)5的頻譜特性，因為R5(n)5是一個直流序列，只有直流成分（即零頻率成分）。 第3章 離散傅里葉變換(DFT) 3.1.4 用用MATLAB計算序列的計算序列的DFTMATLAB提供了用快速傅里葉變換算法FFT(算法見第4章介紹)計算DFT的函數(shù)fft，其調(diào)用格

19、式如下: Xk = fft (xn, N)；調(diào)用參數(shù)xn為被變換的時域序列向量，N是DFT變換區(qū)間長度，當(dāng)N大于xn的長度時，fft函數(shù)自動在xn后面補(bǔ)零。函數(shù)返回xn的N點(diǎn)DFT變換結(jié)果向量Xk。當(dāng)N小于xn的長度時，fft函數(shù)計算xn的前面N個元素構(gòu)成的N長序列的N點(diǎn)DFT，忽略xn后面的元素。 Ifft函數(shù)計算IDFT，其調(diào)用格式與fft函數(shù)相同，可參考help文件。第3章 離散傅里葉變換(DFT) 3.2 離散傅里葉變換的基本性質(zhì)離散傅里葉變換的基本性質(zhì)3.2.1 線性性質(zhì)線性性質(zhì)如果x1(n)和x2(n)是兩個有限長序列，長度分別為N1和N2，且y(n)=ax1(n)+bx2(n)式

20、中，a、b為常數(shù)，取N=maxN1, N2, 則y(n)的N點(diǎn)DFT為Y(k)=DFTy(n)N=aX1(k)+bX2(k) 0kN1 (3.2.1)其中X1(k)和X2(k)分別為x1(n)和x2(n)的N點(diǎn)DFT。 第3章 離散傅里葉變換(DFT) 3.2.2 循環(huán)移位性質(zhì)循環(huán)移位性質(zhì)1序列的循環(huán)移位序列的循環(huán)移位 設(shè)x(n)為有限長序列，長度為M，MN，則x(n)的循環(huán)移位定義為y(n)=x(n+m) NRn(n) (3.2.2)(3.2.2)式表明，將x(n)以N為周期進(jìn)行周期延拓得到，再將左移m得到，最后取的主值序列則得到有限長序列x(n)的循環(huán)移位序列y(n)。 M=6, N=8,

21、 m=2時，x(n)及其循環(huán)移位過程如圖3.2.1所示。Nnxnx)()()(nx)(mnx)(mnx第3章 離散傅里葉變換(DFT) 顯然，y(n)是長度為N的有限長序列。觀察圖3.2.1可見，循環(huán)移位的實質(zhì)是將x(n)左移m位，而移出主值區(qū)(0nN1)的序列值又依次從右側(cè)進(jìn)入主值區(qū)?！把h(huán)移位”就是由此得名的。由循環(huán)移位的定義可知，對同一序列x(n)和相同的位移m，當(dāng)延拓周期N不同時，y(n)=x(n+m)NRn(n)則不同。請讀者畫出N = M=6，m=2時，x(n)的循環(huán)移位序列y(n)波形圖。第3章 離散傅里葉變換(DFT) 圖3.2.1 x(n)及其循環(huán)移位過程第3章 離散傅里葉變

22、換(DFT) (e)x(n)21n 0N1N2on 0N1N221n 0N2N1( f )( g )210 x(n)n0n)(nxNnxnx)2()2(0n)()2(nRnxNN0N1n(a)(b)(c)(d )N1N1N1第3章 離散傅里葉變換(DFT) 2 時域循環(huán)移位定理時域循環(huán)移位定理 設(shè)x(n)是長度為M（MN）的有限長序列，y(n)為x(n)的循環(huán)移位，即y(n)=x(n+m)NRn(n)則(3.2.3)其中X(k)=DFTx(n)N 0kN1( )DFT ( )( )kmNNY ky nWX k第3章 離散傅里葉變換(DFT) nkNNWnx)(證明證明1令n+m=n，則有由于上

23、式中求和項以N為周期，因此對其在任一周期上的求和結(jié)果相同。將上式的求和區(qū)間改在主值區(qū)，則得1100( )DFT ( )()( )()NNknknNNNNNNnnY ky nx nmRn Wx nmW11()( )( )( )NmNmk nmkmknNNNNNnmnmY kx nWWx nW 1100( )( )( )( )NNkmknkmknkmNNNNNNnnY kWx nWWx n WWX k第3章 離散傅里葉變換(DFT) 證明證明2)()()(kXWmnxDFSmnxDFSmkNN ()( ) ()( ) ()( )( )( )( )NNNNmkNNmkNDFT x nmRnDFT x

24、 nm RnDFS x nm RnWX k RkWX k第3章 離散傅里葉變換(DFT) 3 頻域循環(huán)移位定理頻域循環(huán)移位定理如果X(k)=DFTx(n)N 0kN1Y(k)=X(k+l)NRN(k)則(3.2.4)(3.2.4)式的證明方法與時域循環(huán)移位定理類似，直接對Y(k)=X(k+l)NRN(k)進(jìn)行IDFT即得證。( )IDFT ( )( )nlNNy nY kW x n第3章 離散傅里葉變換(DFT) 說 明 本 性 質(zhì) 與 時 域 移 位 性 質(zhì) 成 對 偶 關(guān) 系. 本 性 質(zhì) 又 稱 調(diào) 制 特 性, 時 域 序 列 的 調(diào) 制 等 效 于 頻 域 移 位. 注 意 是 圓

25、周 移 位 . 由 此 性 質(zhì) 可 得 出 以 下 兩 個 公 式:第3章 離散傅里葉變換(DFT) 3.2.3 循環(huán)卷積定理循環(huán)卷積定理時域循環(huán)卷積定理是DFT中最重要的定理，具有很強(qiáng)的實用性。已知系統(tǒng)輸入和系統(tǒng)的單位脈沖響應(yīng)，計算系統(tǒng)的輸出，以及FIR濾波器用FFT實現(xiàn)等，都是基于該定理的。下面首先介紹循環(huán)卷積的概念和計算循環(huán)卷積的方法，然后介紹循環(huán)卷積定理。1 兩個有限長序列的兩個有限長序列的循環(huán)卷積循環(huán)卷積設(shè)序列h(n)和x(n)的長度分別為N1和N2 。h(n)與x(n)的N點(diǎn)循環(huán)卷積定義為（3.2.5）1c0( )( ) ()( )NNNmy nh m x nmRn第3章 離散傅里

26、葉變換(DFT) 式中，L稱為循環(huán)卷積區(qū)間長度，LmaxN，M。上式顯然與第1章介紹的線性卷積不同，為了區(qū)別線性卷積，用 *表示循環(huán)卷積，用表示L點(diǎn)循環(huán)卷積，即yc(n)=h(n)x(n)。觀察（3.2.5）式，x(nm)L是以L為周期的周期信號，n和m的變化區(qū)間均是0, L1，第3章 離散傅里葉變換(DFT) 1 1、 圓圓 周周 卷卷 積積 定定 義義2 2、圓、圓 周周 卷卷 積積 的的 實實 現(xiàn)現(xiàn) 步步 驟驟圓周卷積圓周卷積第3章 離散傅里葉變換(DFT) 卷積過程可以用圖3-15來表示。圓周卷積過程中，求和變量為m, n為參變量。先將x2(m)周期化，形成x2(m)N，再反轉(zhuǎn)形成x2

27、(-m)N，取主值序列則得到x2(-m)NRN(m)，通常稱之為x2(m)的圓周反轉(zhuǎn)。對x2(m)的圓周反轉(zhuǎn)序列圓周右移n，形成x2(n-m)NRN(m)，當(dāng)n=0,1,2,N-1時，分別將x1(m)與x2(n-m)NRN(m)相乘，并在m=0 到N-1 區(qū)間內(nèi)求和，便得到圓周卷積y(n)。 可以看出,它和周期卷積過程是一樣的，只不過這里要取主值序列。特別要注意，兩個長度小于等于N的序列的N點(diǎn)圓周卷積長度仍為N，這與一般的線性卷積不同。圓周卷積用符號來表示。 圓周內(nèi)的N表示所作的是N點(diǎn)圓周卷積。 N第3章 離散傅里葉變換(DFT) 圖圖 3-15 圓周卷積過程示意圖圓周卷積過程示意圖 x1(n

28、)1N1nx2(n)1N1nx2(0 m)NRN(m)1N1mooo第3章 離散傅里葉變換(DFT) 圖圖 3-15 圓周卷積過程示意圖圓周卷積過程示意圖 x2(1 m)NRN(m)1N1mx2(2 m)NRN(m)1N1my(n) x1(n) x2(n)233211N1noooN第3章 離散傅里葉變換(DFT) 當(dāng)n = 0, 1, 2, , L1時，由x(n)形成的序列為: x(0), x(1), , x(L1)。令n=0, m=0, 1, , L1，由式（3.2.5）中x(n-m)L形成x(n)的循環(huán)倒相序列為與序列x(n)進(jìn)行對比，相當(dāng)于將第一個序列值x(0)不動，將后面的序列反轉(zhuǎn)18

29、0再放在 x(0) 的后面。這樣形成的序列稱為x(n)的循環(huán)倒相序列。(0) , ( 1) , ( 2) , , (1) (0), (1), (2), , (1)LLLLxxxxLxx Lx Lx直接計算該式比較麻煩。計算機(jī)中采用矩陣相乘或快速傅里葉變換（FFT）的方法計算循環(huán)卷積。第3章 離散傅里葉變換(DFT) 令n = 1, m = 0, 1, , L-1，由式（3.2.5）中x(n-m)L形成的序列為觀察上式等號右端序列，它相當(dāng)于x(n)的循環(huán)倒相序列向右循環(huán)移一位，即向右移1位，移出區(qū)間0, L1的序列值再從左邊移進(jìn)。再令n = 2, m = 0, 1, , L1，此時得到的序列又是

30、上面的序列向右循環(huán)移1位。依次類推，當(dāng)n和m均從0變化到L-1時，得到一個關(guān)于x(nm)L的矩陣如下： (1) , (0) , ( 1) , , (2) (1), (0), (1), , (2)LLLLxxxxLxxx Lx第3章 離散傅里葉變換(DFT) （3.2.6） (0)(1)(2)(1)(1)(0)(1)(2)(2)(1)(0)(3)(1)(2)(3)(0)xx Lx Lxxxx Lxxxxxx Lx Lx Lx第3章 離散傅里葉變換(DFT) 上面矩陣稱為x(n)的L點(diǎn)“循環(huán)卷積矩陣”，其特點(diǎn)是:（1） 第1行是序列x(0), x(1), , x(L1)的循環(huán)倒相序列。注意，如果x

31、(n)的長度ML，則需要在x(n)末尾補(bǔ)LM個零后，再形成第一行的循環(huán)倒相序列。（2） 第1行以后的各行均是前一行向右循環(huán)移1位形成的。（3） 矩陣的各主對角線上的序列值均相等。有了上面介紹的循環(huán)卷積矩陣，就可以寫出式（3.2.5）的矩陣形式如下:第3章 離散傅里葉變換(DFT) （3.2.7） cccc(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 Lxhyxxx Lxhyxxxxhy Lx Lx Lx Lxh L按照上式，可以在計算機(jī)上用矩陣相乘的方法計算兩個序列的循環(huán)卷積，這里關(guān)

32、鍵是先形成循環(huán)卷積矩陣。上式中如果h(n)的長度NL，則需要在h(n)末尾補(bǔ)LN個零。第3章 離散傅里葉變換(DFT) 【例例3.2.1】 計算下面給出的兩個長度為4的序列h(n)與x(n)的4點(diǎn)和8點(diǎn)循環(huán)卷積。 ( )(0), (1), (2), (3)1,2,3,4( )(0), (1), (2), (3)1,1,1,1h nhhhhx nxxxx解解 按照式（3.2.21）寫出h(n)與x(n)的4點(diǎn)循環(huán)卷積矩陣形式為cccc(0)1432110(1)2143110(2)3214110(3)4321110yyyy 第3章 離散傅里葉變換(DFT) cccccccc(0)111000043

33、2(1)1321000043(2)1632100004(3)110432100000904321000(4)0043210007(5)00043210(6)0400004321(7)0yyyyyyyy 0h(n)與x(n)的8點(diǎn)循環(huán)卷積矩陣形式為第3章 離散傅里葉變換(DFT) h(n)和x(n)及其4點(diǎn)和8點(diǎn)循環(huán)卷積結(jié)果分別如圖3.2.2(a)、(b)、(c)和(d)所示。請讀者計算驗證本例的8點(diǎn)循環(huán)卷積結(jié)果等于h(n)與x(n)的線性卷積結(jié)果。后面將證明，當(dāng)循環(huán)卷積區(qū)間長度L大于等于y(n) = h(n)*x(n)的長度時，循環(huán)卷積結(jié)果就等于線性卷積。 第3章 離散傅里葉變換(DFT) 圖

34、3.2.2 序列及其循環(huán)卷積波形第3章 離散傅里葉變換(DFT) 2. 循環(huán)卷積定理循環(huán)卷積定理 有限長序列x1(n)和x2(n)的長度分別為N1和N2，N=maxN1, N2，x1(n)和x2(n)的N點(diǎn)循環(huán)卷積為（3.2.8）則x(n)的N點(diǎn)DFT為其中2( )( )x nx nN 11210( )( )()( )NNNmx nx m xnmRn12( )DFT ( )( )( )NX kx nX kXk（3.2.9）1122( )DFT( ) ,( )DFT( )NNX kx nXkx n第3章 離散傅里葉變換(DFT) 證明證明 直接對(3.2.8)式兩邊進(jìn)行DFT，則有1112001

35、11200( )DFT ( )( )()( )( )()NNNknNNNnmNNknNNmnX kx nx m xnmRn Wx mxnmW 第3章 離散傅里葉變換(DFT) 令nm=n，則有因為上式中是以N為周期的，所以對其在任一個周期上求和的結(jié)果不變。因此10121101)(21)()()()()(NmmNmnknNNkmNNmmNmnmnkNNWnxWmxWnxmxkX2)(knNNWnx第3章 離散傅里葉變換(DFT) 由于，因此即循環(huán)卷積亦滿足交換律。 10)()() ()()(21101021NkkXkXWnxWmxkXNmNnknNkmN，1221( )DFT ( )( )( )

36、( )( )X kx nX k XkXk X k1221( )IDFT( )( )( )( )( )x nX kx nx nx nx n第3章 離散傅里葉變換(DFT) 作為習(xí)題請讀者證明以下頻域循環(huán)卷積定理:如果x(n)=x1(n)x2(n)，則(3.2.10a) 11( )DFT ( )( )NX kx nX kN2( )XkN 11201( )()( )NNNlX l XklRkN第3章 離散傅里葉變換(DFT) 112101( )( )()( )NNNlX kXl XklRkN或(3.2.10b)式中相對頻域循環(huán)卷積定理，稱(3.2.9)式為時域循環(huán)卷積定理。 21( )( )X kX

37、kNN 1122 ( )DFT ( )01( )DFT( )NNX kx nkNXkx n第3章 離散傅里葉變換(DFT) 補(bǔ)充：循環(huán)反褶性質(zhì)補(bǔ)充：循環(huán)反褶性質(zhì)11)(0)0()()(11)(0)0()(NkkNXkXkXnxDFTNkkNxkxnxNNN第3章 離散傅里葉變換(DFT) 補(bǔ)充：補(bǔ)充： 有限長序列的線性卷積與圓周卷積有限長序列的線性卷積與圓周卷積 時域圓周卷積在頻域上相當(dāng)于兩序列的DFT的乘積，而計算DFT可以采用它的快速算法快速傅里葉變換（FFT）（見第4章）， 因此圓周卷積與線性卷積相比，計算速度可以大大加快。 但是實際問題大多總是要求解線性卷積。例如，信號通過線性時不變系

38、統(tǒng)，其輸出就是輸入信號與系統(tǒng)的單位脈沖響應(yīng)的線性卷積， 如果信號以及系統(tǒng)的單位脈沖響應(yīng)都是有限長序列， 那么是否能用圓周卷積運(yùn)算來代替線性卷積運(yùn)算而不失真呢？下面就來討論這個問題。 設(shè)x1(n)是N1點(diǎn)的有限長序列（0nN1-1），x2(n)是N2點(diǎn)的有限長序列（0nN2-1）。 第3章 離散傅里葉變換(DFT) （1）先看它們的線性卷積 1021212111)()()()()()()(Nmmmnxmxmnxmxnxnxnyx1(m)的非零區(qū)間為 0mN1-1 x2(n-m)的非零區(qū)間為 0n-mN2-1 (2-43)第3章 離散傅里葉變換(DFT) 將兩個不等式相加，得到 0nN1+N2-2

39、 在上述區(qū)間外，不是x1(m)=0就是x2(n-m)=0，因而y1(n)=0。所以y1(n)是N1+N2-1 點(diǎn)有限長序列，即線性卷積的長度等于參與卷積的兩序列的長度之和減1。第3章 離散傅里葉變換(DFT) （2）我們再來看x1(n)與x2(n)的圓周卷積。先假設(shè)進(jìn)行L點(diǎn)的圓周卷積，再討論L取何值時，圓周卷積才能代表線性卷積。 設(shè)y(n)=x1(n)x2(n)是兩序列的L點(diǎn)圓周卷積，LmaxN1, N2，這就要將x1(n)與x2(n)都看成是L點(diǎn)的序列。在這L個序列值中，x1(n)只有前N1個是非零值，后L-N1個均為補(bǔ)充的零值。同樣， x2(n)只有前N2個是非零值，后L-N2個均為補(bǔ)充的

40、零值。則 L102121)()()()()()(LmLLnRmnxmxnxnxnyL（2-44） 第3章 離散傅里葉變換(DFT) 為了分析其圓周卷積，我們先將序列x1(n)與x2(n)以L為周期進(jìn)行周期延拓 )()()()()()(222111rLnxnxnxkLnxnxnxrLkL它們的周期卷積序列為 )()()()()()()()(1210121012101rLnymrLnxmxmrLnxmxmnxmxnyrLmrrLmLLm（2-45） 第3章 離散傅里葉變換(DFT) 前面已經(jīng)分析了y1(n)具有N1+N2-1個非零值。因此可以看到， 如果周期卷積的周期LN1+N2-1，那么y1(n

41、)的周期延拓就必然有一部分非零序列值要交疊起來，從而出現(xiàn)混疊現(xiàn)象。只有在LN1+N2-1 時，才沒有交疊現(xiàn)象。這時, 在y1(n)的周期延拓 中， 每一個周期L內(nèi)，前N1+N2-1個序列值正好是y1(n)的全部非零序列值，而剩下的L-(N1+N2-1)個點(diǎn)上的序列值則是補(bǔ)充的零值。 圓周卷積正是周期卷積取主值序列 )(1ny)()()(1nRrLnynyLr)()()()()(21nRnynxnxnyLL因此 (2-46)第3章 離散傅里葉變換(DFT) 所以要使圓周卷積等于線性卷積而不產(chǎn)生混疊的必要條件為 121NNL（2-47） 滿足此條件后就有 )()(1nyny即 x1(n) x2(n

42、)=x1(n)*x2(n) L 下圖（d）、（e）、（f）正反映了（2-46）式的圓周卷積與線性卷積的關(guān)系。在圖2-16（d）中，L=6小于N1+N2-1=8，這時產(chǎn)生混疊現(xiàn)象，其圓周卷積不等于線性卷積；而在圖2-16（e）、（f）中, L=8和L=10，這時圓周卷積結(jié)果與線性卷積相同，所得y(n)的前8點(diǎn)序列值正好代表線性卷積結(jié)果。 所以只要LN1+N2-1，圓周卷積結(jié)果就能完全代表線性卷積。 第3章 離散傅里葉變換(DFT) 圖 線性卷積與圓周卷積第3章 離散傅里葉變換(DFT) 例例 一個有限長序列為 )5(2)()(nnnx（1） 計算序列x(n)的10點(diǎn)離散傅里葉變換。（2） 若序列

43、y(n)的DFT為 )()(1022kXekYkj式中，X(k)是x(n)的10點(diǎn)離散傅里葉變換，求序列y(n)。 第3章 離散傅里葉變換(DFT) （3）若10點(diǎn)序列y(n)的10點(diǎn)離散傅里葉變換是 )()()(kWkXkY式中, X(k)是序列x(n)的10點(diǎn)DFT，W(k)是序列w(n)的10點(diǎn)DFT 01)(nw0n6 其他 求序列y(n)。 第3章 離散傅里葉變換(DFT) 解解 （1） 由式（2-30）可求得x(n)的10點(diǎn)DFT kkjknkNnnnkNeWWnnWnxkX) 1(212121)5(2)()()(510251010101100 （2）X(k)乘以一個WNkm形式的

44、復(fù)指數(shù)相當(dāng)于是x(n)圓周移位m點(diǎn)。 本題中m=-2, x(n)向左圓周移位了2點(diǎn)， 就有 y(n)=x(n+2)10R10(n)=2(n-3)+(n-8) 90 k第3章 離散傅里葉變換(DFT) （3）X(k)乘以W(k)相當(dāng)于x(n)與w(n)的圓周卷積。為了進(jìn)行圓周卷積，可以先計算線性卷積再將結(jié)果周期延拓并取主值序列。 x(n)與w(n)的線性卷積為z(n)=x(n)*w(n)=1, 1, 1, 1, 1, 3, 3, 2, 2, 2, 2, 2圓周卷積為 )()10()(10nRrnznyr 在 0n9 求和中，僅有序列z(n)和z(n+10)有非零值，用表列出z(n)和z(n+10

45、)的值，對n=0, 1, 2, , 9求和，得到： 第3章 離散傅里葉變換(DFT) n0 1 2 3 4 5 6 7 8 910 11Z(n)z(n+10) 1 1 1 1 1 3 3 2 2 22 2 0 0 0 0 0 0 0 02 20 0y(n)3 3 1 1 1 3 3 2 2 2_ _所以10點(diǎn)圓周卷積為 y(n)=3, 3, 1, 1， 1, 3, 3, 2, 2, 2 第3章 離散傅里葉變換(DFT) 2.5.5 共軛對稱性共軛對稱性 設(shè)x*(n)為x(n)的共軛復(fù)序列，則 DFTx*(n)=X*(-k)NRN(k)=X*(N-k)NRN(k) =X*(N-k) 0kN-1

46、且 X(N)=X(0) （2-48） 證證 )(*)()(*)()()()(*)()()()(*)(*10)(10*10kNXkRkNXkRWnxkRkXkRWnxkRWnxnxDFTNNNNnnkNNNNNnNNnnkNNnkN0kN-1 第3章 離散傅里葉變換(DFT) 3.2.4 復(fù)共軛序列的復(fù)共軛序列的DFT 設(shè)x*(n)是x(n)的復(fù)共軛序列，長度為N，X(k)=DFTx(n)N，則(3.2.11)且X(N)=X(0)。證明證明 根據(jù)DFT的唯一性，只要證明(3.2.11)式右邊等于左邊即可。DFTx*(n)=X*(-k)NRN(k)=X*(N-k)NRN(k) =X*(N-k) 0

47、kN-1 第3章 離散傅里葉變換(DFT) 又由X(k)的隱含周期性，有X(N)=X(0)用同樣的方法可以證明 (3.2.12)11*()*()001*0()( )( )( )DFT( )NNN k nN k nNNnnNknNNnXNkx n Wx n Wx n Wx n*DFT()( )NxNnXk122njnNNjnNNeeW這里利用了 第3章 離散傅里葉變換(DFT) 3.2.5 DFT的共軛對稱性的共軛對稱性1 有限長共軛對稱序列和共軛反對稱序列有限長共軛對稱序列和共軛反對稱序列為了區(qū)別于傅里葉變換中所定義的共軛對稱（或共軛反對稱）序列，下面用xep(n)和xop(n)分別表示有限長

48、共軛對稱序列和共軛反對稱序列，則二者滿足如下關(guān)系式：(3.2.13a)(3.2.13b)*epep( )() 01xnxNnnN*opop( )() 01xnxNnnN 第3章 離散傅里葉變換(DFT) 當(dāng)N為偶數(shù)時，將上式中的n換成N/2n，可得到：上式更清楚地說明了有限長序列共軛對稱序列是關(guān)于n=N/2點(diǎn)對稱。容易證明，如同任何實函數(shù)都可以分解成偶對稱分量和奇對稱分量一樣，任何有限長序列x(n)都可以表示成其共軛對稱分量和共軛反對稱分量之和，即 *epep()() 01222NNNxnxnn*opop()() 01222NNNxnxnn 第3章 離散傅里葉變換(DFT) (3.2.14)

49、將上式中的n換成Nn，并取復(fù)共軛，再將(3.2.13a)式和(3.2.13b)式代入，得到：(3.2.15)(3.2.14)式分別加減(3.2.15)式，可得(3.2.16a)(3.2.16b)epop( )( )( )01x nxnxnnN*epopepop()()()( )( )xNnxNnxNmxnxn*ep1( ) ( )()2xnx nxNn*op1( ) ( )()2xnx nxNn第3章 離散傅里葉變換(DFT) 2 DFT的共軛對稱性的共軛對稱性 (1) 如果將x(n)表示為x(n)=xr(n)+jxi(n) (3.2.17)其中那么，由(3.2.11)式和(3.2.16a)式

50、可得*r*i1( )Re ( ) ( )( )21j ( )jIm ( ) ( )( )2x nx nx nx nx nx nx nx n第3章 離散傅里葉變換(DFT) (3.2.18) 由(3.2.11)式和(3.2.16b)式可得 (3.2.19)*rep11DFT( )DFT ( )( )( )()( )22x nx nx nX kXNkXk*iop11DFTj ( )DFT ( )( )( )()( )22x nx nx nX kXNkXk第3章 離散傅里葉變換(DFT) 由DFT的線性性質(zhì)即可得 (3.2.20)其中，Xop(k)=DFTxr(n)是X(k)的共軛對稱分量，Xop(

51、k)=DFTjxi(n)是X(k)的共軛反對稱分量。 (2) 如果將x(n)表示為(3.2.21) epop( )DFT ( )( )( )X kx nXkXkepop( )( )( )01x nxnxnnN第3章 離散傅里葉變換(DFT) 其中，是x(n)的共軛對稱分量，是x(n)的共軛反對稱分量, 那么，由(3.2.12)式可得*ep1( ) ( )()2xnx nxNn*op1( ) ( )()2xnx nxNn*ep11DFT( )DFT ( )()( )( )Re( )22xnx nxNnX kXkX k*op11DFT( )DFT ( )()( )( )Im( )22xnx nxN

52、nX kXkjX k第3章 離散傅里葉變換(DFT) 因此 (3.2.22)其中RI( )DFT ( )( )j( )X kx nXkX kRep( )Re( )DFT()XkX kxIopj( )jIm( )( )X kX kDFT xn第3章 離散傅里葉變換(DFT) 綜上所述，可總結(jié)出DFT的共軛對稱性質(zhì)：如果序列x(n)的DFT為X(k)，則x(n)的實部和虛部（包括j）的DFT分別為X(k)的共軛對稱分量和共軛反對稱分量；而x(n)的共軛對稱分量和共軛反對稱分量的DFT別為X(k)的實部和虛部乘以j。第3章 離散傅里葉變換(DFT) 共軛對稱性第3章 離散傅里葉變換(DFT) 第3章

53、 離散傅里葉變換(DFT) XX10-23第3章 離散傅里葉變換(DFT) 另外，請讀者根據(jù)上述共軛對稱性證明有限長實序列另外，請讀者根據(jù)上述共軛對稱性證明有限長實序列DFT的共軛對稱性（見本章習(xí)題題的共軛對稱性（見本章習(xí)題題7）。 設(shè)x(n)是長度為N的實序列，且X(k)=DFTx(n)N，*( )()( )( )( )()( )NNNDFT x nXkx nx nX kXkRk NNNNkXkXkXkXsequenceoddcircularkNXkXsequenceevencircularkXkX)()(|)(| )(|: )(Im)(Im: )(Re)(Re第3章 離散傅里葉變換(DFT

54、) 設(shè)x(n)是長度為N的實序列，且X(k)=DFTx(n)N，則X(k)滿足如下對稱性： (1) X(k)共軛對稱，即X(k)=X*(N-k) k=0, 1, , N-1 (3.2.23) (2) 如果x(n)是偶對稱序列，即x(n)=x(Nn)，則X(k)實偶對稱，即X(k)=X(Nk) (3.2.24) (3) 如果是奇對稱序列，即x(n)=x(Nn)，則X(k)純虛奇對稱，即X(k)=X(Nk) (3.2.25)第3章 離散傅里葉變換(DFT) 奇奇 偶偶 虛虛 實實 關(guān)關(guān) 系系 表表 奇奇 - - 指序列是指序列是圓周圓周奇對稱序列奇對稱序列 偶偶 - - 指序列是指序列是圓周圓周偶

55、對稱序列偶對稱序列虛虛 - - 指序列是純虛序列指序列是純虛序列實實 - - 指序列是實序列指序列是實序列圓周圓周奇對稱序列奇對稱序列圓周圓周偶對稱序列偶對稱序列1)1)各序列都是有限長序列各序列都是有限長序列( (隱含周期性隱含周期性) )2) 2) 根據(jù)時域根據(jù)時域, ,頻域的對偶性質(zhì)頻域的對偶性質(zhì), , 上表的時域與頻域可以互調(diào)上表的時域與頻域可以互調(diào)第3章 離散傅里葉變換(DFT) 實際中經(jīng)常需要對實序列進(jìn)行DFT，利用上述對稱性質(zhì)，可減少DFT的運(yùn)算量，提高運(yùn)算效率。例如，計算實序列的N點(diǎn)DFT時，當(dāng)N=偶數(shù)時，只需計算X(k)的前面N/2+1點(diǎn)，而N = 奇數(shù)時，只需計算X(k)的

56、前面(N+1)/2點(diǎn)，其他點(diǎn)按照(3.2.22)式即可求得。例如， X(N1)=X*(1), X(N2)=X*(2), 這樣可以減少近一半運(yùn)算量。X(k)=X*(N-k) k=0, 1, , N-1 第3章 離散傅里葉變換(DFT) 【例例3.2.2】 利用DFT的共軛對稱性，設(shè)計一種高效算法，通過計算一個N點(diǎn)DFT，就可以計算出兩個實序列x1(n)和x2(n)的N點(diǎn)DFT。解解構(gòu)造新序列x(n)=x1(n)+jx2(n)，對x(n)進(jìn)行DFT，得到：第3章 離散傅里葉變換(DFT) 由(3.2.17)、(3.2.18)和(3.2.19)式得到：所以，由X(k)可以求得兩個實序列x1(n)和x

57、2(n)的N點(diǎn)DFT：epop( )DFT ( )( )( )X kx nXkXk*ep11( )DFT( )( )()2Xkx nX kXNk*op21( )DFTj( )( )()2Xkx nX kXNk)()(21)()(*11kNXkXnxDFTkX*221( )DFT( )j ( )()2Xkx nX kXNk 第3章 離散傅里葉變換(DFT) 補(bǔ)充. Parsevals relation:102102| )(|1| )(|NkNnxkXNnxE1010*)(*)(1)()(NkNnkYkXNnynx*111*000111*0001( )( )( )( )11( )( )( )( )

58、NNNknNnnkNNNknNknnx n y nx nYk WNYkx n WX k YkNN第3章 離散傅里葉變換(DFT) 補(bǔ)充.Duality(對偶性)-補(bǔ)充第3章 離散傅里葉變換(DFT) 第3章 離散傅里葉變換(DFT) 3.頻域采樣理論頻域采樣理論 首先，考慮一個任意的絕對可和的非周期序列x(n)，它的Z變換為 nnznxzX)()(由于絕對可和，所以其傅里葉變換存在且連續(xù)，故Z變換收斂域包括單位圓。如果我們對X(z)在單位圓上進(jìn)行N點(diǎn)等距采樣： 1, 1 , 0)()()(NkWnxzXkXnkNnWzkN（3-64） 第3章 離散傅里葉變換(DFT) 問題在于，這樣采樣以后是

59、否仍能不失真地恢復(fù)出原序列x(n)。 也就是說，頻率采樣后從X(k)的反變換中所獲得的有限長序列， 即xN(n)=IDFTX(k)，能不能代表原序列x(n)？為此，我們先來分析X(k)的周期延拓序列 的離散傅里葉級數(shù)的反變換， 令其為 。)(kX)(nxNnkNNknkNNkNWkXNWkXNkXIDFSnx1010)(1)(1)()( mNkknmNnkNNkmmkNNWNmxWWmxNnx10)(101)()(1)(將式（3-64）代入此式，可得 第3章 離散傅里葉變換(DFT) 由于 10)(011NkknmNWNm=n+rN, r為任意整數(shù) 其他m 所以 rNrNnxnx)()(（3-

60、65） 這說明由 得到的周期序列 是原非周期序列x(n)的周期延拓，其時域周期為頻域采樣點(diǎn)數(shù)N。已經(jīng)知道，時域采樣造成頻域的周期延拓，這里又看到一個對稱的特性，即頻域采樣同樣會造成時域的周期延拓。 )(kX)(nxN第3章 離散傅里葉變換(DFT) （1） 如果x(n)是有限長序列，點(diǎn)數(shù)為M，則當(dāng)頻域采樣不夠密，即當(dāng)NM時，x(n)以N為周期進(jìn)行延拓，就會造成混疊。這時，從 就不能不失真地恢復(fù)出原信號x(n)來。因此，對于M點(diǎn)的有限長序列x(n) )(nxN0)()(nxnx0nM-1 其他n 頻域采樣不失真的條件是頻域采樣點(diǎn)數(shù)N要大于或等于時域采樣點(diǎn)數(shù)M（時域序列長度），即滿足 NM （3-