FFT快速傅里葉變換是數(shù)字信號(hào)處理的經(jīng)典算法,學(xué)過DSP或者芯片設(shè)計(jì)的人大多知道這個(gè)算法;但是,大家是否想過,為什么數(shù)字信號(hào)處理會(huì)有那么多FFT呢有人會(huì)說(shuō),為了分析信號(hào)的頻譜;那么下邊的問題就是,分析頻譜對(duì)我們的日常需求,比如手機(jī)打電話,雷達(dá)測(cè)量速度和方向等等一些與實(shí)際需求有什么聯(lián)系為什么FFT如此重要本文舉一些簡(jiǎn)明的例子,闡釋一下FFT到底有什么用;

先回憶一下FFT是什么;上世紀(jì)70年代之前,我們主要通過模擬電路來(lái)進(jìn)行信號(hào)處理,比如大家熟悉的用二極管和電容進(jìn)行AM調(diào)制信號(hào)的包絡(luò)檢波一樣,隨著數(shù)字系統(tǒng)的普及,我們可以用處理器或者數(shù)字電路更為精確的處理信號(hào),比如我們做AM檢波,實(shí)際上可以用載波把信號(hào)混頻與余弦函數(shù)做乘法,再進(jìn)行低通濾波,那么這個(gè)過程可以用數(shù)字電路的乘法器和FIR濾波器來(lái)做,FIR比二極管和電容構(gòu)成的低通濾波器階數(shù)高的多,性能自然更為理想,同時(shí),由于數(shù)字電路易于做成集成電路,因此我們更多地是將原先的模擬信號(hào)比如麥克風(fēng)的音頻通過模擬-數(shù)字轉(zhuǎn)換器,轉(zhuǎn)換為數(shù)字值后進(jìn)行處理;這樣的系統(tǒng)有幾個(gè)問題,一個(gè)是信號(hào)需要被采樣,其次是信號(hào)被分成若干量階;信號(hào)被采樣,也就意味著我們得到的不是原先的連續(xù)的信號(hào)了,而是一個(gè)離散的一些采集的樣點(diǎn);那么對(duì)時(shí)域信號(hào)進(jìn)行采樣,必然造成頻譜的周期化,如果原先頻譜僅限于有限的帶寬,那么周期化之后,只要周期大于原先的帶寬,那么實(shí)際上沒有混疊失真;而數(shù)字電路限制我們只能進(jìn)行乘加等二進(jìn)制域的計(jì)算,獲得另一些離散的點(diǎn),因此我們不得不將頻譜也進(jìn)行“采樣”,頻域的抽樣導(dǎo)致時(shí)域上又周期化了,好在如果我們只取有限的長(zhǎng)度,可以假定沒采集的部分進(jìn)行的是周期化延拓由于平穩(wěn)系統(tǒng)認(rèn)為信號(hào)可以分解為正余弦函數(shù)的組合,而正余弦函數(shù)是可以周期延拓的,所以這個(gè)假設(shè)沒有問題,那么我們得到了時(shí)域和頻域都是離散的周期延拓的點(diǎn)集;既然是周期延拓的,那么延拓的部分和主值區(qū)間靠近0的那個(gè)周期是重復(fù)的數(shù)值,因此我們只保留主值區(qū)間的部分,這樣的時(shí)域點(diǎn)集到頻域點(diǎn)集的變換關(guān)系叫離散傅里葉變換DFT;然而它的運(yùn)算過于復(fù)雜,因此庫(kù)里和圖基Cooley, Tukey兩人力圖化簡(jiǎn)它,找到了這個(gè)算法的一些內(nèi)在運(yùn)算規(guī)律,得到的運(yùn)算量由原來(lái)的平方級(jí)降為NlogN級(jí),這個(gè)算法就叫按時(shí)間抽取快速傅里葉變換,桑德和圖基研究按頻率抽取也可以得到類似的低復(fù)雜度算法,這類算法統(tǒng)稱快速傅里葉變換FFT,FFT的計(jì)算結(jié)果和DFT是完全等價(jià)的,只是運(yùn)算量降低了;又由于時(shí)頻變換能量不變Parseval定理,所以頻域的絕對(duì)數(shù)值沒有意義了,只要獲得相對(duì)數(shù)值即可,因此數(shù)字系統(tǒng)中的量化階數(shù)以及數(shù)字系統(tǒng)溢出后的縮放調(diào)整對(duì)FFT的計(jì)算結(jié)果影響僅在于精度,而不是對(duì)錯(cuò),從而,FFT正好滿足數(shù)字系統(tǒng)可以處理的前提,同時(shí)運(yùn)算復(fù)雜度不高,因此獲得了廣泛的應(yīng)用;那么,模擬系統(tǒng)能不能做類似的FFT呢可以,構(gòu)造與頻點(diǎn)數(shù)量相同個(gè)數(shù)的帶通濾波器,組成一個(gè)陣列,信號(hào)進(jìn)入這個(gè)帶通濾波器組,每個(gè)濾波器只保留了相應(yīng)頻點(diǎn)為中心的類似于sinc的頻響函數(shù),那么就可以得到FFT的結(jié)果;當(dāng)然,這個(gè)代價(jià)不是一般的系統(tǒng)可以負(fù)擔(dān)的;所以,在沒有數(shù)字電路普及的年代里,FFT基本是數(shù)學(xué)算法,是不可實(shí)現(xiàn)的;

