談?wù)凢FT到底有何用

1、談?wù)凢FT到底有何用FFT（快速傅里葉變換）是數(shù)字信號(hào)處理的經(jīng)典算法，學(xué)過(guò)DSP或者芯片設(shè)計(jì)的人大多知道這個(gè)算法。但是，大家是否想過(guò)，為什么數(shù)字信號(hào)處理會(huì)有那么多FFT呢？有人會(huì)說(shuō)，為了分析信號(hào)的頻譜。那么下邊的問(wèn)題就是，分析頻譜對(duì)我們的日常需求，比如手機(jī)打電話，雷達(dá)測(cè)量速度和方向等等一些與實(shí)際需求有什么聯(lián)系？為什么FFT如此重要？本文舉一些簡(jiǎn)明的例子，闡釋一下FFT到底有什么用。 先回憶一下FFT是什么。上世紀(jì)70年代之前，我們主要通過(guò)模擬電路來(lái)進(jìn)行信號(hào)處理，比如大家熟悉的用二極管和電容進(jìn)行AM調(diào)制信號(hào)的包絡(luò)檢波一樣，隨著數(shù)字系統(tǒng)的普及，我們可以用處理器或者數(shù)字電路更為精確的處理信

2、號(hào)，比如我們做AM檢波，實(shí)際上可以用載波把信號(hào)混頻（與余弦函數(shù)做乘法），再進(jìn)行低通濾波，那么這個(gè)過(guò)程可以用數(shù)字電路的乘法器和FIR濾波器來(lái)做，F(xiàn)IR比二極管和電容構(gòu)成的低通濾波器階數(shù)高的多，性能自然更為理想，同時(shí)，由于數(shù)字電路易于做成集成電路，因此我們更多地是將原先的模擬信號(hào)（比如麥克風(fēng)的音頻）通過(guò)模擬-數(shù)字轉(zhuǎn)換器，轉(zhuǎn)換為數(shù)字值后進(jìn)行處理。這樣的系統(tǒng)有幾個(gè)問(wèn)題，一個(gè)是信號(hào)需要被采樣，其次是信號(hào)被分成若干量階。信號(hào)被采樣，也就意味著我們得到的不是原先的連續(xù)的信號(hào)了，而是一個(gè)離散的一些采集的樣點(diǎn)。那么對(duì)時(shí)域信號(hào)進(jìn)行采樣，必然造成頻譜的周期化，如果原先頻譜僅限于有限的帶寬，那么周期化之后，只要周期大

3、于原先的帶寬，那么實(shí)際上沒(méi)有混疊失真。而數(shù)字電路限制我們只能進(jìn)行乘加等二進(jìn)制域的計(jì)算，獲得另一些離散的點(diǎn)，因此我們不得不將頻譜也進(jìn)行“采樣”，頻域的抽樣導(dǎo)致時(shí)域上又周期化了，好在如果我們只取有限的長(zhǎng)度，可以假定沒(méi)采集的部分進(jìn)行的是周期化延拓（由于平穩(wěn)系統(tǒng)認(rèn)為信號(hào)可以分解為正余弦函數(shù)的組合，而正余弦函數(shù)是可以周期延拓的，所以這個(gè)假設(shè)沒(méi)有問(wèn)題），那么我們得到了時(shí)域和頻域都是離散的周期延拓的點(diǎn)集。既然是周期延拓的，那么延拓的部分和主值區(qū)間（靠近0的那個(gè)周期）是重復(fù)的數(shù)值，因此我們只保留主值區(qū)間的部分，這樣的時(shí)域點(diǎn)集到頻域點(diǎn)集的變換關(guān)系叫離散傅里葉變換（DFT）。然而它的運(yùn)算過(guò)于復(fù)雜，因此庫(kù)里和圖基（

4、Cooley, Tukey）兩人力圖化簡(jiǎn)它，找到了這個(gè)算法的一些內(nèi)在運(yùn)算規(guī)律，得到的運(yùn)算量由原來(lái)的平方級(jí)降為NlogN級(jí)，這個(gè)算法就叫按時(shí)間抽取快速傅里葉變換，桑德和圖基研究按頻率抽取也可以得到類似的低復(fù)雜度算法，這類算法統(tǒng)稱快速傅里葉變換（FFT），F(xiàn)FT的計(jì)算結(jié)果和DFT是完全等價(jià)的，只是運(yùn)算量降低了。又由于時(shí)頻變換能量不變（Parseval定理），所以頻域的絕對(duì)數(shù)值沒(méi)有意義了，只要獲得相對(duì)數(shù)值即可，因此數(shù)字系統(tǒng)中的量化階數(shù)以及數(shù)字系統(tǒng)溢出后的縮放調(diào)整對(duì)FFT的計(jì)算結(jié)果影響僅在于精度，而不是對(duì)錯(cuò)，從而，F(xiàn)FT正好滿足數(shù)字系統(tǒng)可以處理的前提，同時(shí)運(yùn)算復(fù)雜度不高，因此獲得了廣泛的應(yīng)用。那么，模

5、擬系統(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)的。所以，在沒(méi)有數(shù)字電路普及的年代里，F(xiàn)FT基本是數(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í)

