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

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

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

的DFT

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

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

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

↑。（2）許多信號(hào)本身可能含有全頻帶的頻率成分；（3）信號(hào)采集系統(tǒng)包括采樣頻率上限。采用抗混疊濾波器。可先使信號(hào)通過一個(gè)低通濾波器，濾除高于fmax/2的信號(hào)頻率成分，然后再進(jìn)行采樣。

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

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

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

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