現(xiàn)在知道FFT是什么了,它是傅里葉變換的時(shí)頻離散后的可數(shù)字計(jì)算的一個(gè)變換算法,這個(gè)算法計(jì)算的對(duì)象是時(shí)域上周期延拓的點(diǎn)集的主值區(qū)間部分有限個(gè)數(shù),計(jì)算的結(jié)果是頻譜,也是周期延拓的點(diǎn)集的主值區(qū)間部分,與傅里葉變換等價(jià)的前提是采樣速率大于信號(hào)最大頻率的2倍高頻延拓不混疊,同時(shí)時(shí)域有限長(zhǎng)度之外的部分假定按周期延拓到無(wú)窮;為了滿足第一個(gè)前提,我們往往在信號(hào)處理之前甚至是模數(shù)轉(zhuǎn)換之前加入一個(gè)低通濾波器,使得高頻分量被抑制,對(duì)于比如聲音或者在某個(gè)頻帶內(nèi)的通信系統(tǒng),高頻分量本身就是無(wú)意義的,因此這個(gè)前提可以滿足;為了滿足第二個(gè)前提,我們需要保證采集的樣本在采集區(qū)外的數(shù)值與假想的周期延拓的數(shù)值一致,這顯然做不到,做不到導(dǎo)致的結(jié)果是什么呢頻譜出現(xiàn)泄漏,也就是頻譜能量會(huì)分散到帶外比如余弦不再是一根譜線,而是sinc,分散的過程可以看做時(shí)域加矩形窗和門函數(shù)相乘導(dǎo)致的,那么頻譜相當(dāng)于和sinc函數(shù)的卷積,時(shí)域窗越小也就是采集的點(diǎn)越少,頻譜sinc的主瓣越寬,頻譜泄露越嚴(yán)重,也就是原先一個(gè)頻點(diǎn)的能量會(huì)被散發(fā)到更大的附近范圍里,而自己的峰值會(huì)降低,如果相鄰點(diǎn)各有個(gè)峰值,那么散發(fā)后就難以分辨了,所以系統(tǒng)的實(shí)際分辨率與時(shí)域窗的長(zhǎng)度成反比,采集更多的點(diǎn),才有可能獲得更精細(xì)的頻譜;那么,有沒有辦法減輕這個(gè)泄露呢那么,最好讓邊界處的取值點(diǎn)起的作用小一點(diǎn),中間的部分權(quán)重大一點(diǎn),那么實(shí)際上就乘了一系列加權(quán)的數(shù)值,這些數(shù)值形成的是一個(gè)時(shí)域的窗函數(shù),加窗之后,頻譜泄露會(huì)減輕,能量會(huì)集中一些,但是主瓣會(huì)更寬,這是一個(gè)權(quán)衡;就這樣,兩個(gè)前提條件得以近似滿足,雖然不是完全,但是也夠用了;

