信號(hào)分析與處理：第8章 離散傅里葉變換1

1、第8章 離散傅里葉變換8.1離散傅里葉變換(DFT)定義8.2離散傅里葉變換的性質(zhì)8.3用DFT計(jì)算線(xiàn)性卷積8.4頻域采樣8.5快速傅里葉變換(FFT)8.6 FFT的應(yīng)用從理論研究到工程實(shí)際L T I系統(tǒng)計(jì)算機(jī)可以處理的數(shù)據(jù)形式 離散有限：存儲(chǔ)、運(yùn)算離散：存儲(chǔ)空間、運(yùn)算速度有限時(shí)域?qū)﹄x散化后的序列截?cái)嗷蚣哟?頻域?qū)﹄x散信號(hào)的頻譜（周期）加窗即只取用一個(gè)周期 從理論研究到工程實(shí)際已有的理論基礎(chǔ) 時(shí)頻域均離散 8.1 離散傅里葉變換的定義8.1.1 離散傅里葉變換的定義從離散傅里葉級(jí)數(shù)DFS到離散傅里葉變換DFS變換對(duì)為： 由于對(duì)k和n都是以N為周期的，所以當(dāng)也是以N為周期時(shí)。其本身時(shí)，可以利用

2、DFS的周期性，只需要在時(shí)域和頻域各取一個(gè)周期，計(jì)算一個(gè)周期，將所得結(jié)果進(jìn)行周期延拓，即可以得到它們。是以N為周期時(shí)，則和是無(wú)限長(zhǎng)的，但在計(jì)算序列的頻譜和雖然 由于在DFS中，只用到一個(gè)周期的N個(gè)值，取它們的主值序列：x(n) (0 n N-1)和X(k) (0 k N-1)，等式依然成立，這就是離散傅里葉變換，即k=0,1, N-1 n=0,1, N-1 k=0,1, N-1 DFT并不是一個(gè)新的傅里葉變換形式，只不過(guò)是將DFS變換對(duì)中的序列取主值，就得到了DFT，將DFT進(jìn)行周期延拓就得到DFS，因此DFT隱含周期性。 DFT與DFS的關(guān)系：有限長(zhǎng)序列x(n)是非周期的，其頻譜應(yīng)該是連續(xù)的

3、，但用DFT得到的x(n)的頻譜是離散頻譜，這是由于將有限長(zhǎng)序列x(n)延拓成周期序列而造成的。 n=0,1, N-1 8.1.2 離散傅里葉變換（DFT）與離散傅里葉級(jí)數(shù)（DFS）的關(guān)系8.1.3 DFT與DTFT和ZT變換的關(guān)系 設(shè)x (n)是一個(gè)長(zhǎng)度為N的有限長(zhǎng)序列， 則x (n)的離散時(shí)間傅里葉變換為 將離散化，在02上從0開(kāi)始等間隔地取N個(gè)點(diǎn)，即即可得到離散傅里葉變換DFT。對(duì)X()進(jìn)行均勻采樣， 1. DTFT和DFT的關(guān)系 X(k) 是序列的傅立葉變換X() 的在區(qū)間0, 2上的N點(diǎn)等間隔采樣，采樣間隔為： N=2/N。為求DFT的反變換，將DFT兩邊乘以下面證明IDFT的唯一性

4、并對(duì)k從0到N-1求和，得上式右邊=Nx(n)n=0, 1, , N-12. DFT和Z變換的關(guān)系 比較z變換與DFT變換，可見(jiàn)當(dāng)設(shè)序列x(n)的長(zhǎng)度為N， 其z變換和DFT分別為：時(shí)，則有 X(k)也是z變換在單位圓上的N點(diǎn)等間隔采樣值，采樣間隔為：例 求x(n) = R4(n) 的DTFT及16點(diǎn)和32點(diǎn)的DFT。 解 根據(jù)DTFT的定義得 其頻譜為連續(xù)的，如圖(b)所示 設(shè)變換區(qū)間N=16， 則，n=0, 1, , 15根據(jù)DFT的定義得 圖6-1 DFT與DTFT的關(guān)系圖6-1(c) 為16點(diǎn)DFT的頻譜（實(shí)線(xiàn)），是離散的，實(shí)際上是對(duì)DTFT連續(xù)頻譜離散化的結(jié)果，虛線(xiàn)是DTFT的頻譜。

