1、1,離散傅里葉變換，是對有限長序列傅里葉變換的 有限點(diǎn)離散采樣，開辟了頻域離散化的道路，使數(shù) 字信號處理可以在頻域采用數(shù)字運(yùn)算的方法進(jìn)行。,第四章 離散傅里葉變換(DFT),的快速算法,使信號的實(shí)時處理和設(shè)備的簡化得以實(shí)現(xiàn)。,DFT在各種信號的處理中起著核心作用。 本章主要內(nèi)容：DFT的定義，物理意義。 DFT的基本性質(zhì)。頻域采樣和DFT的應(yīng)用例子。,(無限長序列，有限長序列)。,4.1 引言,2,4.2 離散傅里葉變換的定義 4.2.1 DFT的定義 第2章中DFS變換對,令,，對于一個長度為M的有限長序列，定義,的N點(diǎn)離散傅里葉變換對為：,N稱為DFT變換區(qū)間長度,3,證明：,由于,因而,

2、由此可見，離散傅里葉逆變換定義是惟一的。,4,例：,求：,解：變換區(qū)間N=8則,變換區(qū)間N=16則,由此可見，x(n)的離散傅里葉變換結(jié)果與變換區(qū)間長度N的區(qū)值有關(guān)。,的8點(diǎn)和16 點(diǎn)DFT。,5,4.2.2 DFT和Z變換的關(guān)系,比較以上等式可得：,或,6,例：上例結(jié)果,上式表明序列,的N點(diǎn)DFT是x(n)的z變換單位圓上的N點(diǎn)等間隔采樣?；蛘?是X（K）為x(n)傅里葉變換,上的N點(diǎn)等間隔乘樣。,這就是DFT的物理意義,7,8,4.2.3 DFT的隱含周期性與DFS的關(guān)系 ,由于,9, 將x(n)以N為周期，進(jìn)行周期延拓，成為周期序列,。則,.,隱含著周期性。,10,上進(jìn)行N點(diǎn)等間距采樣。

3、當(dāng)自變量K超出DFT變換區(qū)間時，必然得到,以外區(qū)間上,的采樣，且以N為周期重復(fù)出現(xiàn)，得到,例：比較,11,4.3離散傅里葉變換的基本性質(zhì)及定理 4.3.1 線性性質(zhì),令,12,由于,4.3.2 隱含周期性,設(shè)：,13,4.3.3 循環(huán)移位性質(zhì),表示將：,序列按周期N延拓成周期序列，左移M位，再取,區(qū)間主值區(qū)。即為序列的循環(huán)移位。,1. 序列的循環(huán)移位,14,循環(huán)移位過程示意圖N=5,15,2時域循環(huán)移位定理,為長度為N的有限序列。,則,可以用定義證明。,設(shè),為 的循環(huán)移位，即,證明：,16,3. 頻域循環(huán)移位定位 如果,令 ，則有,17,1. 復(fù)共軛序列的DFT 設(shè),則,且,4.3.4 DFT

4、的共軛對稱性,18,證明：,由,的隱含周期性，有,同理可得：,19,2. DFT的共軛對稱性 FT的對稱性是指關(guān)于坐標(biāo)原點(diǎn)的縱坐標(biāo)的對稱性, DFT的對稱性是指關(guān)于N/2點(diǎn)的對稱性。,1) 有限長共軛對稱序列和共軛反對稱序列,：有限長共軛對稱序列，,：有限長共軛反對稱序列，,即：,20,當(dāng)N為偶數(shù)時，將上式中的n換成,，可得到：,21,任何有限長序列,都可以表示成其共軛對稱分量和共軛反對對稱分量之和。,22,2) DFT的共軛對稱性,其中,23,24, 有限長實(shí)序列DFT的共軛對稱性。, 如果, 如果,25,實(shí)際中對實(shí)序列進(jìn)行DFT。利用上述對稱性質(zhì)，可減少DFT運(yùn)算量。 計算實(shí)序列的N點(diǎn)DF

