第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ù)字信號(hào)處理中常用的重要數(shù)學(xué)變換。對(duì)于有限長(zhǎng)序列，還有一種更為重要的數(shù)學(xué)變換，即本章要討論的離散傅里葉變換(Discrete Fourier Transform，DFT)。DFT之所以更為重要，是因?yàn)槠鋵?shí)質(zhì)是有限長(zhǎng)序列傅里葉變換的有限點(diǎn)離散采

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

3、散傅里葉變換的定義及物理意義3.1.1 DFT的定義的定義 設(shè)x(n)是一個(gè)長(zhǎng)度為M的有限長(zhǎng)序列，則定義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ū)間長(zhǎng)度。通常稱(3.1.1)式和(3.1.2)式為離散傅里葉變換對(duì)。為了敘述簡(jiǎn)潔，常常用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由此可見(jiàn)，(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。這是一個(gè)很特殊的例子，它表明對(duì)序列(n)來(lái)說(shuō)，不論對(duì)它進(jìn)行多少點(diǎn)的DFT，所得結(jié)果都是一個(gè)離散矩形序列。 第3章 離散傅里葉變換(DFT) 圖2-9 序列(n)及其離散傅里葉變換 第3章 離散傅里葉變換(DFT) 例例 3.1.2 已知x(n)=cos(n/6)是一個(gè)長(zhǎng)度N=12的有限長(zhǎng)序列， 求它的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 有限長(zhǎng)序列及其DFT第3章 離散傅里葉變換(DFT) 例例 3.1.3 已知如下X(k):13)(kXk=0 1k9 求其10點(diǎn)IDFT。 解解 X(k)可以表示為 X(k)=1+2(k) 0k9 寫成這種形式后，就可以很容易確定離散傅里葉反變換。 由于一個(gè)單位脈沖序列的DFT為常數(shù)： 111( )( )( )( )1x nnX kDFT x n第3章 離散傅里葉變換(DFT

7、) 同樣，一個(gè)常數(shù)的DFT是一個(gè)單位脈沖序列： 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)的長(zhǎng)度為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的物理意義的物理意義。顯而易見(jiàn)，DFT的變換區(qū)間長(zhǎng)度N不同， 表示對(duì)X(ej)在區(qū)間0, 2上的采樣間隔和采樣點(diǎn)數(shù)不同， 所以DFT的變換結(jié)果也不同。 第3章 離散傅里葉變換(DFT) X(ej)在區(qū)間0, 2上的N點(diǎn)等間隔采樣。這就是DFT的物理意義。由此可見(jiàn)，DFT的變換區(qū)間長(zhǎng)度N不同，表示對(duì)X(ej)在區(qū)間0, 2上的采樣間隔和采樣點(diǎn)數(shù)不同，所以DFT的變換結(jié)果不同。上例中， x(n)=

9、R4(n)，DFT變換區(qū)間長(zhǎng)度N分別取8、16時(shí)，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變換對(duì)中，x(n)與X(k)均為有限長(zhǎng)序列，但由于的周期性，使(3.1.1)和(3.1.2)式中的X(k)隱含周期性，且周期均為N。對(duì)任意整數(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的第一個(gè)周期為的主值區(qū)間，而主值區(qū)間上的序列稱為的主值序列。因此x(n)與的上述關(guān)系可敘述為：是x(n)的周期延拓序列，x(n)是的主值序列。)