5、圖6-1(d) 為32點(diǎn)DFT的頻譜（其DFT變換省略）。 解：例 k1時(shí)，k1時(shí)，k7時(shí)，k7時(shí)， X(0)=X(2)=X(3)=X(4)=X(5)=X(6)=0當(dāng)k=7時(shí)，當(dāng)k=1時(shí)，解： X(0)=X(2)=X(3)=X(4)=X(5)=X(6)=0當(dāng)k=7時(shí)，DFT一般為復(fù)數(shù)當(dāng)k=1時(shí)，解：例 和 分別為 和 的N點(diǎn)DFT.若 和 是兩個(gè)有限長(zhǎng)度序列，長(zhǎng)度分別為 和 ，則其線(xiàn)性組合的N點(diǎn)DFT為 1. 線(xiàn)性性質(zhì)8.2 離散傅里葉變換的性質(zhì) 當(dāng)k的取值不受限制時(shí)，X(k) 以N為周期。2. DFT的隱含周期性設(shè)x*(n)是x(n)的復(fù)共軛序列， 長(zhǎng)度為N X(k)=DFTx(n)則 DF

6、Tx*(n)=X*(N-k), 0kN-1 且 X(N)=X(0)3. 復(fù)共軛序列的DFT證明：又由X(k)的隱含周期性有X(N)=X(0),它的末點(diǎn)就是它的起始點(diǎn)。用同樣的方法可以證明 DFTx*(N- n)=X*(k) 4. DFT的共軛對(duì)稱(chēng)性有限長(zhǎng)共軛對(duì)稱(chēng)序列和共軛反對(duì)稱(chēng)序列有限長(zhǎng)共軛對(duì)稱(chēng)序列： xep(n)=x*ep(N-n), 0nN-1有限長(zhǎng)共軛反對(duì)稱(chēng)序列：xop(n)= -x*op(N-n), 0nN-1DFT的對(duì)稱(chēng)性是關(guān)于N/2點(diǎn)的對(duì)稱(chēng)性。注意：X(k)也是序列， 對(duì)X(k)也成立。有限長(zhǎng)共軛對(duì)稱(chēng)序列有限長(zhǎng)共軛反對(duì)稱(chēng)序列4. DFT的共軛對(duì)稱(chēng)性有限長(zhǎng)共軛對(duì)稱(chēng)序列和共軛反對(duì)稱(chēng)序列

7、有限長(zhǎng)共軛對(duì)稱(chēng)序列： xep(n)=x*ep(N-n), 0nN-1有限長(zhǎng)共軛反對(duì)稱(chēng)序列：xop(n)= -x*op(N-n), 0nN-1DFT的對(duì)稱(chēng)性是關(guān)于N/2點(diǎn)的對(duì)稱(chēng)性。注意：X(k)也是序列， 對(duì)X(k)也成立。N/2左邊N/2右邊當(dāng)N為偶數(shù)時(shí)， 將上式中的n換成 可得到 任何有限長(zhǎng)序列x(n)都可以表示成其共軛對(duì)稱(chēng)分量和共軛反對(duì)稱(chēng)分量之和， 即 x(n)=xep(n)+xop(n), 0nN-1 將上式中的n換成N-n， 并取復(fù)共軛， 可得 x*(N-n) = x*ep(N-n) + x*op(N-n) = xep(n) - xop(n) xep(n)=x*ep(N-n), 0nN

8、-1xop(n)= -x*op(N-n), 0nN-11) 如果 x(n)=xep(n)+xop(n)， 0nN-1其中4. DFT的共軛對(duì)稱(chēng)性2) 如果 x(n)=xr(n)+jxi(n)其中 Xep(k)=DFTxr(n), 是X(k)的共軛對(duì)稱(chēng)分量; Xop(k)=DFTjxi(n), 是X(k)的共軛反對(duì)稱(chēng)分量。用同樣的方法可以證明具有共軛反對(duì)稱(chēng)性證明了 Xep(k)=DFTxr(n) 是X(k)的共軛對(duì)稱(chēng)分量。實(shí)際上設(shè)x(n)是長(zhǎng)度為N的實(shí)序列，且X(k)=DFTx(n)，對(duì)于純實(shí)數(shù)序列，x(n)=xr (n)，X(k)只有共軛偶對(duì)稱(chēng)部分，即X(k)=Xep(k)，表明實(shí)數(shù)序列的DF