5、T時：,應(yīng)用方法：,利用DFT的共軛對稱性，通過計算一個N點(diǎn)DFT，可以得到兩個 不同實(shí)序列的N點(diǎn)DFT。,26,為兩個實(shí)序列構(gòu)成新序列,如下：,對,進(jìn)行DFT，得到：,由公式求得：,所以,設(shè),27,有限長序列,長度分別為,如果,則,4.3.5 循環(huán)卷積定理,設(shè) N=8,28,設(shè) N=8的時域循環(huán)卷積,29,稱為（時域）循環(huán)卷積（可以用定義證明） 。,不同。,30,證明：,同樣可證明頻域循環(huán)卷積定理。,31,如果：,則：,式中,頻域循環(huán)卷積定理,32,4.3.6 頻率域采樣,設(shè)任意序列,的Z變換為,在單位圓上對,等間隔采樣N點(diǎn)得到：,也表示在區(qū)間,上，對,的傅里葉變換,的N點(diǎn)等間隔采樣。,時域

6、采樣,頻域采樣？,33,將,看作長度為N的有限長度序列,，即,關(guān)系,頻域采樣定理,34,將,代入上式,，得,式中，,35,所以,以上說明：,在單位圓上的N點(diǎn)等間隔采樣,的IDFT，為原序列,以N為周期的周期延拓序列,的主值序列。,36,如果序列,的長度為M，則只有頻域采樣點(diǎn)數(shù),才有：,即可由頻域采樣恢復(fù)原序列，否則產(chǎn)生時域混疊現(xiàn)象。 這就是所謂的頻域采樣定理。,長度為M，在頻域,之間等間隔采樣N點(diǎn),則有,式中：,時，,用頻域采樣表示Z變換：,37,將上式代入Z變換表示式中：,令,稱為內(nèi)插函數(shù),則,稱用,的內(nèi)插函數(shù)和內(nèi)插公式,38,的內(nèi)插函數(shù)公式,即得：,時，,的傅里葉變換,的內(nèi)插函數(shù)公式，,當(dāng)

7、：,39,進(jìn)一步化簡，可得,頻域采樣理論及有關(guān)公式可提供一種有可用的濾波器結(jié)構(gòu) 和濾波器設(shè)計途徑。,40,FFT 使DFT在數(shù)字通信、語音信號處理數(shù)值分析等 各個領(lǐng)域得到廣泛應(yīng)用。 DFT計算卷積和相關(guān)系數(shù)的基本原理； DFT對連續(xù)信號和序列進(jìn)行譜分析等最基本的應(yīng)用。,4.4 DFT的應(yīng)用舉例,4.4.1用DFT計算線性卷積.,設(shè),41,計算框圖：,在實(shí)際應(yīng)用中，為了分析時域離散線性非移變系統(tǒng)或者對序列 進(jìn)行濾波處理，都需要計算兩個序列的線性卷積。,都是有限長序列分別是N和M。,其中,線性卷積：,循環(huán)卷積：,設(shè),42,其中,43,說明：,以L為周期的周期延拓序列的主值序列。,長度為,，因此只有

8、當(dāng)循環(huán)卷積長度,以L為周期進(jìn)行周期延拓才無混疊,線性卷積,現(xiàn)象。,此時取主值序列顯然滿足：,44,計算線性卷積的算法：,為有限長序列。其長度分別為N和M，計算L長度的循環(huán)卷積,當(dāng),時，其循環(huán)卷積就等于線性卷積，即,對于,用DFT(FFT)計算線性卷積框圖如下：,點(diǎn)全部補(bǔ)上零。,設(shè),45,例：已知,如圖所示，用循環(huán)卷積法求線性卷積。,5,1,46,1,1,47,如果兩個序列長度相等相差很大，MN時，短序列 需補(bǔ)很多零。需要占用存貯容量大。處理時間延時很大， 很難實(shí)時處理，如對語言信號和地震信號的實(shí)時處理，就 成問題了。解決方法是利用分段處理法。 分段處理是將長序列均勻分段，然后逐段處理，有重 疊

9、相加法和重疊保留法兩種。下面主要介紹重疊相加法。,48,重疊相加法：,為無限長序列。將,均勻分段，每段長M。,式中,于是,設(shè)：,則：,49,上式中：,序列長度,序列長度,將重疊的部分進(jìn)行相加。如圖所示。,50,51,52,用DFT對連續(xù)信號進(jìn)行譜分析。,信號的譜分析：就是計算信號的傅里葉變換。DFT是一種時域 和頻域均離散化的變換，適合數(shù)值運(yùn)算，是分析離散信號和系 統(tǒng)的有利工具。 對連續(xù)信號和系統(tǒng)，可以通過時域采樣，應(yīng)用DFT進(jìn)行近似譜分析。,是,在頻率區(qū)間,上的N點(diǎn)等間隔采樣。,4.4.2 用DFT對信號進(jìn)行譜分析,都為有限長序列。,由FT理論可知： 信號持續(xù)時間有限長，則其頻譜無限寬。 若

