復(fù)試-哈工大通信原理課件dsp-chapter

第三章離散傅立葉變換（DiscreteFourierTransform——DFT）1、連續(xù)時(shí)間、連續(xù)頻率的傅立葉變換時(shí)域連續(xù)函數(shù)→頻域是非周期的時(shí)域非周期→頻域是連續(xù)的2、連續(xù)時(shí)間、離散頻率的傅立葉變換----傅立葉級(jí)數(shù)時(shí)域連續(xù)函數(shù)→頻域是非周期的時(shí)域周期性→頻域是離散的3、離散時(shí)間、連續(xù)頻率的傅立葉變換----序列的傅立葉變換時(shí)域離散化→頻域周期延拓時(shí)域非周期→頻域是連續(xù)的4、離散時(shí)間、離散頻率的傅立葉變換----離散傅立葉變換時(shí)域離散化→頻域周期延拓時(shí)域周期性→頻域離散化§3-1周期序列的離散傅立葉級(jí)數(shù)（DFS）

一、周期序列的傅立葉級(jí)數(shù)表示

設(shè)是周期為N的周期序列，可用一系列正弦或復(fù)指數(shù)序列來(lái)表示由于：

故：序列的離散傅立葉級(jí)數(shù)的諧波成分只有N個(gè)是獨(dú)立的成分（k=0,1,2,…,N-1)，所以，序列可展成離散傅立葉級(jí)數(shù)：二、離散傅立葉級(jí)數(shù)將上式兩邊乘以，并從n=0到N-1求和得由于：所以：即令則：令則所以k=6Re[z]Im[z]|z|=1k=0k=7=N-1k=1k=2k=3k=4k=5三、傅立葉級(jí)數(shù)的性質(zhì)1、線(xiàn)性2、序列位移3、對(duì)稱(chēng)性（1）共軛對(duì)稱(chēng)性（2）序列實(shí)部和虛部的對(duì)稱(chēng)性若則（3）周期序列的共軛對(duì)稱(chēng)部分的傅立葉級(jí)數(shù)和共軛反對(duì)稱(chēng)部分的傅立葉級(jí)數(shù)：若則(4)實(shí)偶周期序列傅立葉級(jí)數(shù)若則4、周期卷積

周期卷積是指兩周期序列的卷積，即