11、(nx)(nx)(nx)(nx)(nx)(nx實(shí)際上，任何周期為N的周期序列都可以看做長(zhǎng)度為N的有限長(zhǎng)序列x(n)的周期延拓序列，而x(n)則是 的一個(gè)周期，即)(nx)(nx第3章 離散傅里葉變換(DFT) 為了以后敘述簡(jiǎn)潔，當(dāng)N大于等于序列x(n)的長(zhǎng)度時(shí)，將(3.1.5)式用如下形式表示：(3.1.7)式中x(n) N表示x(n)以N為周期的周期延拓序列，(n)N表示模N對(duì)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)說(shuō)明，若x(n)實(shí)際長(zhǎng)度為M，延拓周期為N，則當(dāng)NM時(shí)，(3.1.5)式仍表示以N為周期的周期序列，但(3.1.6)和 (3.1.7)式僅對(duì)NM時(shí)成立。圖3.1.2（a）中x(n)實(shí)際長(zhǎng)度M=6，當(dāng)延拓周期N=4時(shí)，如圖3.1.2（c）所示。 如果x(n)的長(zhǎng)度為M，且，NM，則可寫出的離散傅里葉級(jí)數(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)式相比較可知，有限長(zhǎng)序列x(n)的N點(diǎn)離散傅里葉變換X(k)正好是x(n)的周期延拓序列x(n)N的離散傅里葉級(jí)數(shù)系數(shù)的主值序列，即。后面要討論的頻域采樣理論將會(huì)加深對(duì)這一關(guān)系的理解。我們知道，周期延拓序列頻譜完全由其離散傅里葉級(jí)數(shù)系數(shù)確定，因此，X(k)實(shí)質(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 有限長(zhǎng)序列x(n)為 01)(nx0n4 其余n 求其N=5 點(diǎn)離散傅里葉變換X(k)。 解解 序列x(n)如圖2-12（a）所示。在確定DFT時(shí)，我們可以將x(n)看作是一個(gè)長(zhǎng)度N5的任意有限長(zhǎng)序列。首先我們以N=5 為周期將x(n)延拓成周期序列 ，如圖2-12（b）， 的DFS與x(n)的DFT相對(duì)應(yīng)。因?yàn)樵趫D2-12（ b）中的序列在區(qū)間0nN-1 上為常數(shù)值，所以可以得出 )(nx011)

15、()/2210)/2(NeeekXNkjkjNnnNkj（k=0, N, 2N, 其他 (2-35)第3章 離散傅里葉變換(DFT) 也就是說(shuō)，只有在k=0 和k=N 的整數(shù)倍處才有非零的DFS系數(shù) 值。這些DFS系數(shù)如圖2-12（c）所示。為了說(shuō)明傅里葉級(jí)數(shù) 與x(n)的頻譜X(ej)間的關(guān)系，在圖2-12（c）中也畫出了傅里葉變換的幅值|X（ej)|。顯然， 就是X(ej)在頻率k=2k/N 處的樣本序列。按照式（2-29），x(n)的DFT對(duì)應(yīng)于取 的一個(gè)周期而得到的有限長(zhǎ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的舉例說(shuō)明（a） 有限長(zhǎng)序列x(n); （b）由x(n)形成的周期N=10的周期序列x(n); （c） DFT的幅值 第3章 離散傅里葉變換(DFT) 圖 3-2 DFT的舉例說(shuō)明（a） 有限長(zhǎng)序列x(n); （b） 由x(n)形成的周期N=5的周期序列; （c） 對(duì)應(yīng)于 的傅里葉級(jí)數(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)。分別計(jì)算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計(jì)算xn=1 1 1 1; %輸入時(shí)域序列向量xn=R4(n)Xk16=fft(xn, 16); %計(jì)算xn的16點(diǎn)DFTXk32=fft(xn, 32);

18、%計(jì)算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的頻譜特性，因?yàn)镽5(n)5是一個(gè)直流序列，只有直流成分（即零頻率成分）。 第3章 離散傅里葉變換(DFT) 3.1.4 用用MATLAB計(jì)算序列的計(jì)算序列的DFTMATLAB提供了用快速傅里葉變換算法FFT(算法見(jiàn)第4章介紹)計(jì)算DFT的函數(shù)fft，其調(diào)用格

19、式如下: Xk = fft (xn, N)；調(diào)用參數(shù)xn為被變換的時(shí)域序列向量，N是DFT變換區(qū)間長(zhǎng)度，當(dāng)N大于xn的長(zhǎng)度時(shí)，fft函數(shù)自動(dòng)在xn后面補(bǔ)零。函數(shù)返回xn的N點(diǎn)DFT變換結(jié)果向量Xk。當(dāng)N小于xn的長(zhǎng)度時(shí)，fft函數(shù)計(jì)算xn的前面N個(gè)元素構(gòu)成的N長(zhǎng)序列的N點(diǎn)DFT，忽略xn后面的元素。 Ifft函數(shù)計(jì)算IDFT，其調(diào)用格式與fft函數(shù)相同，可參考help文件。第3章 離散傅里葉變換(DFT) 3.2 離散傅里葉變換的基本性質(zhì)離散傅里葉變換的基本性質(zhì)3.2.1 線性性質(zhì)線性性質(zhì)如果x1(n)和x2(n)是兩個(gè)有限長(zhǎng)序列，長(zhǎng)度分別為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)為有限長(zhǎng)序列，長(zhǎng)度為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得到，最后取的主值序列則得到有限長(zhǎng)序列x(n)的循環(huán)移位序列y(n)。 M=6, N=8,