9、T滿(mǎn)足共軛對(duì)稱(chēng)性，故 X(k)=X*(N-k)，0kN-1DFTx(n)=DFTxr(n)= X(k) =Xep(k) = X*ep (N-k) = X* (N-k)3) 實(shí)信號(hào)DFT的共軛對(duì)稱(chēng)性 X(k)=X*(N-k)，0kN-1 ，利用這一特性，只要知道一半數(shù)目的X(k)，就可得到另一半的X(k)，這一特點(diǎn)在DFT運(yùn)算中可以加以利用，以提高運(yùn)算效率。4) DFT的共軛對(duì)稱(chēng)性的意義 一次DFT變換兩個(gè)實(shí)序列。將兩個(gè)實(shí)序列， 構(gòu)成新序列x(n)如下 ： x(n)=x1(n)+jx2(n)對(duì)x(n)進(jìn)行DFT， 得到 X(k)=DFTx(n)=Xep(k)+Xop(k) 由Xep(k)=DFT

10、x1(n)=1/2X(k)+X*(N-k) Xop(k)=DFTjx2(n)=1/2X(k)-X*(N-k)得X1(k)=DFTx1(n)=1/2X(k)+X*(N-k) X2(k)=DFTx2(n)= -j1/2X(k)-X*(N-k) 5DFT的對(duì)偶性設(shè)長(zhǎng)度為N的序列 的DFT為 ，則對(duì)應(yīng)于DTFT的平移對(duì)應(yīng)于DFT的移位m1m3m2圓周移位序列6. DFT的圓周（循環(huán)）移位性質(zhì)循環(huán)移位示意圖右移出去的m個(gè)數(shù)據(jù)從左邊補(bǔ)進(jìn)來(lái)，數(shù)據(jù)不少，只是重新排隊(duì)。時(shí)域循環(huán)移位特性若時(shí)域序列的圓周位移的DFT為原來(lái)的DFT乘以一個(gè)因子則N為偶數(shù)時(shí) 若則頻域循環(huán)移位特性若則在頻域的頻移l，則IDFT在時(shí)域x(

11、n)乘以一個(gè)若則若x(n)和h(n)均為N點(diǎn)有限長(zhǎng)序列，且則N點(diǎn)的圓周卷積x(n)和h(n)都需是N點(diǎn)定義為圓周卷積兩序列循環(huán)卷積的長(zhǎng)度為N。7DFT的時(shí)域離散圓周卷積定理用DFT計(jì)算循環(huán)卷積則由時(shí)域循環(huán)卷積定理有 Y(k)=DFTy(n)=X1(k)X2(k), 0kN-1y(n)=IDFTY(k)當(dāng)L很大時(shí),在頻域計(jì)算提高了運(yùn)算速度。圓周卷積的計(jì)算特點(diǎn)圓卷積只在 區(qū)間內(nèi)進(jìn)行，圓卷積結(jié)果也為 N點(diǎn)有限長(zhǎng)序列。x(m)是把x(n )變量代換后的N點(diǎn)序列， 是把h(n )變量代換、圓反轉(zhuǎn)、圓移位后，取其前N個(gè)點(diǎn)后 的N點(diǎn)序列。對(duì)每一個(gè)n點(diǎn)圓移位，先計(jì)算對(duì)應(yīng)各個(gè)m點(diǎn)的乘積，再對(duì) 范圍內(nèi)的全部乘積求