6、域有限長(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），分散的過(guò)程可以看做時(shí)域加矩形窗（和門函數(shù)相乘）導(dǎo)致的，那么頻譜相當(dāng)于和sinc函數(shù)的卷積，時(shí)域窗越?。ㄒ簿褪遣杉狞c(diǎn)越少），頻譜sinc的主瓣越寬，頻譜泄露越

7、嚴(yán)重，也就是原先一個(gè)頻點(diǎn)的能量會(huì)被散發(fā)到更大的附近范圍里，而自己的峰值會(huì)降低，如果相鄰點(diǎn)各有個(gè)峰值，那么散發(fā)后就難以分辨了，所以系統(tǒng)的實(shí)際分辨率與時(shí)域窗的長(zhǎng)度成反比，采集更多的點(diǎn)，才有可能獲得更精細(xì)的頻譜。那么，有沒(méi)有辦法減輕這個(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)，

8、類似于正弦或者若干正弦的復(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í)行過(guò)程。而很多時(shí)候，這個(gè)需要被測(cè)量的參數(shù)是和時(shí)間延遲有關(guān)的，舉個(gè)例子，手機(jī)開(kāi)機(jī)后，要和基站同步，也就是說(shuō)要知道每個(gè)數(shù)據(jù)幀開(kāi)始的時(shí)刻，那么怎么得到呢？首先基站

9、和手機(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ù)的過(guò)程可以被簡(jiǎn)化成一個(gè)信號(hào)的共軛（把虛部取反）與另外一個(gè)信號(hào)相乘的過(guò)程。即使加上正負(fù)兩個(gè)FFT的開(kāi)銷，算下來(lái)仍然比原來(lái)小很多（N方和NlogN級(jí)的差別），這

10、樣一來(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)的過(guò)程搞定。再舉個(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)

11、的波形，這些峰值點(diǎn)對(duì)應(yīng)的位置就是若干目標(biāo)的回波時(shí)延值，換算出來(lái)就是位置，這個(gè)將波形能量壓縮到點(diǎn)的過(guò)程一般是采用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濾波器是不帶反饋的，沒(méi)有記憶，可以用卷積算法直接得到輸出。那么，如果數(shù)據(jù)是塊數(shù)據(jù)（不是按時(shí)鐘節(jié)拍的流數(shù)據(jù)），用快速卷積就可以降低運(yùn)算量。其過(guò)程與快速相關(guān)雷同，區(qū)別是頻域相乘時(shí)無(wú)需共軛。想一下，如果FM收音機(jī)收到好幾個(gè)臺(tái)，相互靠的很近，怎么辦？

12、可以采用階數(shù)比較高的FIR帶通濾波器選出想要的那個(gè)臺(tái)，例如德生的DSP芯片解調(diào)的收音機(jī)可以做到0.01MHz的分辨率，這就是現(xiàn)在我們的數(shù)字FM收音機(jī)比原來(lái)的模擬FM收音機(jī)音質(zhì)好的原因之一。3，經(jīng)典譜估計(jì)在實(shí)際的生活里，我們不可能見(jiàn)到的都是確定的無(wú)限長(zhǎng)的正余弦類的疊加的信號(hào)，最起碼這樣的信號(hào)在傳輸過(guò)程中也會(huì)疊加上噪聲，即高斯白噪聲，因此傅里葉變換頻譜分析的前提無(wú)法滿足，這樣的時(shí)頻變換也就沒(méi)有了實(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)特性

13、往往包含信號(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ì)通過(guò)FFT得到功率譜，而自相關(guān)估計(jì)通過(guò)快速相關(guān)算法計(jì)算。細(xì)心的人會(huì)發(fā)現(xiàn)，這個(gè)流程最后一個(gè)FFT緊接IFFT，抵消后實(shí)際上只需要一個(gè)FFT，而不是三個(gè)，那么這樣的功率譜估計(jì)叫周期圖法功率譜估計(jì)，也是我

14、們最經(jīng)常使用的經(jīng)典譜估計(jì)。值得注意的是，信號(hào)的功率譜實(shí)際上對(duì)應(yīng)的是自相關(guān)的理想值，而不是通過(guò)接收到的數(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法。這些方法之所

15、以能夠被接納，主要是由于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)為可以通過(guò)構(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)為歐

16、式距離最小化比較合理，也就是最小均方準(zhǔn)則，在這個(gè)準(zhǔn)則下，加上線性系統(tǒng)的前提條件，那個(gè)有趣的平方的期望被轉(zhuǎn)化為系統(tǒng)的自相關(guān)和互相關(guān)項(xiàng)（WienerHopf方程），而這兩個(gè)項(xiàng)的估計(jì)方法，無(wú)需多問(wèn)，也只能是采用快速相關(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)通過(guò)這個(gè)模型進(jìn)行平滑處理等等。再比如，如果想測(cè)量一個(gè)物體的方位怎么做？在現(xiàn)代雷達(dá)中，一般會(huì)有一個(gè)天線陣列，如果接收到的物

17、體的回波與天線陣列有個(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è)離

18、散點(diǎn)的值與另一個(gè)離散點(diǎn)的值沒(méi)有關(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)部可以看做為平坦的，那么通過(guò)均衡器，比如迫零均衡之后，我們就可以得到類似于沖擊響應(yīng)的子信道特性，從而解調(diào)出每個(gè)子信道符號(hào)的值。由于子信道之間正交，互不干擾，因此可以實(shí)現(xiàn)多載波通信，并行傳輸所有的數(shù)據(jù)，大大加快了傳輸速度，這也就是4G移動(dòng)通信速度可以達(dá)到百兆甚至更高的核心技術(shù)之一。如今，F(xiàn)FT運(yùn)算能力已經(jīng)成為處理器