21、 m=2時(shí)，x(n)及其循環(huán)移位過(guò)程如圖3.2.1所示。Nnxnx)()()(nx)(mnx)(mnx第3章 離散傅里葉變換(DFT) 顯然，y(n)是長(zhǎng)度為N的有限長(zhǎng)序列。觀察圖3.2.1可見(jiàn)，循環(huán)移位的實(shí)質(zhì)是將x(n)左移m位，而移出主值區(qū)(0nN1)的序列值又依次從右側(cè)進(jìn)入主值區(qū)?！把h(huán)移位”就是由此得名的。由循環(huán)移位的定義可知，對(duì)同一序列x(n)和相同的位移m，當(dāng)延拓周期N不同時(shí)，y(n)=x(n+m)NRn(n)則不同。請(qǐng)讀者畫出N = M=6，m=2時(shí)，x(n)的循環(huán)移位序列y(n)波形圖。第3章 離散傅里葉變換(DFT) 圖3.2.1 x(n)及其循環(huán)移位過(guò)程第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 時(shí)域循環(huán)移位定理時(shí)域循環(huán)移位定理 設(shè)x(n)是長(zhǎng)度為M（MN）的有限長(zhǎng)序列，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、式中求和項(xiàng)以N為周期，因此對(duì)其在任一周期上的求和結(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)式的證明方法與時(shí)域循環(huán)移位定理類似，直接對(duì)Y(k)=X(k+l)NRN(k)進(jìn)行IDFT即得證。( )IDFT ( )( )nlNNy nY kW x n第3章 離散傅里葉變換(DFT) 說(shuō) 明 本 性 質(zhì) 與 時(shí) 域 移 位 性 質(zhì) 成 對(duì) 偶 關(guān) 系. 本 性 質(zhì) 又 稱 調(diào) 制 特 性, 時(shí) 域 序 列 的 調(diào) 制 等 效 于 頻 域 移 位. 注 意 是 圓

25、周 移 位 . 由 此 性 質(zhì) 可 得 出 以 下 兩 個(gè) 公 式:第3章 離散傅里葉變換(DFT) 3.2.3 循環(huán)卷積定理循環(huán)卷積定理時(shí)域循環(huán)卷積定理是DFT中最重要的定理，具有很強(qiáng)的實(shí)用性。已知系統(tǒng)輸入和系統(tǒng)的單位脈沖響應(yīng)，計(jì)算系統(tǒng)的輸出，以及FIR濾波器用FFT實(shí)現(xiàn)等，都是基于該定理的。下面首先介紹循環(huán)卷積的概念和計(jì)算循環(huán)卷積的方法，然后介紹循環(huán)卷積定理。1 兩個(gè)有限長(zhǎng)序列的兩個(gè)有限長(zhǎng)序列的循環(huán)卷積循環(huán)卷積設(shè)序列h(n)和x(n)的長(zhǎng)度分別為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ū)間長(zhǎng)度，LmaxN，M。上式顯然與第1章介紹的線性卷積不同，為了區(qū)別線性卷積，用 *表示循環(huán)卷積，用表示L點(diǎn)循環(huán)卷積，即yc(n)=h(n)x(n)。觀察（3.2.5）式，x(nm)L是以L為周期的周期信號(hào)，n和m的變化區(qū)間均是0, L1，第3章 離散傅里葉變換(DFT) 1 1、 圓圓 周周 卷卷 積積 定定 義義2 2、圓、圓 周周 卷卷 積積 的的 實(shí)實(shí) 現(xiàn)現(xiàn) 步步 驟驟圓周卷積圓周卷積第3章 離散傅里葉變換(DFT) 卷積過(guò)程可以用圖3-15來(lái)表示。圓周卷積過(guò)程中，求和變量為m, n為參變量。先將x2(m)周期化，形成x2(m)N，再反轉(zhuǎn)形成x2

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