這些都是比較基礎(chǔ)的知識(shí)了,下面說(shuō)說(shuō)有趣的事情;如果FFT只用于分析確定性的平穩(wěn)信號(hào),類似于正弦或者若干正弦的復(fù)合的無(wú)限長(zhǎng)周期信號(hào)之類,看看譜線什么的,它將不會(huì)有今天的地位;它還能用來(lái)干嘛呢

1,做快速相關(guān)

相關(guān)在數(shù)字信號(hào)處理的重要程度可以說(shuō)是炙手可熱級(jí)別的;簡(jiǎn)單的講,如果你不知道信號(hào)中的某個(gè)參數(shù)比如頻率,或者相位,或者碼片序列,或者成型波形,那么你就設(shè)計(jì)帶有這個(gè)參數(shù)的所有可能值的一組信號(hào)跟它做一下相關(guān),看看結(jié)果最大的那個(gè),所對(duì)應(yīng)的參數(shù)就是最有可能的了,這個(gè)算法叫做最大似然檢測(cè),相關(guān)往往作為最大似然檢測(cè)的實(shí)際執(zhí)行過程;而很多時(shí)候,這個(gè)需要被測(cè)量的參數(shù)是和時(shí)間延遲有關(guān)的,舉個(gè)例子,手機(jī)開機(jī)后,要和基站同步,也就是說(shuō)要知道每個(gè)數(shù)據(jù)幀開始的時(shí)刻,那么怎么得到呢首先基站和手機(jī)有一個(gè)協(xié)議,在幀的某個(gè)位置會(huì)有一個(gè)固定的序列,這個(gè)序列調(diào)制后會(huì)有一個(gè)固定的波形,那么手機(jī)就可以制造有若干延遲的波形副本,與接收到的波形相關(guān),那么得到峰值所對(duì)應(yīng)的延遲就可以換算出幀的起始時(shí)刻;有關(guān)相關(guān)的強(qiáng)大以后找機(jī)會(huì)再聊,那么相關(guān)和FFT有什么關(guān)系呢相關(guān)和卷積都是復(fù)雜度非常大的運(yùn)算,每計(jì)算一個(gè)延遲下的相關(guān)值,都需要兩個(gè)波形所有非零部分對(duì)應(yīng)相乘并且加和得到,所有的延遲下相關(guān)值構(gòu)成一條曲線,叫相關(guān)函數(shù);而當(dāng)把信號(hào)轉(zhuǎn)換為頻域后,獲取相關(guān)函數(shù)的過程可以被簡(jiǎn)化成一個(gè)信號(hào)的共軛把虛部取反與另外一個(gè)信號(hào)相乘的過程;即使加上正負(fù)兩個(gè)FFT的開銷,算下來(lái)仍然比原來(lái)小很多N方和NlogN級(jí)的差別,這樣一來(lái),相關(guān)算法的復(fù)雜度被大大降低;那么有時(shí)候,輸入的信號(hào)太長(zhǎng)了,怎么辦大家又發(fā)現(xiàn)相關(guān)操作可以分段進(jìn)行,可以逐段相關(guān)最后拼合起來(lái),就得到了相關(guān)后的結(jié)果;這樣一來(lái),手機(jī)的定時(shí)的操作可以用一個(gè)快速相關(guān)的過程搞定;再舉個(gè)例子,雷達(dá)如果想定位一個(gè)目標(biāo)的距離,怎么做呢最簡(jiǎn)單的想法是打一個(gè)沖擊信號(hào),看它什么時(shí)候回來(lái),時(shí)延乘上光速除以2就是距離,但是,類似于沖激函數(shù)的波形對(duì)于功放來(lái)講實(shí)在很難實(shí)現(xiàn),因此雷達(dá)系統(tǒng)實(shí)際上打出去的是具有一定時(shí)間長(zhǎng)度的帶寬很大的信號(hào),比如chirp或者某種成型,在接收時(shí),我們需要知道這個(gè)信號(hào)被延遲了多少,因此把它和本地的成型波形副本進(jìn)行相關(guān),成功的相關(guān)操作會(huì)得到一個(gè)帶有若干峰值點(diǎn)的波形,這些峰值點(diǎn)對(duì)應(yīng)的位置就是若干目標(biāo)的回波時(shí)延值,換算出來(lái)就是位置,這個(gè)將波形能量壓縮到點(diǎn)的過程一般是采用FFT實(shí)現(xiàn)的;

