1、第九章 離散傅里葉變換,前言：引入DFT的原因,計算機應(yīng)用于信號處理的基本條件： 1. 連續(xù)函數(shù)轉(zhuǎn)變?yōu)殡x散數(shù)據(jù)(時域與頻域)； 2. 計算范圍從無限寬收縮到一個有限區(qū)間。 離散傅里葉變換研究內(nèi)容： 1. 如何在頻域進行離散化？ 2. 時域上的樣本與頻域上的樣本之間的數(shù)學(xué)關(guān)系是怎樣的？,主要內(nèi)容,離散傅里葉級數(shù)（DFS） 離散傅里葉變換（DFT） 快速傅里葉變換（FFT）,一.DFT是重要的變換 1.分析有限長序列的有用工具。 2.在信號處理的理論上有重要意義。 3.在運算方法上起核心作用，譜分析、 卷積、相關(guān)都可以通DFT在計算機上 實現(xiàn)。, 9-1引 言,二.DFT是現(xiàn)代信號處理橋梁 DFT

2、要解決兩個問題： 一是離散與量化， 二是快速運算。,信號處理,DFT(FFT),傅氏變換,離散量化,FT 傅立葉變換,時域：連續(xù)、非周期，頻域：非周期、連續(xù),9.2 傅里葉變換的幾種可能形式,FS 傅立葉級數(shù),時域：連續(xù)、周期，頻域：非周期、離散,1,1,1,1,1,1,1,1,1,1,DTFT,時域：離散、非周期 頻域：周期、連續(xù),時域 頻域,連續(xù)非周期 非周期連續(xù) 傅里葉變換,連續(xù)周期 非周期離散 傅里葉級數(shù),離散非周期 周期連續(xù) 序列的傅里葉變換,離散周期 周期離散 離散傅里葉級數(shù),傅里葉變換形式,傅里葉變換的4種形式,但是，前三種傅里葉變換對都不適于計算機上運算，因為它們至少在一個域（

3、時域或頻域）中函數(shù)是連續(xù)的。 因此，我們感興趣的是時域和頻域都是離散的情況。,時域：離散、周期，頻域：周期、離散,9.3 DFS與DFT,連續(xù)周期信號: 抽樣（抽樣周期為T，一個周期 內(nèi)抽樣N個點）,得周期序列,一、離散傅里葉級數(shù),是周期為N的周期序列,1、DFS的引入,將 兩端乘 再從 n=0到N-1求和，,則：,2、 的求取,3、將定標(biāo)因子1/N移到 表達(dá)式中。,保持與Z變換相同的形式？,設(shè) 則離散傅氏級數(shù)表示為：,正變換：,反變換：,4、離散傅氏級數(shù)的表示：,DFS的圖示說明,5、 函數(shù)的幾個性質(zhì)：,1.共軛對稱性：,2.周期性：,i為整數(shù),3.可約性：,4.正交性：,i為整數(shù),二、 離

4、散傅里葉變換,在進行DFS分析時，時域、頻域序列都是無限長的周期序列 周期序列實際上只有有限個序列值有意義 長度為N的有限長序列可以看成周期為N的周期序列的一個周期（主值序列） 借助DFS變換對，取時域、頻域的主值序列可以得到一個新的變換DFT，即有限長序列的離散傅里葉變換,另一種表示,其中 表示對 n 取模N 運算(或模 N的余數(shù))。,則,若,1、周期序列與主值序列的關(guān)系,舉例：設(shè)周期為 N=6。則有周期序列和求余運算： 這是因為： (19=36+1) 同理 這是因為： (-2=-16+4),同樣：X(k)也是一個N點的有限長序列,2、DFT的定義,3、DFT的矩陣形式,其中：,4、離散傅里

5、葉變換(DFT)的特點,序列x(n)在時域是有限長的(長度為N)，它的離散傅里葉變換X(k)也是離散、有限長的(長度也為N)。 n為時域變量，k為頻域變量。 離散傅里葉變換與離散傅里葉級數(shù)沒有本質(zhì)區(qū)別，DFT實際上是離散傅里葉級數(shù)的主值，DFT也隱含有周期性。 離散傅里葉變換(DFT)具有唯一性。,例1、計算 (N=12)的N點DFT. 解：,9.4 離散傅里葉變換的性質(zhì),1、線性,這里，序列長度及DFT點數(shù)均為N 若不等，分別為N1，N2，則需補零使兩序列長度相等，均為N，且,若,則,有限長序列的圓周移位導(dǎo)致頻譜線性相移，而對頻譜幅度無影響。,(1)圓周移位,2、時移特性,(2)時移特性,從

