離散傅里葉變換及其快速算法

離散傅里葉變換及其快速算法概述傅里葉變換實現(xiàn)了時域到頻域的轉換，在連續(xù)信號和離散信號處理技術領域有廣泛的應用。為利用計算機計算傅里葉變換,對信號與頻譜有如下要求：信號與頻譜應是離散的數(shù)據(jù)長度都是有限的本節(jié)介紹如何將傅里葉級數(shù)和傅里葉變換的分析方法應用于離散時間信號，它們是由傅里葉變換發(fā)展而來的一種變換方法。離散傅里葉變換(DFT)和快速傅里葉變換(FFT)在理論上解決了利用計算機進行傅里葉分析的問題。離散時間序列數(shù)字計算機只能處理有限長的數(shù)字信號。因此，必須把一個連續(xù)的變化的模擬信號轉換成有限長的離散時間序列，才能由計算機來處理。這一轉換稱模擬信號數(shù)字化。對x(t)進行抽樣，抽樣間隔為Δ，x(t)的離散值在時間t=rΔ，寫為xr。{xr},r=…,-1,0,1,2,3,…叫做離散時間序列。周期序列的離散分析連續(xù)周期函數(shù)x(t)，抽樣間隔Δt=T/N離散傅里葉級數(shù)(DFS)的性質離散傅里葉系數(shù)也是離散周期的，周期為N。傅里葉變換對小結傅里葉級數(shù)(FS)（時域：連續(xù)周期；頻域：非周期離散）傅里葉變換(FT)（時域：連續(xù)非周期；頻域：非周期連續(xù)）離散傅里葉級數(shù)(DFS)（時域：離散周期；頻域：周期離散）傅里葉變換對小結離散傅里葉變換(DFT)工作中經(jīng)常要對有限長序列進行頻譜分析,這就是我們這里要談到的離散傅里葉變換。對有限長數(shù)字序列進行分析處理，即必須對信號進行截斷。截取一段長為T的信號截斷的過程是，對實測連續(xù)信號

稱為樣本，稱為樣本長度，N為采樣點。離散傅里葉變換(DFT)的定義和基本概念設x(n)為有限長序列：正變換：逆變換：DFT與DFS的區(qū)別如何區(qū)分DFT與DFS這兩個變換對？在意義上有差別,在形式上相同。DFS描述的是周期離散序列xr與其頻譜ck的關系，它表明時域中的周期序列得到的頻譜也是周期離散的。它是嚴格按照傅里葉分析的概念得來的。由前面的分析已知，有限長序列是非周期性的，故其傅里葉變換應當是連續(xù)、周期性的頻譜。DFT是DFS的主值序列，只是一種借用形式，一種算法。注意：--------離散傅里葉變換關系中，有限長序列都作為周期序列的一個周期來表示，都隱含有周期性意義。DFSDFT非周期函數(shù)的離散傅里葉變換的物理邏輯過程(a)原函數(shù)，(b)截斷后保留部分，(c)周期拓廣，(d)離散采樣，(e)離散傅里葉變化后的離散譜DFT表達式：通常記，則DFT簡化為上兩式可寫為矩陣形式例：利用DFT的矩陣表達式求4點序列

的DFT

解：由N=4得x(n)和X(k)的波形圖如下所示采樣、采樣定理和混頻現(xiàn)象1、采樣

數(shù)字信號處理的第一步是對連續(xù)模擬信號的離散化(即采樣)。離散化本身一般會帶來頻率混疊誤差。其原理圖如下：數(shù)學描述為：理想抽樣就是以周期性沖激串來對連續(xù)時間信號進行抽樣。周期單位脈沖周期單位沖激序列：復指數(shù)形式FS：周期單位沖激序列的傅里葉變換積分限在-Ts/2和Ts/2之間：周期單位沖激序列的傅里葉變換：周期單位沖激序列的傅里葉變換周期單位沖激序列的傅里葉變換各點處的單位脈沖按等間隔排列所組成的序列