2,快速卷積

類似與相關(guān),信號(hào)處理的一大操作類型是卷積,一個(gè)系統(tǒng)可以采用系統(tǒng)函數(shù)來(lái)表征,其輸出就是輸入數(shù)據(jù)卷積上系統(tǒng)函數(shù),或?qū)τ谄椒€(wěn)的隨機(jī)信號(hào)而言,輸出為輸入數(shù)據(jù)卷積上系統(tǒng)函數(shù)模值的平方;卷積操作常常用于對(duì)信號(hào)進(jìn)行FIR濾波,因?yàn)镕IR濾波器是不帶反饋的,沒有記憶,可以用卷積算法直接得到輸出;那么,如果數(shù)據(jù)是塊數(shù)據(jù)不是按時(shí)鐘節(jié)拍的流數(shù)據(jù),用快速卷積就可以降低運(yùn)算量;其過程與快速相關(guān)雷同,區(qū)別是頻域相乘時(shí)無(wú)需共軛;想一下,如果FM收音機(jī)收到好幾個(gè)臺(tái),相互靠的很近,怎么辦可以采用階數(shù)比較高的FIR帶通濾波器選出想要的那個(gè)臺(tái),例如德生的DSP芯片解調(diào)的收音機(jī)可以做到的分辨率,這就是現(xiàn)在我們的數(shù)字FM收音機(jī)比原來(lái)的模擬FM收音機(jī)音質(zhì)好的原因之一;

3,經(jīng)典譜估計(jì)

在實(shí)際的生活里,我們不可能見到的都是確定的無(wú)限長(zhǎng)的正余弦類的疊加的信號(hào),最起碼這樣的信號(hào)在傳輸過程中也會(huì)疊加上噪聲,即高斯白噪聲,因此傅里葉變換頻譜分析的前提無(wú)法滿足,這樣的時(shí)頻變換也就沒有了實(shí)際意義,退一步,我們可以分析的往往是無(wú)限長(zhǎng)的,隨機(jī)的,但在隨機(jī)意義上自相關(guān)等二階統(tǒng)計(jì)特性上平穩(wěn)的信號(hào),如果達(dá)不到這個(gè)前提,起碼可以在某個(gè)時(shí)間段內(nèi)滿足;這樣的信號(hào)往往自身是隨機(jī)的,但是自相關(guān)和互相關(guān)特性往往包含信號(hào)的二階統(tǒng)計(jì)信息;而對(duì)于實(shí)際的系統(tǒng),我們只能估計(jì)它,相關(guān)函數(shù)估計(jì)的一個(gè)基礎(chǔ)方法是將一個(gè)信號(hào)和帶有延遲并共軛后的另一個(gè)信號(hào)的點(diǎn)乘運(yùn)算,得到的是基于延遲的函數(shù);上文已述,用FFT就可以搞定它;