10、信號的頻譜有限寬，則其持續(xù)時間無限長。,連續(xù)信號,53,處理方法： 對頻譜很寬的信號，為了防止時域采樣后產(chǎn)生頻譜混迭失真， 可用預(yù)濾波器濾除幅度較小的高頻成分。fs 2fc,對于持續(xù)時間很長的信號，采樣點(diǎn)數(shù)太多以致無法存貯和計算， 只好截取有限點(diǎn)進(jìn)行DFT。去掉幅度很小的部分時間信號。 上述可見，用DFT對連續(xù)信號進(jìn)行譜分析必然是近似的，其近 似程度與信號帶寬，采樣頻率和截取長度有關(guān)。工程角度看，濾除 幅度很小的高頻成分和截去幅度很小的部分時間信號是允許的。,54,設(shè) ：連續(xù)信號,持續(xù)時間為,，最高頻率為,FT：,對,以采樣間隔,采樣得,共采樣N點(diǎn)，對,作零階近似,，得,的連續(xù)周期函數(shù)，周期為

11、采樣頻率,55,對,在區(qū)間,上等間隔采樣N點(diǎn)，采樣間隔為F，,將,令,56,同樣可以由,推導(dǎo)出,57,58,直接由分析結(jié)果,N個點(diǎn)離散采樣點(diǎn)的譜特性。這就是所謂的柵欄效應(yīng)。,要進(jìn)行截斷處理，還會產(chǎn)生頻混和泄漏現(xiàn)象。,的全部頻譜特性，而只能看到,如果，對,由課本上理想低通濾波器的單位沖激響應(yīng)及頻響函數(shù)可知，如 對信號進(jìn)行截斷處理，會發(fā)現(xiàn)，低頻部分近似理想低通頻響特 性，而高頻部分誤差較大，且整個頻響都有波動。這些差別都 是截斷所產(chǎn)生的。為了減少這種截斷誤差，可適當(dāng)增長TP，增 加采樣點(diǎn)數(shù)N，然后再進(jìn)行DFT。 對連續(xù)信號進(jìn)行譜分析，主要關(guān)心兩個問題：譜分析范圍和頻率分辨率，分別與fs和F有關(guān)。,

12、59,增加譜分析范圍，提高采樣頻率,頻率分辨率：,譜分析范圍：,當(dāng)fs提高了，F(xiàn)變小，即頻率分辨率變低； 如保持fs不變，增加采樣點(diǎn)數(shù)N，F(xiàn)變小，即提高頻率分辨率。,只有增加對信號的觀察時間TP，才能增加N。,60,例：對實(shí)信號進(jìn)行譜分析，要求,，,求,如果,不變要求譜分辨率增加一倍，求,解 ,在應(yīng)用中，,甚至,可得到更好的頻譜分辨率。,61,2.用DFT對序列進(jìn)行譜分析,的N點(diǎn)等間隔采樣。對序列,由此序列的FT 可利用DFT(即FFT)來分析計算。,由于DFT的隱含周期為N,式中：,因而可用 的頻譜結(jié)構(gòu)。,62,。,(1)如果截取長度M等于 的整個周期，即M=mN，m為正數(shù)，則,詳情見p90

13、,63,設(shè)：,，,，,也能表示 的頻譜結(jié)構(gòu)。,64,（2）如果 的周期預(yù)先不知道。,將截取長度擴(kuò)大1倍截取，得,比較,，如果二者的主譜差別滿足分析誤差要求，則,近似表示,進(jìn)行DFT分析，直到主頻譜差別達(dá)到要求為止。,的頻譜。否則，連續(xù)擴(kuò)大截取長度，,可先截取M點(diǎn)進(jìn)行DFT，即,65,（3）在很多實(shí)應(yīng)用中，并非整個單位圓上的頻譜都很有定義。,例如，對于寬帶信號往往只希望對信號所在的一段頻帶進(jìn)分析，這時便 希望采樣距離密集地在這段頻帶內(nèi)進(jìn)行，而帶外部分可完全不予考慮。 另外，有時希望采樣點(diǎn)不局限于單位圓上。 例如，語言信號處理中，常常需要知道系統(tǒng)極點(diǎn)所對應(yīng)的頻率，如果極 點(diǎn)位置離單位圓較遠(yuǎn)，則其單

