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

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

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

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

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

5、擬系統(tǒng)能不能做類似的FFT呢？可以，構(gòu)造與頻點數(shù)量相同個數(shù)的帶通濾波器，組成一個陣列，信號進入這個帶通濾波器組，每個濾波器只保留了相應(yīng)頻點為中心的類似于sinc的頻響函數(shù)，那么就可以得到FFT的結(jié)果。當然，這個代價不是一般的系統(tǒng)可以負擔的。所以，在沒有數(shù)字電路普及的年代里，F(xiàn)FT基本是數(shù)學算法，是不可實現(xiàn)的。 現(xiàn)在知道FFT是什么了，它是傅里葉變換的時頻離散后的可數(shù)字計算的一個變換算法，這個算法計算的對象是時域上周期延拓的點集的主值區(qū)間部分（有限個數(shù)），計算的結(jié)果是頻譜，也是周期延拓的點集的主值區(qū)間部分，與傅里葉變換等價的前提是采樣速率大于信號最大頻率的2倍（高頻延拓不混疊），同時時

6、域有限長度之外的部分假定按周期延拓到無窮。為了滿足第一個前提，我們往往在信號處理之前（甚至是模數(shù)轉(zhuǎn)換之前）加入一個低通濾波器，使得高頻分量被抑制，對于比如聲音或者在某個頻帶內(nèi)的通信系統(tǒng)，高頻分量本身就是無意義的，因此這個前提可以滿足。為了滿足第二個前提，我們需要保證采集的樣本在采集區(qū)外的數(shù)值與假想的周期延拓的數(shù)值一致，這顯然做不到，做不到導致的結(jié)果是什么呢？頻譜出現(xiàn)泄漏，也就是頻譜能量會分散到帶外（比如余弦不再是一根譜線，而是sinc），分散的過程可以看做時域加矩形窗（和門函數(shù)相乘）導致的，那么頻譜相當于和sinc函數(shù)的卷積，時域窗越小（也就是采集的點越少），頻譜sinc的主瓣越寬，頻譜泄露越

7、嚴重，也就是原先一個頻點的能量會被散發(fā)到更大的附近范圍里，而自己的峰值會降低，如果相鄰點各有個峰值，那么散發(fā)后就難以分辨了，所以系統(tǒng)的實際分辨率與時域窗的長度成反比，采集更多的點，才有可能獲得更精細的頻譜。那么，有沒有辦法減輕這個泄露呢？那么，最好讓邊界處的取值點起的作用小一點，中間的部分權(quán)重大一點，那么實際上就乘了一系列加權(quán)的數(shù)值，這些數(shù)值形成的是一個時域的窗函數(shù)，加窗之后，頻譜泄露會減輕，能量會集中一些，但是主瓣會更寬，這是一個權(quán)衡。就這樣，兩個前提條件得以近似滿足，雖然不是完全，但是也夠用了。 這些都是比較基礎(chǔ)的知識了，下面說說有趣的事情。如果FFT只用于分析確定性的平穩(wěn)信號，

8、類似于正弦或者若干正弦的復合的無限長周期信號之類，看看譜線什么的，它將不會有今天的地位。它還能用來干嘛呢？ 1，做快速相關(guān)相關(guān)在數(shù)字信號處理的重要程度可以說是炙手可熱級別的。簡單的講，如果你不知道信號中的某個參數(shù)（比如頻率，或者相位，或者碼片序列，或者成型波形），那么你就設(shè)計帶有這個參數(shù)的所有可能值的一組信號跟它做一下相關(guān)，看看結(jié)果最大的那個，所對應(yīng)的參數(shù)就是最有可能的了，這個算法叫做最大似然檢測，相關(guān)往往作為最大似然檢測的實際執(zhí)行過程。而很多時候，這個需要被測量的參數(shù)是和時間延遲有關(guān)的，舉個例子，手機開機后，要和基站同步，也就是說要知道每個數(shù)據(jù)幀開始的時刻，那么怎么得到呢？首先基站