記為且有證明：X1(m）X2(m）X2(-m）X2(1-m）X2(2-m）X2(6-m）周期卷積N=7§3-2離散傅立葉變換(DFT)----有限長(zhǎng)序列的離散頻域表示

DFS(IDFS):周期序列→周期序列序列長(zhǎng)度均無(wú)限長(zhǎng)n,k:(-∞,∞)實(shí)際序列x(n)：有限長(zhǎng)希望頻域數(shù)據(jù)：有限長(zhǎng)對(duì)有限長(zhǎng)數(shù)據(jù)x(n)的處理：將x(n)周期開(kāi)拓，周期為N

即：構(gòu)造一周期序列或N=7r=1r=0r=-1n=-7,-7+7=0n=-6,-6+7=1n=-1,-1+7=6n=7,7-7=0n=8,8-7=1n=14,14-7=6-7-6-10178140123456,0≤n≤N-1

由于對(duì)不同r值，x(n+rN)之間并不重疊，故上式可寫(xiě)為稱(chēng)為余數(shù)運(yùn)算，或稱(chēng)為取模運(yùn)算

利用矩形序列：則

同樣，的傅立葉級(jí)數(shù)也可看成是某一有限長(zhǎng)序列的周期開(kāi)拓，其周期為N，即或于是，DFS可寫(xiě)為在主周期內(nèi)（0≤n≤N-1）,上式為：類(lèi)似地，有即

注意！雖然和都是有限長(zhǎng)序列，但他們是由周期序列截取主周期得到的，隱含有周期性。

§3-3Z變換的抽樣

一、離散傅立葉變換與Z變換的關(guān)系考察長(zhǎng)度為N的有限長(zhǎng)序列的Z變換

在平面單位圓取值在單位圓上等間隔抽樣

即：長(zhǎng)度為N的有限長(zhǎng)序列的DFT，等于其Z變換在單位圓上N個(gè)等間隔點(diǎn)的抽樣值，也即等于其傅立葉變換在范圍內(nèi)等間隔點(diǎn)上的值。

k=6Re[z]Im[z]|z|=1k=0k=7=N-1k=1k=2k=3k=4例:求下列等幅有限長(zhǎng)序列的離散傅立葉變換，并與其傅立葉變換的抽樣進(jìn)行比較。設(shè)抽樣點(diǎn)數(shù)為N=10。解：（1）

x(n)

的DFT為

即（2）x(n)的傅立葉變換為

即：在頻率點(diǎn)的抽樣值為

幅頻特性相頻特性012345678910+-++-二、頻域抽樣定理

1、抽樣對(duì)有限長(zhǎng)序列x(n),0≤n≤M-1,其Z變換為X(z)，對(duì)其在單位上作等間隔抽樣，抽樣點(diǎn)數(shù)為N對(duì)X(k)作DFT得由于：即x’(n)是x(n)以N為周期進(jìn)行周期開(kāi)拓截取主周期的結(jié)果。（1）若N<M，混疊，x’(n)≠x(n)（2）若N≥M，不混疊，x’(n)=x(n)抽樣定理：對(duì)有限長(zhǎng)序列x(n)的Z變換X(z)在單位圓上等間隔抽樣，抽樣點(diǎn)數(shù)為N，或抽樣間隔為，當(dāng)N≥M時(shí)，才可由X(k)不失真恢復(fù)X(jw)…..…..…..…..…..…..…..…..M-1N-NN-N2、內(nèi)插或?qū)懗善渲小?-4離散傅立葉變換的性質(zhì)

一、線(xiàn)性

式中為常數(shù)。的與的寬度。N為DFT長(zhǎng)度二、序列的循環(huán)位移

若，則用來(lái)代替。

三、對(duì)稱(chēng)性

1、序列的對(duì)稱(chēng)

設(shè)由開(kāi)拓成的周期序列為

則將和截取主周期，分別得

于是

N-10-(N-1)0-(N-1)N-1N-1-(N-1)2N-1x(n)x*(-n)xe(n)xo(n)xp(n)xp*(N-n)Xpet(n)Xpo(n)Xpe(n)Xpot(n)N-1非周期序列的共軛對(duì)稱(chēng)與反對(duì)稱(chēng)部分周期序列的共軛對(duì)稱(chēng)與反對(duì)稱(chēng)部分x(n)x*(N-n)Xpet(n)0N-1Xpot(n)N-12、用來(lái)表示和

由圖可見(jiàn)所以故同理因?yàn)樗?、的共軛序列的離散傅立葉變換

證明：4、的逆象的離散傅立葉變換

5、的逆象共軛的離散傅立葉變換

6、序列的實(shí)部和虛部的離散立葉變換

證明：

因?yàn)?/p>

所以

7、序列的周期共軛對(duì)稱(chēng)分量與周期共軛反對(duì)稱(chēng)分量的離散傅離葉變換

證明：

因?yàn)?/p>

所以

8、若為實(shí)周期對(duì)稱(chēng)序列，則其離散傅離葉變換也為實(shí)周期對(duì)稱(chēng)序列。若為純虛周期反對(duì)稱(chēng)序列，則其離散傅離葉變換也是純虛周期反對(duì)稱(chēng)序列

例：利用共軛對(duì)稱(chēng)性，用一個(gè)DFT計(jì)算兩個(gè)實(shí)序列的DFT，以減少計(jì)算量。四、循環(huán)卷積循環(huán)卷積是周期卷積截取主周期的結(jié)果，即是周期卷積在主周期的值。周期卷積循環(huán)卷積表示為循環(huán)卷積的DFT若則或即：證明：即循環(huán)卷積滿(mǎn)足交換律頻域循環(huán)卷積例：設(shè)兩個(gè)有限長(zhǎng)序列分別為計(jì)算兩序列N=6點(diǎn)的循環(huán)卷積。解：x1(n)x2(n)1axp2(-n)xp2(1-n)xp2(2-n)xp2(3-n)DFT的性質(zhì)序列DFT實(shí)序列DFT3-5用循環(huán)卷積計(jì)算序列的線(xiàn)性卷積一、用循環(huán)卷積計(jì)算線(xiàn)性卷積的條件

1、有限長(zhǎng)序列的線(xiàn)性卷積的取值范圍設(shè)有兩個(gè)有限長(zhǎng)序列、，其長(zhǎng)度分別為，他們的線(xiàn)性卷積為：由于、的取值范圍分別為：對(duì)于線(xiàn)性卷積中每個(gè)，相應(yīng)的、的取值范圍為對(duì)于后者，非零部分的m為即的取值范圍為2、有限長(zhǎng)序列的線(xiàn)性卷積與循環(huán)卷積的關(guān)系將、開(kāi)拓成以N為周期的周期序列他們的周期卷積為

即:和周期開(kāi)拓后的周期卷積等于他們的線(xiàn)性卷積的的周期開(kāi)拓。（1）當(dāng)N<N1+N2-1時(shí)，由圖可見(jiàn)，x3(n+qN)重疊。重疊區(qū)域在前(N1+N2-1)-N點(diǎn)。…012….N1+N2-2……N-1-N………截取其主周期不等于兩有限長(zhǎng)序列的循環(huán)卷積又所以

即：當(dāng)N<N1+N2-1時(shí)，不能用循環(huán)卷積計(jì)算線(xiàn)性卷積?；殳B（2）當(dāng)N≥N1+N2-1時(shí)，由圖可見(jiàn)，x3(n+qN)不重疊。…012….N1+N2-2……N-1-N………截取其主周期即得兩有限長(zhǎng)序列的循環(huán)卷積又所以

即：當(dāng)N≥N1+N2-1時(shí)，可以用循環(huán)卷積計(jì)算線(xiàn)性卷積。3、用FFT（DFT)來(lái)實(shí)現(xiàn)循環(huán)卷積（因此又叫快速卷積）若則或N點(diǎn)DFTN點(diǎn)DFTN點(diǎn)IDFT二、處理一個(gè)長(zhǎng)序列(長(zhǎng)為N)和一個(gè)短序列（長(zhǎng)為M）的快速卷積的方法（N>>M)----分段處理方法原因：