28、)1N1nx2(n)1N1nx2(0 m)NRN(m)1N1mooo第3章 離散傅里葉變換(DFT) 圖圖 3-15 圓周卷積過(guò)程示意圖圓周卷積過(guò)程示意圖 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時(shí)，由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)行對(duì)比，相當(dāng)于將第一個(gè)序列值x(0)不動(dòng)，將后面的序列反轉(zhuǎn)18

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

30、上面的序列向右循環(huán)移1位。依次類推，當(dāng)n和m均從0變化到L-1時(shí)，得到一個(gè)關(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)的長(zhǎng)度ML，則需要在x(n)末尾補(bǔ)LM個(gè)零后，再形成第一行的循環(huán)倒相序列。（2） 第1行以后的各行均是前一行向右循環(huán)移1位形成的。（3） 矩陣的各主對(duì)角線上的序列值均相等。有了上面介紹的循環(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ì)算機(jī)上用矩陣相乘的方法計(jì)算兩個(gè)序列的循環(huán)卷積，這里關(guān)

32、鍵是先形成循環(huán)卷積矩陣。上式中如果h(n)的長(zhǎng)度NL，則需要在h(n)末尾補(bǔ)LN個(gè)零。第3章 離散傅里葉變換(DFT) 【例例3.2.1】 計(jì)算下面給出的兩個(gè)長(zhǎng)度為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)所示。請(qǐng)讀者計(jì)算驗(yàn)證本例的8點(diǎn)循環(huán)卷積結(jié)果等于h(n)與x(n)的線性卷積結(jié)果。后面將證明，當(dāng)循環(huán)卷積區(qū)間長(zhǎng)度L大于等于y(n) = h(n)*x(n)的長(zhǎng)度時(shí)，循環(huán)卷積結(jié)果就等于線性卷積。 第3章 離散傅里葉變換(DFT) 圖

34、3.2.2 序列及其循環(huán)卷積波形第3章 離散傅里葉變換(DFT) 2. 循環(huán)卷積定理循環(huán)卷積定理 有限長(zhǎng)序列x1(n)和x2(n)的長(zhǎng)度分別為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) 證明證明 直接對(duì)(3.2.8)式兩邊進(jìn)行DFT，則有1112001

35、11200( )DFT ( )( )()( )( )()NNNknNNNnmNNknNNmnX kx nx m xnmRn Wx mxnmW 第3章 離散傅里葉變換(DFT) 令nm=n，則有因?yàn)樯鲜街惺且訬為周期的，所以對(duì)其在任一個(gè)周期上求和的結(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í)題請(qǐng)讀者證明以下頻域循環(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)式中相對(duì)頻域循環(huán)卷積定理，稱(3.2.9)式為時(shí)域循環(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ǔ)充： 有限長(zhǎng)序列的線性卷積與圓周卷積有限長(zhǎng)序列的線性卷積與圓周卷積 時(shí)域圓周卷積在頻域上相當(dāng)于兩序列的DFT的乘積，而計(jì)算DFT可以采用它的快速算法快速傅里葉變換（FFT）（見(jiàn)第4章）， 因此圓周卷積與線性卷積相比，計(jì)算速度可以大大加快。 但是實(shí)際問(wèn)題大多總是要求解線性卷積。例如，信號(hào)通過(guò)線性時(shí)不變系

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

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

41、)的周期延拓就必然有一部分非零序列值要交疊起來(lái)，從而出現(xiàn)混疊現(xiàn)象。只有在LN1+N2-1 時(shí)，才沒(méi)有交疊現(xiàn)象。這時(shí), 在y1(n)的周期延拓 中， 每一個(gè)周期L內(nèi)，前N1+N2-1個(gè)序列值正好是y1(n)的全部非零序列值，而剩下的L-(N1+N2-1)個(gè)點(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，這時(shí)產(chǎn)生混疊現(xiàn)象，其圓周卷積不等于線性卷積；而在圖2-16（e）、（f）中, L=8和L=10，這時(shí)圓周卷積結(jié)果與線性卷積相同，所得y(n)的前8點(diǎn)序列值正好代表線性卷積結(jié)果。 所以只要LN1+N2-1，圓周卷積結(jié)果就能完全代表線性卷積。 第3章 離散傅里葉變換(DFT) 圖 線性卷積與圓周卷積第3章 離散傅里葉變換(DFT) 例例 一個(gè)有限長(zhǎng)序列為 )5(2)()(nnnx（1） 計(jì)算序列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)乘以一個(gè)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)行圓周卷積，可以先計(jì)算線性卷積再將結(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、)的值，對(duì)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 共軛對(duì)稱性共軛對(duì)稱性 設(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ù)共軛序列，長(zhǎng)度為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的共軛對(duì)稱性的共軛對(duì)稱性1 有限長(zhǎng)共軛對(duì)稱序列和共軛反對(duì)稱序列有限長(zhǎng)共軛對(duì)稱序列和共軛反對(duì)稱序列為了區(qū)別于傅里葉變換中所定義的共軛對(duì)稱（或共軛反對(duì)稱）序列，下面用xep(n)和xop(n)分別表示有限長(zhǎng)

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