單位脈沖序列的傅式譜仍為脈沖序列，但其譜值為如上圖（b）。如上圖（a）。譜線間隔為其原理圖如下：數(shù)學描述為：理想抽樣就是以周期性沖激串來對連續(xù)時間信號進行抽樣。周期單位脈沖單位脈沖序列的傅式譜可寫成根據(jù)卷積定理，的傅式譜為（1）幅值發(fā)生了變化（fs倍）（2）周期延拓，周期為T=1/t=fs2、采樣定理和頻混現(xiàn)象則在離散信號譜這種現(xiàn)象稱為頻率混疊或頻混。如果原信號x(t)中包含的最高頻率成分中相應周期的譜會出現(xiàn)重疊，為混疊頻率或Nyquist頻率。即不產生頻率混淆現(xiàn)象的臨界條件。采樣定理又可稱為：如果分析信號中最高頻率成分不超過混疊頻率，則不出現(xiàn)頻率混疊。反之，如果頻率成分的兩倍，則采樣后離散信號頻譜中不會出現(xiàn)頻率混疊。這就是采樣定理。即采樣頻率大于等于分析信號中最高如何避免頻混消除混疊的方法有兩種:提高采樣頻率fs，即縮小采樣時間間隔。缺點:（1）采樣頻率高，內存占用量和計算量

↑。（2）許多信號本身可能含有全頻帶的頻率成分；（3）信號采集系統(tǒng)包括采樣頻率上限。采用抗混疊濾波器?？上仁剐盘柾ㄟ^一個低通濾波器，濾除高于fmax/2的信號頻率成分，然后再進行采樣。

實際上，由于信號頻率都不是嚴格有限的，而且，實際使用的濾波器也都不具有理想濾波器在截止頻率處的垂直截止特性，故不足以把稍高于截止頻率的頻率分量衰減掉。

所以實際處理時一般應使采樣頻率滿足抗混濾波(anti-aliasing)離散傅里葉變換的泄漏問題(Leakage)在實際應用中，通常將所觀測的信號限制在一定的時間間隔內，也就是說，在時域對信號進行截斷操作，或稱作加時間窗，亦即用時間窗函數(shù)乘以信號，即由卷積定理可知，時域相乘，頻域為卷積，則有有時會造成能量分散現(xiàn)象，稱之為頻譜泄漏。從數(shù)學意義上講，無限長連續(xù)信號的截斷相當于用一高度為1，寬度為T的矩形窗函數(shù)w(t)乘原信號x(t)

，則截斷信號時域截斷信號頻域離散傅里葉變換的泄漏問題(Leakage)余弦信號矩形窗函數(shù)頻域乘積時域余弦信號被矩形窗截斷形成的泄漏余弦信號被矩形窗截斷形成的泄漏周期延拓信號與真實信號不同——能量泄露誤差克服方法之一：信號整周期截斷對于連續(xù)周期函數(shù)，在符合采樣定理的條件下，保證窗函數(shù)b(t)的時段τ等于被截函數(shù)的周期T的整倍數(shù)，可以保證逆變換后準確地恢復原波形，不產生泄漏。對于隨機振動信號（非周期函數(shù)），控制泄漏的方法是采用特定的窗函數(shù)，以達到控制旁瓣的效果。為了減少泄漏應該盡量尋找頻域中接近(f)的窗函數(shù)W(f)，即主瓣窄旁瓣小的窗函數(shù)。

頻域中|f|<1/T的部分稱為W(f)的主瓣－主瓣窄，分辨率高其余兩旁的部分即附加頻率分量稱為旁瓣。－旁瓣低，減少泄露－1/T1/T2/T3/T－2/T常用窗函數(shù)(1)矩形窗(Rectangular) w(t)=1(2)漢寧窗(Hanning) w(t)=1-cos(2t/T),(3)凱塞窗(Kaiser-Bessel) w(t)=1-2.4cos(2t/T)+0.244cos(4t/T)-0.00305cos(6t/T)(4)平頂窗（FlatTop）