（1）DFT點(diǎn)數(shù)L≥N+M-1>>M，對(duì)于短序列也要計(jì)算如此長(zhǎng)的DFT，計(jì)算時(shí)間較長(zhǎng)，而且要存儲(chǔ)N點(diǎn)的DFT系數(shù)。（2）某些情況下序列的長(zhǎng)度不定。如對(duì)語(yǔ)音信號(hào)、地震信號(hào)的濾波，要求數(shù)據(jù)隨入隨出，而濾波器的長(zhǎng)度較短。分段處理的基本思想：可簡(jiǎn)單地把長(zhǎng)序列x(n)分成數(shù)段，每段長(zhǎng)N，而短序列h(n)長(zhǎng)為M，然后對(duì)每一段分別與h(n)作N點(diǎn)的快速卷積。再將所有段的結(jié)果合成即可。問(wèn)題：有混疊失真。對(duì)于每段，前M-1點(diǎn)失真。（如圖示）?；殳B部分(N+M-1)-N=M-1一、重疊保留法（重疊舍去法）

此法是將每段數(shù)據(jù)向前多取M-1點(diǎn)，然后作L=N+M-1點(diǎn)處理。前M-1點(diǎn)數(shù)據(jù)也混疊，要舍去；后N點(diǎn)數(shù)據(jù)無(wú)混疊，要保留。對(duì)于第一段，則要向前補(bǔ)M-1個(gè)零。（如圖）設(shè)每段為，則二、重疊相加法