6、圖中兩虛線之間的主值序列的移位情況可以看出： 當(dāng)主值序列左移m個樣本時，從右邊會同時移進m個樣本 好像是剛向左邊移出的那些樣本又從右邊循環(huán)移了進來 因此取名“循環(huán)移位”。 顯然，循環(huán)移位不同于線性移位,3、頻移特性,時域序列的調(diào)制等效于頻域的圓周移位,eg：,4、時域圓周卷積,設(shè),則,(1)定理,圓周卷積步驟： 1）翻褶 2）圓周移位 3）相乘 4）相加,(2) 圓周卷積的計算,0,m,0,m,0,m,0,m,最后結(jié)果：,1）.線性卷積 的長度為 的長度為,2）圓周卷積,（3）線性卷積與圓周卷積的關(guān)系,3) 關(guān)系,補0 加長,x(n)的N點DFT是 x(n)的z變換在單位圓上的N點等間隔抽樣；

7、 x(n)的DTFT在區(qū)間0,2上的N點等間隔抽樣。,一.DFT的計算工作量 兩者的差別僅在指數(shù)的符號和因子1/N.,9-6 FFT的應(yīng)用,DFT與IDFT運算特點,當(dāng)N很大時,運算量將是驚人的,如N=1024, 要完成1048576 次(一百多萬次)運算.這樣, 難以做到實時處理.,二.改進的途徑,1. 的對稱性和周期性,對稱性:,周期性:,2、N點DFT 2個N/2點DFT,利用上述特性,可以將有些項合并,并 將DFT分解為短序列,從而降低運算次數(shù),提 高運算速度.1965年,庫利(cooley)和圖基 (Tukey)首先提出FFT算法.對于N點DFT,僅需 (N/2)log2N 次復(fù)數(shù)乘

8、法運算.例如N=1024=210 時， 需要(1024/2)log2 210 =512*10=5120次。 5120/1048576=4.88% ,速度提高20倍,三、基2FFT算法的思路,把一個序列分為長度減半的偶序列和奇序列, 原序列的DFT就由這兩個N/2序列求得. 進一步把N/2序列分解成兩個N/4序列, 一直分解到2點序列.,Eg. N=8的FFT,四.算法原理(基2FFT) 1.先將 按n的奇偶分為兩組N/2點作DFT,設(shè)N=2M ,不足時,可補些零。 n為偶數(shù)時: n為奇數(shù)時:,因此,其中, 2.兩點結(jié)論: (1) G(k),H (k)均為N/2點的DFT。 (2) X(k)=G

9、(k)+W H (k)只能確定出 X(k)的k= 0,1,(N/2-1)時的值； 即前N/2點的結(jié)果。,k,N,同理,3.X(k)后N/2個點的確定,*X(k)的后N/2個點，也完全由G(k), H(k)確定 *N點的DFT可由兩個N/2點的DFT來計算。,實現(xiàn)上式運算的流圖稱作蝶形運算,k= 0,1,(N/2-1),4.蝶形運算,（N/2個蝶形),由X1(k)、X 2(k)表示X(k)的運算是一種特殊的運算-碟形運算,k= 0,1,(N/2-1),例 N=8 時的FFT:,1、 2個N/2點DFT,（1）將 分成奇偶序列，并計算X(k),其中,g(0)=x(0) g(1)=x(2) N/2點

10、 g(2)=x(4) DFT g(3)=x(6) h(0)=x(1) h(1)=x(3) N/2點 h(2)=x(5) DFT h(3)=x(7),1 2,G(0),G(1),G(2),G(3),H(0),H(1),H(2),H(3),W,N,2,W,N,1,W,N,0,W,N,3,-1,-1,-1,-1,X(0),X(1),X(2),X(3),X(4),X(5),X(6),X(7),（2）對X (k)和X (k)進行蝶形運算如下圖所示:,2、 4個N/4點DFT,（1）將 分成奇偶序列，并進行DFT,其中,（2）將 分成奇偶序列,并進行DFT,W,N,0,W,N,0,W,N,0,W,0,N,