14、位圓上的頻譜很平滑，這時很難從中識別出 極點(diǎn)對應(yīng)的頻率。如果使采樣點(diǎn)軌跡沿一條接近這些極點(diǎn)的弧線或圓周進(jìn) 行，則采樣結(jié)果將會在極點(diǎn)對應(yīng)的頻率上出現(xiàn)明顯的尖峰，這樣就能準(zhǔn)確 地測定出極點(diǎn)頻率。,可得N點(diǎn)頻率樣點(diǎn)。,在同心圓周上采樣N點(diǎn)，,66, 在螺旋弧線線上采樣，稱為線性調(diào)頻Z變換,前一種方法：計算序列,在半徑為,的圓上的頻譜,令,則,這種方法的計算量大。下面主要介紹CZT。,變換，,簡稱（CZT）。,67,3.,設(shè)序列,長度為N，要分析Z平面上M點(diǎn)頻譜采樣值，分析點(diǎn)為,式中A和W為復(fù)數(shù)，用極坐標(biāo)形式表示為,式中，,為實(shí)數(shù)，當(dāng)K=0時，有,A決定譜分析起點(diǎn)始點(diǎn),的位置，,的值決定分析路徑的盤旋

15、趨勢，,則表示兩個相鄰分析點(diǎn)之間的夾角。,，,68,如果 ，隨著K增大，分析點(diǎn) 以 為步長向外盤旋；,如下圖所示：,將,代入Z變換公式得到,如果 ，隨著K增大，分析點(diǎn) 以 為步長向內(nèi)盤旋；,69,可以想象成其頻率隨時間線性增加的復(fù)指數(shù)序列，在雷達(dá),令,則,當(dāng),系統(tǒng)中，這樣的信號稱作線性調(diào)頻信號，用,故稱上述變換為線性調(diào)頻Z變換，簡稱,。,表示,70,用DFT（FFT）計算,變換的原理和實(shí)現(xiàn)步驟。,無限長序列,譜分析點(diǎn)數(shù)為M，只要 區(qū)間上的卷積結(jié)果。,因此 ，只要計算出 區(qū)間上的M個值就可以了。,無限長序列,原理：,71,取主值序列形成,用循環(huán)卷積計算線性卷積,要截取區(qū)間 上的 值，長度為(N+

16、M-1)。,y(n)的長度為N。V（n）長度為2N+M-2,（,而,在0,M-1區(qū)間上沒有混疊。,以L為周期進(jìn)行周期拓展，,的尾部要補(bǔ) 個零，可用循環(huán)卷積計算線性卷積。,72,（1）形成,序列,（2）,（3）,（4）,（5）計算,（7）,步驟：,（6）,73,總之， 變換用作譜分析時，具有靈活、適應(yīng)性強(qiáng) 和運(yùn)算效率高等優(yōu)點(diǎn)。,（4）當(dāng) 時， 均勻分布在單位圓上， 此時 變換就是序列的DFT。因此可說，DFT是 變換的特例。,（2）分析頻率點(diǎn) 的起始點(diǎn) 及相鄰兩點(diǎn)的夾角 是任意的（即頻率分辨率是任意的），因此可從任意頻率上開始，對輸入數(shù)據(jù)進(jìn)行窄帶高分辯率的譜分析。,與標(biāo)準(zhǔn) DFT（FFT）算法相

17、比較，,（1）輸入序列長度N和輸出序列長度不需要相等。且二者均可為素數(shù)。,（3）譜分析路徑可以是螺旋形的。,變換有以下特點(diǎn)：,74,誤差造成：對連續(xù)信號采樣和截斷； 對非時限數(shù)據(jù)序列的截斷。,采取措施，預(yù)濾波，,4有DFT進(jìn)行譜分析的誤差問題,（1）混疊現(xiàn)象：,以下分別對可能產(chǎn)生誤差的三種現(xiàn)象進(jìn)行討論：,75,N點(diǎn)DFT是在頻率區(qū)間0，2上對信號的頻譜進(jìn)行N點(diǎn)等間隔采樣， 好象從N個柵欄縫隙中觀看信號的頻譜情況，稱為柵欄效應(yīng)。 有可能漏掉（擋住）大的頻譜分量。,采取措施：增加頻率采樣點(diǎn)數(shù)和采樣位置。對模擬信號提高采樣頻率，增加采樣點(diǎn)數(shù)。,（2）柵欄效應(yīng)：,76,對x(n)無限長序列的截斷，才能用DFT對其進(jìn)行譜分析。,（3）截斷效應(yīng)：