此法是將每段數(shù)據(jù)直接作L≥N+M-1點(diǎn)的處理。然后將各段數(shù)據(jù)相加（如圖）設(shè)每段為，則或ML=r≤1032511~1964620~29128730~49256850~995129100~199102410200~299204811300~599409612600~9998192131000-199916384142000-39993276815分段卷積時(shí)的最佳卷積長(zhǎng)度L3-6利用DFT對(duì)連續(xù)時(shí)間信號(hào)的逼近1、混疊現(xiàn)象及離散譜分辨率

抽樣若對(duì)信號(hào)的抽樣不滿(mǎn)足抽樣定理，則有混疊抽樣x(n)的時(shí)間分辨率T

若對(duì)時(shí)間信號(hào)抽樣得，則x(n)的每一點(diǎn)代表時(shí)間上的寬度T(即抽樣間隔），或稱(chēng)為x(n)的時(shí)域分辨率為T(mén)。X(k)的頻率分辨率F

對(duì)信號(hào)x(n)的DFT的信號(hào)得的數(shù)字譜X(k)實(shí)際上是的抽樣。它的一個(gè)點(diǎn)也代表信號(hào)頻譜的一定寬度，稱(chēng)為頻率分辨率，它也是頻域上的抽樣間隔。2、時(shí)間分辨率T、頻率分辨率F、時(shí)間寬度Tw、頻率寬度B、DFT點(diǎn)數(shù)N的關(guān)系（1）對(duì)信號(hào)作N點(diǎn)DFT，則要取N點(diǎn)數(shù)據(jù)，時(shí)寬:Tw=N·T

（2）若DFT的頻率分辨率為F，則DFT后總的頻寬:B=N·F

（3）由抽樣定理，頻譜寬度與時(shí)域采樣周期的關(guān)系：B=1/T，或：T=1/B=1/(NF)或F=1/(NT)=1/Tw(也可由頻域得到，如下）可得：3、N一定時(shí)，頻域分辨率F與時(shí)間分辨率T的關(guān)系由上面分析可知：T=1/(NF)即因此：在N一定時(shí)，時(shí)域分辨率T與頻域分變率F是一個(gè)矛盾的量，兩者不能同時(shí)較小。（F小則T大，或：T小則F大）使兩者都較好（較小）的唯一辦法是增加N。

例：有一頻譜分析用的FFT處理器，其抽樣點(diǎn)數(shù)必須是2的整數(shù)冪，現(xiàn)對(duì)一信號(hào)分析，信號(hào)的最高頻率為：4kHz，要求頻率分辨率小于10Hz，確定:(1)最小紀(jì)錄長(zhǎng)度Tw;(2)最大時(shí)間分辨率（抽樣間隔）（3）最小紀(jì)錄點(diǎn)數(shù)解：(1)Tw=1/F≥1/10=0.1s(2)T=1/B≤1/(4000*2)=0.000125(3)N=Tw/T≥0.1/0.000125=800

按2的整數(shù)冪,取N=1024此時(shí)：若取N=1024,F=10Hz

則：Tw=0.1s,B=1024*10=10240Hz,T=1/B=1/10240≈0.0001s

若取N=1024,T=0.000125

則：Tw=NT=1024*0.000125=0.128s,F=1/Tw=7.8125Hz4、頻譜泄漏若信號(hào)x(t)的頻譜X(jΩ)有限寬→信號(hào)在時(shí)域x(t)無(wú)限寬實(shí)際：信號(hào)在時(shí)域x1(t)有限寬→頻譜X1(jΩ)無(wú)限寬此時(shí)：x1(t)=x(t)R(t)→泄漏的頻譜截?cái)啻?-7快速傅立葉變換(FFT)一、基2時(shí)域抽選FFT1、DFT的計(jì)算次數(shù)對(duì)每一個(gè)X(k)，有N次復(fù)數(shù)乘法，(N-1)次復(fù)數(shù)加法對(duì)所有N個(gè)X(k)，有N·N=次復(fù)數(shù)乘法，N(N-1)≈次復(fù)數(shù)加法對(duì)每一個(gè)X(k)，有4N次實(shí)數(shù)乘法，2(2N-1)次實(shí)數(shù)加法對(duì)所有N個(gè)X(k)，有N·4N=4次實(shí)數(shù)乘法，N(4N-2)≈4次實(shí)數(shù)加法2、減少計(jì)算量的可能途徑主要是利用的對(duì)稱(chēng)性和周期性（1）對(duì)稱(chēng)性減少一半乘法次數(shù)，加法次數(shù)不變（2）周期性利用以上特性,得到改進(jìn)DFT直接算法的方法

1.合并DFT運(yùn)算中的有些項(xiàng).2.將長(zhǎng)序列DFT利用對(duì)稱(chēng)性和周期性分解為短序列DFT.（因?yàn)椋篋FT的運(yùn)算量∝,N↓,則運(yùn)算量↓)二、基2時(shí)域抽選FFT算法（Tukey-Cooley算法）1、算法原理設(shè)序列長(zhǎng)為，若不滿(mǎn)足，則加0使之滿(mǎn)足。這種的FFT，稱(chēng)為基2FFT。將序列x(n)（n=0,1,2,…,N-1)按n的奇偶分解成兩組：則由于N/2次乘法運(yùn)算顯然N/2次乘法運(yùn)算N=8=時(shí)，N點(diǎn)DFT化為兩個(gè)N/2點(diǎn)DFTN/2點(diǎn)(4點(diǎn))DFTN/2點(diǎn)(4點(diǎn))DFT