11、-1,-1,-1,-1,-1,-1,-1,-1,N,0,N,1,N,2,N,3,-1,-1,-1,-1,X(0),X(1),X(2),X(3),X(4),X(5),X(6),X(7),8點DFT的FFT的運算流圖如下,1.蝶形運算 蝶形單元 蝶距:2m-1 （第m級蝶形運算）,五. FFT算法的特點,輸入數(shù)據(jù)、中間運算結(jié)果和最后輸出均用同一存儲器。,2.原位運算,W,N,0,W,N,0,W,N,0,W,0,N,-1,-1,-1,-1,-1,-1,-1,-1,N,0,N,1,N,2,N,3,-1,-1,-1,-1,X(0),X(1),X(2),X(3),X(4),X(5),X(6),X(7),3

12、 倒位序運算 FFT運算流程中，輸出X(k)按正常順序排 列在存儲單元,而輸入是按順序: 這種順序稱作倒位序,即二進制數(shù) 倒位。,是由奇偶分組造成的,以N=8為例說明如下:,倒位序的實現(xiàn) 輸入序列先按自然順序存入存儲單元,然后經(jīng)變址運算來實現(xiàn)倒位序排列。 設(shè)輸入序列的序號為n,二進制為 (n2 n1 n0 )2 ,倒位序順序用 表示,其倒位序 二進制為(n0 n1 n2 )2 。,0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 4 2 0 1 0 0 1 0 2 3 0 1 1 1 1 0 6 4 1 0 0 0 0 1 1 5 1 0 1 1 0 1 5 6 1 1 0 0 1

13、1 3 7 1 1 1 1 1 1 7,自然順序n 二進制n n n 倒位序二進制n n n 倒位順序n,2 1 0 0 1 2,碼位倒序（N=8）,碼位倒序（N=16）,倒位序的變址處理方法,存儲單元,自然順序,變址,倒位序,蝶距為1,蝶距為2,W,N,0,W,N,0,W,N,0,W,0,N,-1,-1,-1,-1,-1,-1,-1,-1,N,0,N,1,N,2,N,3,-1,-1,-1,-1,X(0),X(1),X(2),X(3),X(4),X(5),X(6),X(7),4.WNr 的分布規(guī)律 第1級： 第2級： 第i級: 第L級:,5.存儲單元 存輸入序列 (n),n=0,1, ,N-1

14、, 計N 個單元; 存放系數(shù) , r=0,1, ,N/2-1, 需N/2個存儲單元； 共計(N+N/2)個存儲單元。,三、FFT運算量,1 N=2 時，共有L=log N級蝶形運算；每一級有N/2個蝶形單元。 2每一級有N個輸入中間數(shù)據(jù)，且每級只用到本級的輸入中間數(shù)據(jù)，適合于迭代運算。 3計算量： 每級N/2次復(fù)乘法，N次復(fù)加。（每蝶形只乘一次，加減各一次）。共有L*N/2=N/2log2N 次復(fù)乘法；復(fù)加法L*N=Nlog2N 次。與直接DFT定義式運算量相比(倍數(shù)) N2/(Nlog2N) 。當(dāng) N大時，此倍數(shù)很大。,2,L,9-7 DFT的應(yīng)用,一、利用FFT計算線卷積,1、時域圓周卷積

15、定理,設(shè),則,2、圓周卷積與線卷積的關(guān)系,補0 加長,3、方法,N點FFT,N點FFT,IFFT,x,x(n),h(n),y(n),M,L,連續(xù)時間 非周期信號,1、時域的離散化與有限化,二、利用DFT逼近連續(xù)時間信號的頻譜,2、頻域的有限化與離散化,3、誤差分析 1）.混疊現(xiàn)象 為避免混疊,由抽樣定理可知，須滿足 其中, 為抽樣頻率; 為信號的最高頻率分量； 或者 其中,T為抽樣間隔。,2）.頻譜泄漏（截斷誤差） 在實際應(yīng)用中，通常將所觀測的信號 限制在一定的時間間隔內(nèi),也 就是說， 在時域?qū)π盘栠M行截斷操作,或稱作：加時 間窗,亦即用時間窗函數(shù)乘以信號,由卷積定 理可知，時域相乘,頻域為卷積,這就造成拖 尾現(xiàn)象,稱之為頻譜泄漏.,0,n,0,n,n,3）.柵欄效應(yīng) 用DFT計算頻譜時，只是知道為頻率 的整數(shù)倍處的頻譜。在兩個譜線之間 的情況就不知道,這相當(dāng)通過一個柵欄觀察 景象一樣，故稱作柵欄效應(yīng)。 補零點加大周期 ，可使 變小來提高分辨力，以減少柵欄效應(yīng)。,頻譜分辨力,4.用DFT逼近連續(xù)時間信號