在這種隨機(jī)信號(hào)的分析上,有一個(gè)重要的定理,叫做winner-khintchine定理,它證明了信號(hào)的自相關(guān)和信號(hào)的功率譜之間的關(guān)系是FFT變換;這個(gè)有意思的橋梁使得我們可以做幾件事,一個(gè)是利用自相關(guān)的估計(jì)通過FFT得到功率譜,而自相關(guān)估計(jì)通過快速相關(guān)算法計(jì)算;細(xì)心的人會(huì)發(fā)現(xiàn),這個(gè)流程最后一個(gè)FFT緊接IFFT,抵消后實(shí)際上只需要一個(gè)FFT,而不是三個(gè),那么這樣的功率譜估計(jì)叫周期圖法功率譜估計(jì),也是我們最經(jīng)常使用的經(jīng)典譜估計(jì);值得注意的是,信號(hào)的功率譜實(shí)際上對(duì)應(yīng)的是自相關(guān)的理想值,而不是通過接收到的數(shù)據(jù)得到的估計(jì)值上邊用快速相關(guān)算的是估計(jì)值,這個(gè)估計(jì)如果采用了邊界處的點(diǎn),那么相關(guān)的數(shù)值由于假象邊界外數(shù)值為0而造成了偏差,如果我們只利用中心的若干點(diǎn),那么會(huì)相對(duì)準(zhǔn)確一些,這個(gè)計(jì)算自相關(guān)后選取可靠的點(diǎn),再進(jìn)行傅里葉的做法叫做自相關(guān)法功率譜估計(jì);最有趣的是,兩個(gè)方法可以復(fù)合使用,先對(duì)數(shù)據(jù)分段交疊進(jìn)行周期圖估計(jì),取這些結(jié)果的均值IFFT得到自相關(guān),取自相關(guān)的加窗類似于上文的加權(quán)的作用得到更好的自相關(guān)估計(jì),再FFT得到譜估計(jì),這個(gè)方法是認(rèn)為改進(jìn)的比較好的經(jīng)典譜估計(jì),叫Welch法;這些方法之所以能夠被接納,主要是由于FFT的橋梁的作用;否則,這樣的方法就無(wú)法應(yīng)用到系統(tǒng)中了;頻譜儀這類的儀器就可以采用這些經(jīng)典譜估計(jì)算法當(dāng)然也有掃頻的;另外,由于功率譜的峰值的下標(biāo)代表著信號(hào)的頻率,如果這個(gè)信號(hào)是物體的反射回波,那么可以根據(jù)多普勒公式換算出物體的速度,一類采用這種測(cè)速機(jī)制的雷達(dá)叫脈沖多普勒雷達(dá);

4,現(xiàn)代譜估計(jì)

為了取得更精確的譜估計(jì),有些學(xué)者認(rèn)為可以通過構(gòu)造模型,并且設(shè)待定參數(shù)的方法,獲得更好的譜估計(jì),只要系統(tǒng)模型設(shè)計(jì)得合理,待定參數(shù)被估計(jì)得有效,那么對(duì)信號(hào)的譜估計(jì)可以轉(zhuǎn)化為這個(gè)模型的譜,這樣就可以得到更為精確的估計(jì)效果;這樣的基于模型的譜估計(jì)叫現(xiàn)代譜估計(jì);那么怎么叫合理呢大家認(rèn)為歐式距離最小化比較合理,也就是最小均方準(zhǔn)則,在這個(gè)準(zhǔn)則下,加上線性系統(tǒng)的前提條件,那個(gè)有趣的平方的期望被轉(zhuǎn)化為系統(tǒng)的自相關(guān)和互相關(guān)項(xiàng)Wiener－Hopf方程,而這兩個(gè)項(xiàng)的估計(jì)方法,無(wú)需多問,也只能是采用快速相關(guān)完成比較有效,這就是FFT在有了現(xiàn)代譜估計(jì),AR模型,MA模型等理論以后,仍能派上用場(chǎng)的一些原因;起碼在計(jì)算上,自相關(guān)法是已知的AR參數(shù)估計(jì)方法中最簡(jiǎn)單的一種;估計(jì)出模型后,我們還可以做別的事情,比如根據(jù)模型來(lái)估計(jì)信號(hào)未來(lái)的趨勢(shì),叫做信號(hào)的預(yù)測(cè),也可以對(duì)已經(jīng)采集的信號(hào)通過這個(gè)模型進(jìn)行平滑處理等等;再比如,如果想測(cè)量一個(gè)物體的方位怎么做在現(xiàn)代雷達(dá)中,一般會(huì)有一個(gè)天線陣列,如果接收到的物體的回波與天線陣列有個(gè)角度的話,那么不同的天線會(huì)接收到回波不同時(shí)刻不同相位,幅度基本不變的值,那么,可以利用若干天線的回波信號(hào)估計(jì)出若干目標(biāo)物體的方位角度,叫做到達(dá)角DOA估計(jì),有兩個(gè)經(jīng)典的算法：MUSIC和ESPRIT,他們都是二階統(tǒng)計(jì)信號(hào)算法,依賴于自相關(guān)矩陣作為計(jì)算的起始,因而FFT可以作為自相關(guān)估計(jì)的快速算法;