若N/2=仍是偶數(shù)，則可將其再進(jìn)行奇偶分解，把N/2點(diǎn)DFT化為兩個(gè)N/4點(diǎn)的DFT。此時(shí)，N/2點(diǎn)DFT化為兩個(gè)N/4點(diǎn)DFTN/4點(diǎn)(2點(diǎn))DFTN/4點(diǎn)(2點(diǎn))DFTN/4點(diǎn)DFTN/4點(diǎn)DFTN/4點(diǎn)DFTN/4點(diǎn)DFT

若仍是偶數(shù)，則可將其再進(jìn)行奇偶分解，把N/4點(diǎn)DFT化為兩個(gè)N/8點(diǎn)的DFT。直到兩點(diǎn)DFT化為1點(diǎn)DFT

此時(shí)，1點(diǎn)DFT1點(diǎn)DFT8點(diǎn)基2時(shí)域抽選FFT的完整流圖2、計(jì)算次數(shù)N比值2422162566441281638489618.35122621444608321024104857610240102.42048410430422528186.2DFT與FFT的計(jì)算量的比較三、基2時(shí)域抽選FFT的蝶型運(yùn)算公式及其按點(diǎn)運(yùn)算程序

1、蝶型運(yùn)算公式23123002312300為了減少乘法次數(shù)，可如下處理-1同址運(yùn)算：輸入輸出用同一內(nèi)存單元的運(yùn)算對(duì)偶結(jié)點(diǎn)及對(duì)偶結(jié)點(diǎn)跨距分組間隔8點(diǎn)時(shí)域抽選輸入倒序輸出順序的FFT流圖-1-1-1-1-1-1-1-1-1-1-1-1設(shè)l為分組序號(hào)，則可將所有數(shù)據(jù)表示為也可用一個(gè)式子表示2、輸入數(shù)據(jù)的處理輸出數(shù)據(jù)：按順序排列；輸入數(shù)據(jù)：倒序排列