9、和手機有一個協(xié)議，在幀的某個位置會有一個固定的序列，這個序列調(diào)制后會有一個固定的波形，那么手機就可以制造有若干延遲的波形副本，與接收到的波形相關(guān)，那么得到峰值所對應(yīng)的延遲就可以換算出幀的起始時刻。有關(guān)相關(guān)的強大以后找機會再聊，那么相關(guān)和FFT有什么關(guān)系呢？相關(guān)和卷積都是復雜度非常大的運算，每計算一個延遲下的相關(guān)值，都需要兩個波形所有非零部分對應(yīng)相乘并且加和得到，所有的延遲下相關(guān)值構(gòu)成一條曲線，叫相關(guān)函數(shù)。而當把信號轉(zhuǎn)換為頻域后，獲取相關(guān)函數(shù)的過程可以被簡化成一個信號的共軛（把虛部取反）與另外一個信號相乘的過程。即使加上正負兩個FFT的開銷，算下來仍然比原來小很多（N方和NlogN級的差別），這

10、樣一來，相關(guān)算法的復雜度被大大降低。那么有時候，輸入的信號太長了，怎么辦？大家又發(fā)現(xiàn)相關(guān)操作可以分段進行，可以逐段相關(guān)最后拼合起來，就得到了相關(guān)后的結(jié)果。這樣一來，手機的定時的操作可以用一個快速相關(guān)的過程搞定。再舉個例子，雷達如果想定位一個目標的距離，怎么做呢？最簡單的想法是打一個沖擊信號，看它什么時候回來，時延乘上光速除以2就是距離，但是，類似于沖激函數(shù)的波形對于功放來講實在很難實現(xiàn)，因此雷達系統(tǒng)實際上打出去的是具有一定時間長度的帶寬很大的信號，比如chirp或者某種成型，在接收時，我們需要知道這個信號被延遲了多少，因此把它和本地的成型波形副本進行相關(guān)，成功的相關(guān)操作會得到一個帶有若干峰值點

11、的波形，這些峰值點對應(yīng)的位置就是若干目標的回波時延值，換算出來就是位置，這個將波形能量壓縮到點的過程一般是采用FFT實現(xiàn)的。2，快速卷積類似與相關(guān)，信號處理的一大操作類型是卷積，一個系統(tǒng)可以采用系統(tǒng)函數(shù)來表征，其輸出就是輸入數(shù)據(jù)卷積上系統(tǒng)函數(shù)，或?qū)τ谄椒€(wěn)的隨機信號而言，輸出為輸入數(shù)據(jù)卷積上系統(tǒng)函數(shù)模值的平方。卷積操作常常用于對信號進行FIR濾波，因為FIR濾波器是不帶反饋的，沒有記憶，可以用卷積算法直接得到輸出。那么，如果數(shù)據(jù)是塊數(shù)據(jù)（不是按時鐘節(jié)拍的流數(shù)據(jù)），用快速卷積就可以降低運算量。其過程與快速相關(guān)雷同，區(qū)別是頻域相乘時無需共軛。想一下，如果FM收音機收到好幾個臺，相互靠的很近，怎么辦？

12、可以采用階數(shù)比較高的FIR帶通濾波器選出想要的那個臺，例如德生的DSP芯片解調(diào)的收音機可以做到0.01MHz的分辨率，這就是現(xiàn)在我們的數(shù)字FM收音機比原來的模擬FM收音機音質(zhì)好的原因之一。3，經(jīng)典譜估計在實際的生活里，我們不可能見到的都是確定的無限長的正余弦類的疊加的信號，最起碼這樣的信號在傳輸過程中也會疊加上噪聲，即高斯白噪聲，因此傅里葉變換頻譜分析的前提無法滿足，這樣的時頻變換也就沒有了實際意義，退一步，我們可以分析的往往是無限長的，隨機的，但在隨機意義上（自相關(guān)等二階統(tǒng)計特性上）平穩(wěn)的信號，如果達不到這個前提，起碼可以在某個時間段內(nèi)滿足。這樣的信號往往自身是隨機的，但是自相關(guān)和互相關(guān)特性

13、往往包含信號的二階統(tǒng)計信息。而對于實際的系統(tǒng)，我們只能估計它，相關(guān)函數(shù)估計的一個基礎(chǔ)方法是將一個信號和帶有延遲并共軛后的另一個信號的點乘運算，得到的是基于延遲的函數(shù)。上文已述，用FFT就可以搞定它。在這種隨機信號的分析上，有一個重要的定理，叫做winner-khintchine定理，它證明了信號的自相關(guān)和信號的功率譜之間的關(guān)系是FFT變換。這個有意思的橋梁使得我們可以做幾件事，一個是利用自相關(guān)的估計通過FFT得到功率譜，而自相關(guān)估計通過快速相關(guān)算法計算。細心的人會發(fā)現(xiàn)，這個流程最后一個FFT緊接IFFT，抵消后實際上只需要一個FFT，而不是三個，那么這樣的功率譜估計叫周期圖法功率譜估計，也是我