12、和。每一個(gè)n點(diǎn)圓周卷積的計(jì)算包括：變量代換、圓反轉(zhuǎn)、圓移位、相乘、求和共5個(gè)步驟。以4點(diǎn)圓周卷積為例，全部過(guò)程可以用矩陣表示為：時(shí)域圓周卷積定理圓周卷積5個(gè)步驟的圖解舉例： 變量代換圓反轉(zhuǎn)圓移位相乘求和 例 用圖解法求有限長(zhǎng)序列 的4點(diǎn)圓卷積 。解 （1）變量代換xn、hn的變量置換為m，有 （2）圓反轉(zhuǎn)把hm圓反轉(zhuǎn)為 （3）圓移位相乘求和時(shí)域圓周卷積定理解 （3）圓移位相乘求和1234412342612相乘求和 圓周卷積 線(xiàn)性卷積 時(shí)域圓周卷積定理求和 圓周卷積5個(gè)步驟的圖解舉例： 變量代換圓反轉(zhuǎn)圓移位相乘求和 例 求有限長(zhǎng)序列 的4點(diǎn)圓卷積 。解：例 用時(shí)域卷積定理求有限長(zhǎng)序列 的4點(diǎn)圓卷

13、積 。解若則8DFT的頻域離散圓周卷積定理 實(shí)際問(wèn)題多數(shù)是求解線(xiàn)性卷積，如信號(hào)x(n)通過(guò)系統(tǒng)h(n)，其輸出就是線(xiàn)性卷積 y(n)=x(n)*h(n)。而循環(huán)卷積比起線(xiàn)性卷積，在運(yùn)算速度上有很大的優(yōu)越性，它可以采用快速傅里葉變換（FFT）技術(shù)，若能利用循環(huán)卷積求線(xiàn)性卷積，會(huì)帶來(lái)很大的方便。 現(xiàn)在我們來(lái)討論上述 x(n)與h(n)的線(xiàn)性卷積，如果 x(n)、h(n)為有限長(zhǎng)序列，則在什么條件下能用循環(huán)卷積代替而不產(chǎn)生失真。8.3 用DFT計(jì)算線(xiàn)性卷積(1) 有限長(zhǎng)序列線(xiàn)性卷積與循環(huán)卷積的關(guān)系線(xiàn)性卷積：循環(huán)卷積為：8.3 用DFT計(jì)算線(xiàn)性卷積有限長(zhǎng)序列x(n)為循環(huán)卷積為：即如果兩個(gè)序列的長(zhǎng)度分

14、別為N和M，線(xiàn)性卷積后的長(zhǎng)度為 N+M-1 ，因此，如果循環(huán)卷積的長(zhǎng)度 LN+M-1，那么，yl(n)周期延拓后，必然有一部分非零序列值要重疊，出現(xiàn)混疊現(xiàn)象。只有 LN+M-1 時(shí)，才不會(huì)產(chǎn)生混疊，此即循環(huán)卷積等于線(xiàn)性卷積的條件。(2) 循環(huán)卷積等于線(xiàn)性卷積的條件(3) 用DFT計(jì)算線(xiàn)性卷積的方法如果兩個(gè)序列h(n)和x(n)的長(zhǎng)度分別為N和M，取L=N+M-1作為循環(huán)卷積的長(zhǎng)度；在h(n)后補(bǔ)上L-N個(gè)零值點(diǎn)；在x(n)后補(bǔ)上L-M個(gè)零值點(diǎn)。321012N1-1序號(hào)計(jì)算結(jié)果1234000 xm1234000123h0-my0=144123400012h1-my1=13+24111234000

15、1h2-my2=12+23+34201234000h3-my3=11+22+33+44300123400h4-my4=21+32+43200012340h5-my5=31+42110001234h6-my6=414N1N2-1線(xiàn)性卷積上例線(xiàn)性卷積過(guò)程圖6-4 線(xiàn)性卷積與循環(huán)卷積的比較(a) 線(xiàn)性卷積 (b)循環(huán)卷積例 用DFT求的線(xiàn)卷積 。解8.4 頻率域采樣由X(k)不失真地恢復(fù)x(n)的條件是什么？采樣多少點(diǎn)才能由X(k)恢復(fù)x(n)?如果其收斂域包含單位圓(即x(n)存在傅里葉變換)。 在單位圓上對(duì)X(z)等間隔采樣N點(diǎn)得到0kN-11. 由X(k)不失真地恢復(fù)x(n)的條件xN(n)=IDFTX(k)， 0nN-1xN(n)=IDFTX(k)， 0nN-1采樣點(diǎn)N為多少