51、k)=DFTjxi(n)是X(k)的共軛反對(duì)稱分量。 (2) 如果將x(n)表示為(3.2.21) epop( )DFT ( )( )( )X kx nXkXkepop( )( )( )01x nxnxnnN第3章 離散傅里葉變換(DFT) 其中，是x(n)的共軛對(duì)稱分量，是x(n)的共軛反對(duì)稱分量, 那么，由(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的共軛對(duì)稱性質(zhì)：如果序列x(n)的DFT為X(k)，則x(n)的實(shí)部和虛部（包括j）的DFT分別為X(k)的共軛對(duì)稱分量和共軛反對(duì)稱分量；而x(n)的共軛對(duì)稱分量和共軛反對(duì)稱分量的DFT別為X(k)的實(shí)部和虛部乘以j。第3章 離散傅里葉變換(DFT) 共軛對(duì)稱性第3章 離散傅里葉變換(DFT) 第3章

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

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

55、對(duì)稱序列偶對(duì)稱序列虛虛 - - 指序列是純虛序列指序列是純虛序列實(shí)實(shí) - - 指序列是實(shí)序列指序列是實(shí)序列圓周圓周奇對(duì)稱序列奇對(duì)稱序列圓周圓周偶對(duì)稱序列偶對(duì)稱序列1)1)各序列都是有限長(zhǎng)序列各序列都是有限長(zhǎng)序列( (隱含周期性隱含周期性) )2) 2) 根據(jù)時(shí)域根據(jù)時(shí)域, ,頻域的對(duì)偶性質(zhì)頻域的對(duì)偶性質(zhì), , 上表的時(shí)域與頻域可以互調(diào)上表的時(shí)域與頻域可以互調(diào)第3章 離散傅里葉變換(DFT) 實(shí)際中經(jīng)常需要對(duì)實(shí)序列進(jìn)行DFT，利用上述對(duì)稱性質(zhì)，可減少DFT的運(yùn)算量，提高運(yùn)算效率。例如，計(jì)算實(shí)序列的N點(diǎn)DFT時(shí)，當(dāng)N=偶數(shù)時(shí)，只需計(jì)算X(k)的前面N/2+1點(diǎn)，而N = 奇數(shù)時(shí)，只需計(jì)算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的共軛對(duì)稱性，設(shè)計(jì)一種高效算法，通過(guò)計(jì)算一個(gè)N點(diǎn)DFT，就可以計(jì)算出兩個(gè)實(shí)序列x1(n)和x2(n)的N點(diǎn)DFT。解解構(gòu)造新序列x(n)=x1(n)+jx2(n)，對(duì)x(n)進(jìn)行DFT，得到：第3章 離散傅里葉變換(DFT) 由(3.2.17)、(3.2.18)和(3.2.19)式得到：所以，由X(k)可以求得兩個(gè)實(shí)序列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(對(duì)偶性)-補(bǔ)充第3章 離散傅里葉變換(DFT) 第3章 離散傅里葉變換(DFT) 3.頻域采樣理論頻域采樣理論 首先，考慮一個(gè)任意的絕對(duì)可和的非周期序列x(n)，它的Z變換為 nnznxzX)()(由于絕對(duì)可和，所以其傅里葉變換存在且連續(xù)，故Z變換收斂域包括單位圓。如果我們對(duì)X(z)在單位圓上進(jìn)行N點(diǎn)等距采樣： 1, 1 , 0)()()(NkWnxzXkXnkNnWzkN（3-64） 第3章 離散傅里葉變換(DFT) 問(wèn)題在于，這樣采樣以后是

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

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