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

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

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

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

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

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

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

DFS(IDFS):周期序列→周期序列序列長度均無限長n,k:(-∞,∞)實際序列x(n)：有限長希望頻域數(shù)據(jù)：有限長對有限長數(shù)據(jù)x(n)的處理：將x(n)周期開拓，周期為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

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

利用矩形序列：則

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

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

§3-3Z變換的抽樣

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

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

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

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

x(n)

的DFT為

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

即：在頻率點的抽樣值為

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

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

一、線性

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

若，則用來代替。

三、對稱性

1、序列的對稱

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

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

于是

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非周期序列的共軛對稱與反對稱部分周期序列的共軛對稱與反對稱部分x(n)x*(N-n)Xpet(n)0N-1Xpot(n)N-12、用來表示和

由圖可見所以故同理因為所以3、的共軛序列的離散傅立葉變換

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

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

6、序列的實部和虛部的離散立葉變換

證明：

因為

所以

7、序列的周期共軛對稱分量與周期共軛反對稱分量的離散傅離葉變換

證明：

因為

所以

8、若為實周期對稱序列，則其離散傅離葉變換也為實周期對稱序列。若為純虛周期反對稱序列，則其離散傅離葉變換也是純虛周期反對稱序列

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

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

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

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

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

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

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

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

抽樣若對信號的抽樣不滿足抽樣定理，則有混疊抽樣x(n)的時間分辨率T

若對時間信號抽樣得，則x(n)的每一點代表時間上的寬度T(即抽樣間隔），或稱為x(n)的時域分辨率為T。X(k)的頻率分辨率F

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

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

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

例：有一頻譜分析用的FFT處理器，其抽樣點數(shù)必須是2的整數(shù)冪，現(xiàn)對一信號分析，信號的最高頻率為：4kHz，要求頻率分辨率小于10Hz，確定:(1)最小紀(jì)錄長度Tw;(2)最大時間分辨率（抽樣間隔）（3）最小紀(jì)錄點數(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此時：若取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、頻譜泄漏若信號x(t)的頻譜X(jΩ)有限寬→信號在時域x(t)無限寬實際：信號在時域x1(t)有限寬→頻譜X1(jΩ)無限寬此時：x1(t)=x(t)R(t)→泄漏的頻譜截斷窗3-7快速傅立葉變換(FFT)一、基2時域抽選FFT1、DFT的計算次數(shù)對每一個X(k)，有N次復(fù)數(shù)乘法，(N-1)次復(fù)數(shù)加法對所有N個X(k)，有N·N=次復(fù)數(shù)乘法，N(N-1)≈次復(fù)數(shù)加法對每一個X(k)，有4N次實數(shù)乘法，2(2N-1)次實數(shù)加法對所有N個X(k)，有N·4N=4次實數(shù)乘法，N(4N-2)≈4次實數(shù)加法2、減少計算量的可能途徑主要是利用的對稱性和周期性（1）對稱性減少一半乘法次數(shù)，加法次數(shù)不變（2）周期性利用以上特性,得到改進(jìn)DFT直接算法的方法

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

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

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

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

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