14、們最經(jīng)常使用的經(jīng)典譜估計。值得注意的是，信號的功率譜實際上對應(yīng)的是自相關(guān)的理想值，而不是通過接收到的數(shù)據(jù)得到的估計值（上邊用快速相關(guān)算的是估計值），這個估計如果采用了邊界處的點，那么相關(guān)的數(shù)值由于假象邊界外數(shù)值為0而造成了偏差，如果我們只利用中心的若干點，那么會相對準確一些，這個計算自相關(guān)后選取可靠的點，再進行傅里葉的做法叫做自相關(guān)法功率譜估計。最有趣的是，兩個方法可以復合使用，先對數(shù)據(jù)分段交疊進行周期圖估計，取這些結(jié)果的均值IFFT得到自相關(guān)，取自相關(guān)的加窗（類似于上文的加權(quán)的作用）得到更好的自相關(guān)估計，再FFT得到譜估計，這個方法是認為改進的比較好的經(jīng)典譜估計，叫Welch法。這些方法之所

15、以能夠被接納，主要是由于FFT的橋梁的作用。否則，這樣的方法就無法應(yīng)用到系統(tǒng)中了。頻譜儀這類的儀器就可以采用這些經(jīng)典譜估計算法（當然也有掃頻的）。另外，由于功率譜的峰值的下標代表著信號的頻率，如果這個信號是物體的反射回波，那么可以根據(jù)多普勒公式換算出物體的速度，一類采用這種測速機制的雷達叫脈沖多普勒雷達。4，現(xiàn)代譜估計為了取得更精確的譜估計，有些學者認為可以通過構(gòu)造模型，并且設(shè)待定參數(shù)的方法，獲得更好的譜估計，只要系統(tǒng)模型設(shè)計得合理，待定參數(shù)被估計得有效，那么對信號的譜估計可以轉(zhuǎn)化為這個模型的譜，這樣就可以得到更為精確的估計效果。這樣的基于模型的譜估計叫現(xiàn)代譜估計。那么怎么叫合理呢？大家認為歐

16、式距離最小化比較合理，也就是最小均方準則，在這個準則下，加上線性系統(tǒng)的前提條件，那個有趣的平方的期望被轉(zhuǎn)化為系統(tǒng)的自相關(guān)和互相關(guān)項（WienerHopf方程），而這兩個項的估計方法，無需多問，也只能是采用快速相關(guān)完成比較有效，這就是FFT在有了現(xiàn)代譜估計，AR模型，MA模型等理論以后，仍能派上用場的一些原因。起碼在計算上，自相關(guān)法是已知的AR參數(shù)估計方法中最簡單的一種。估計出模型后，我們還可以做別的事情，比如根據(jù)模型來估計信號未來的趨勢，叫做信號的預(yù)測，也可以對已經(jīng)采集的信號通過這個模型進行平滑處理等等。再比如，如果想測量一個物體的方位怎么做？在現(xiàn)代雷達中，一般會有一個天線陣列，如果接收到的物

17、體的回波與天線陣列有個角度的話，那么不同的天線會接收到回波不同時刻（不同相位，幅度基本不變）的值，那么，可以利用若干天線的回波信號估計出若干目標物體的方位角度，叫做到達角（DOA）估計，有兩個經(jīng)典的算法：MUSIC和ESPRIT，他們都是二階統(tǒng)計信號算法，依賴于自相關(guān)矩陣作為計算的起始，因而FFT可以作為自相關(guān)估計的快速算法。5，構(gòu)建正交系統(tǒng)一個FFT得到的離散頻譜和原先的連續(xù)頻譜在離散點之間值遵循什么規(guī)律？這些部分可以認為是一族正交的sinc函數(shù)疊加的結(jié)果，也可以認為是一個主瓣寬度為頻譜間隔寬度的sinc函數(shù)與沖積函數(shù)串卷積的結(jié)果（因為時域是矩形窗與原信號相乘的結(jié)果），此處的正交指的是一個離

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