w(t)=1-1.93cos(2t/T)+1.29cos(4t/T)-0.388cos(6t/T)+0.0322cos(8t/T)窗函數(shù)用法矩形窗：瞬態(tài)信號、偽隨機或周期隨機、窗長等于周期信號整周期時漢寧窗：純隨機平頂窗：周期或準周期信號力窗或指數(shù)衰減窗：錘擊法測頻響函數(shù)時的力信號和脈沖響應信號快速傅里葉變換(FFT)直接利用DFT進行譜分析時，存在一個突出矛盾，即當序列長度N較大時計算量大、計算時間長、數(shù)據(jù)占用內存多，難以利用DFT進行實時處理，其應用受到很大的限制。1965年庫利(Cooley)和圖基(Tukey)提出了一種DFT的快速算法，這就是FFT。FFT算法使計算量大大降低，計算時間減少，特別是當序列長度N較大時，效果更為顯著。FFT并不是一種新的變換形式，它只是DFT的一種快速算法。并且根據(jù)對序列分解與選取方法的不同而產生了FFT的多種算法。FFT在離散傅里葉反變換、線性卷積和線性相關等方面也有重要應用。DFT表達式：通常記，則DFT簡化為上兩式可寫為矩陣形式DFT的計算量DFT的計算量有限長序列x(n)的DFT為：將DFT定義式展開成方程組寫為矩陣形式用向量表示用復數(shù)表示計算一個X(k)值需要N次復數(shù)乘法和(N-1)次復數(shù)加法，那么N個X(k)共需N2次復數(shù)乘法和N(N-1)次復數(shù)加法。每次復數(shù)乘法包括4次實數(shù)乘法和2次實數(shù)加法，每次復加法包括2次實數(shù)加法，因此計算N點的DFT共需要4N2次實數(shù)乘法和(2N2+2N(N-1))次實數(shù)加法，如N=2048時，計算量為419萬次。減少運算量方法：長序列分為短序列：由于N點DFT的運算量隨N2增長，因此，當N較大時，減少運算量的途徑之一就是將N點DFT分解為幾個較短的DFT進行計算，則可大大減少其運算量。的周期性和對稱性：周期性：對稱性：表示用N除nk之后的余數(shù)FFT算法就是不斷地將長序列的DFT分解為短序列的DFT，利用的對稱性和周期性，將一個大的DFT分解成一些逐次變小的DFT，來減少DFT運算量的快速算法。分解過程遵循兩條規(guī)則：①對時間進行偶奇分解——按時間抽取的FFT算法(Decimationintime)DIT-FFT算法②對頻率進行前后分解——按頻率抽取的FFT算法(Decimationinfrequency)DIF-FFT算法按時間抽取的FFT算法要求DFT變換區(qū)間長度N=2M，M為自然數(shù)。序列x(n)的N點DFT為

將上面的和式按n的奇偶性分解為按時間抽取的FFT算法如取N=23=8，即離散時間信號為按照規(guī)則①將序列x(n)分為奇偶兩組，一組序號為偶數(shù)，另一組序號為奇數(shù)，即分別表示為根據(jù)DFT的定義因為上式中的G(k)和H(k)都是N/2點的DFT注意到G(k)和H(k)只有N/2個點，而X(k)卻需要N個點，如果以G(k)和H(k)表示全部X(k)，應利用G(k)和H(k)的兩個重復周期，則有：由G(k)和H(k)的周期性和WN的對稱性可得：因此可由G(k)和H(k)決定X(k)的全部關系式：以N=8為例說明，此時有：按照上面結論可畫出信號流程圖如下：可進一步把每個N/2點DFT的計算再各分解成兩個N/4點DFT的計算：將所得的信號流程圖合并，便得到下面信號流程圖：因為N=8，所以上圖中N/4點的DFT就是