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

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

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

的DFT

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

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

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

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

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

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

，則截斷信號時域截斷信號頻域離散傅里葉變換的泄漏問題(Leakage)余弦信號矩形窗函數(shù)頻域乘積時域余弦信號被矩形窗截斷形成的泄漏余弦信號被矩形窗截斷形成的泄漏周期延拓信號與真實(shí)信號不同——能量泄露誤差克服方法之一：信號整周期截斷對于連續(xù)周期函數(shù)，在符合采樣定理的條件下，保證窗函數(shù)b(t)的時段τ等于被截函數(shù)的周期T的整倍數(shù)，可以保證逆變換后準(zhǔn)確地恢復(fù)原波形，不產(chǎn)生泄漏。對于隨機(jī)振動信號（非周期函數(shù)），控制泄漏的方法是采用特定的窗函數(shù)，以達(dá)到控制旁瓣的效果。為了減少泄漏應(yīng)該盡量尋找頻域中接近(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)信號、偽隨機(jī)或周期隨機(jī)、窗長等于周期信號整周期時漢寧窗：純隨機(jī)平頂窗：周期或準(zhǔn)周期信號力窗或指數(shù)衰減窗：錘擊法測頻響函數(shù)時的力信號和脈沖響應(yīng)信號快速傅里葉變換(FFT)直接利用DFT進(jìn)行譜分析時，存在一個突出矛盾，即當(dāng)序列長度N較大時計(jì)算量大、計(jì)算時間長、數(shù)據(jù)占用內(nèi)存多，難以利用DFT進(jìn)行實(shí)時處理，其應(yīng)用受到很大的限制。1965年庫利(Cooley)和圖基(Tukey)提出了一種DFT的快速算法，這就是FFT。FFT算法使計(jì)算量大大降低，計(jì)算時間減少，特別是當(dāng)序列長度N較大時，效果更為顯著。FFT并不是一種新的變換形式，它只是DFT的一種快速算法。并且根據(jù)對序列分解與選取方法的不同而產(chǎn)生了FFT的多種算法。FFT在離散傅里葉反變換、線性卷積和線性相關(guān)等方面也有重要應(yīng)用。DFT表達(dá)式：通常記，則DFT簡化為上兩式可寫為矩陣形式DFT的計(jì)算量DFT的計(jì)算量有限長序列x(n)的DFT為：將DFT定義式展開成方程組寫為矩陣形式用向量表示用復(fù)數(shù)表示計(jì)算一個X(k)值需要N次復(fù)數(shù)乘法和(N-1)次復(fù)數(shù)加法，那么N個X(k)共需N2次復(fù)數(shù)乘法和N(N-1)次復(fù)數(shù)加法。每次復(fù)數(shù)乘法包括4次實(shí)數(shù)乘法和2次實(shí)數(shù)加法，每次復(fù)加法包括2次實(shí)數(shù)加法，因此計(jì)算N點(diǎn)的DFT共需要4N2次實(shí)數(shù)乘法和(2N2+2N(N-1))次實(shí)數(shù)加法，如N=2048時，計(jì)算量為419萬次。減少運(yùn)算量方法：長序列分為短序列：由于N點(diǎn)DFT的運(yùn)算量隨N2增長，因此，當(dāng)N較大時，減少運(yùn)算量的途徑之一就是將N點(diǎn)DFT分解為幾個較短的DFT進(jìn)行計(jì)算，則可大大減少其運(yùn)算量。的周期性和對稱性：周期性：對稱性：表示用N除nk之后的余數(shù)FFT算法就是不斷地將長序列的DFT分解為短序列的DFT，利用的對稱性和周期性，將一個大的DFT分解成一些逐次變小的DFT，來減少DFT運(yùn)算量的快速算法。分解過程遵循兩條規(guī)則：①對時間進(jìn)行偶奇分解——按時間抽取的FFT算法(Decimationintime)DIT-FFT算法②對頻率進(jìn)行前后分解——按頻率抽取的FFT算法(Decimationinfrequency)DIF-FFT算法按時間抽取的FFT算法要求DFT變換區(qū)間長度N=2M，M為自然數(shù)。序列x(n)的N點(diǎn)DFT為

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