5,構(gòu)建正交系統(tǒng)

一個(gè)FFT得到的離散頻譜和原先的連續(xù)頻譜在離散點(diǎn)之間值遵循什么規(guī)律這些部分可以認(rèn)為是一族正交的sinc函數(shù)疊加的結(jié)果,也可以認(rèn)為是一個(gè)主瓣寬度為頻譜間隔寬度的sinc函數(shù)與沖積函數(shù)串卷積的結(jié)果因?yàn)闀r(shí)域是矩形窗與原信號(hào)相乘的結(jié)果,此處的正交指的是一個(gè)離散點(diǎn)的值與另一個(gè)離散點(diǎn)的值沒有關(guān)系,互不影響,這樣的系統(tǒng)可以用來(lái)構(gòu)建通信收發(fā)信機(jī),由于采用sinc函數(shù)正交的效果是頻譜效率最好的采用抑制帶寬的辦法雖然可以抑制每個(gè)子帶的帶外旁瓣,但是會(huì)造成時(shí)域信號(hào)的延拓,從而造成符號(hào)間干擾;正交頻分復(fù)用OFDM正是利用了各個(gè)離散頻點(diǎn)之間的正交特性構(gòu)建了一個(gè)高性能低運(yùn)算復(fù)雜度的收發(fā)機(jī);其工作原理是首先將要發(fā)射的數(shù)據(jù)放置在各個(gè)頻點(diǎn)上,一般采用QAM或PSK調(diào)制,之后IFFT得到時(shí)域信號(hào)發(fā)射出去,這些頻點(diǎn)數(shù)據(jù)形成的時(shí)域發(fā)射波形實(shí)際上是一組頻率倍數(shù)關(guān)系的正交余弦函數(shù),接收機(jī)收到這樣的信號(hào)后,再進(jìn)行FFT,轉(zhuǎn)換到頻域或者說(shuō)是正交域,從而得到每個(gè)頻點(diǎn)上的傳輸?shù)姆?hào)的估計(jì);這個(gè)系統(tǒng)的巧妙之處在于克服了寬帶無(wú)線通信系統(tǒng)的多徑衰落,因?yàn)?從整個(gè)頻帶上看,信道不是一個(gè)常數(shù),有的頻點(diǎn)的數(shù)值增強(qiáng)了,有的減弱了,同時(shí)還有相位扭曲;但是當(dāng)把它分成很多正交的子信道之后,這些信道內(nèi)部可以看做為平坦的,那么通過均衡器,比如迫零均衡之后,我們就可以得到類似于沖擊響應(yīng)的子信道特性,從而解調(diào)出每個(gè)子信道符號(hào)的值;由于子信道之間正交,互不干擾,因此可以實(shí)現(xiàn)多載波通信,并行傳輸所有的數(shù)據(jù),大大加快了傳輸速度,這也就是4G移動(dòng)通信速度可以達(dá)到百兆甚至更高的核心技術(shù)之一;

如今,FFT運(yùn)算能力已經(jīng)成為處理器的性能標(biāo)尺之一;比如一個(gè)TI C6000系列的高性能DSP處理器,可以在半個(gè)時(shí)鐘輸出一個(gè)數(shù)據(jù)點(diǎn),那么可以做到幾百兆比特每秒的處理速率;硬件的優(yōu)化使得FFT已經(jīng)成為信號(hào)處理算法內(nèi)部的高速公路;FFT的意義可能遠(yuǎn)不止這些,而且也有許多的變種,比如二維FFT,DCT等等,在圖像領(lǐng)域發(fā)揮著圖像模糊清晰,輪廓化,壓縮等貢獻(xiàn);本文只是一個(gè)引子,讓致力于研究和開發(fā)數(shù)字系統(tǒng)的同行能夠更清晰地理解系統(tǒng)的原理和算法的實(shí)質(zhì);所提及的內(nèi)容都是信號(hào)處理的基礎(chǔ)書籍,一般的碩士課程多有涉及,如此整理一番也算有點(diǎn)新意,希望對(duì)大家有所借鑒;