FFT--快速傅里葉變換

如果說改變世界必須了解的算法，那么FFT絕對占一席之位。

理論介紹 & 工程應用

理論介紹

1

傅里葉變換與離散傅里葉變換

傅里葉變換公式是基于連續定義的，但是在我們的計算機對數據的處理都是離散的，所以必須對傅里葉變換進行離散化，進而有了離散傅里葉變換。

2

快速傅里葉變換

快速傅立葉變換（FFT）是離散傅立葉(DFT)的快速算法，它是根據離散傅立葉變換的奇、偶、虛、實等特性，對離散傅立葉變換的算法進行改進獲得的。它對傅立葉變換的理論并沒有新的發現，但是對于在計算機系統或者說數字系統中應用離散傅立葉變換，可以說是進了一大步。

FFT是基于DFT的一種算法，目的是為了加快DFT的計算速度。當采樣點N=65536=2^16，DFT的計算量約是FFT的4096倍。

FFT典型的時域2分裂算法圖示如下：

3

物理意義

任何連續測量的時序或信號，都可以表示為不同頻率的正弦波信號的無限疊加。有些信號在時域上是很難看出什么特征的，但是如果變換到頻域之后，就很容易看出特征了。這就是很多信號分析采用FFT變換的原因。

因此對于一個時域信號進行采樣，經FFT運算處理后可以得到該信號的頻譜圖（頻率及對應的幅值），基于頻譜圖我們可以設計特定的濾波器來濾除特定頻率的噪聲，從而讓原信號更加真實的顯示出來。如飛控設計過程中，對陀螺儀/加速度信號進行頻譜分析，濾除機架振動的噪聲頻率，從而可以降低機架振動對姿態解算、飛機控制的影響。

工程應用

編程原理

FFT計算的快速性簡單來講就是數學家利用上面提到的旋轉因子W的周期性，對稱性等性質進行公式化簡。在算法編程中則是不斷利用已經計算過的點來算新的點，即：舊點算新點。

FFT中的采樣序列經拆分抽取成很多的蝶形圖，對于N=8的時間抽取如下：

以上的拆分提取，可以稱之為碼位倒序，倒序獲得的序列便為我們蝶形計算的初始序列，如下圖的左邊一列：

將上圖大的蝴蝶組，拆分想象成一個個的蝴蝶并聯及串聯組成，單個蝴蝶計算如下：

后面的蝴蝶使用前面蝴蝶的計算后的節點，從而舊點算新點，循環計算多層，便可得到最后的頻譜數列。

碼位倒序及蝴蝶圖的編程實現可知乎查找《C語言系列之FFT算法實現》，推導與編程實現講的非常詳細。

結果分析

雖然很多人都知道FFT是什么，可以用來做什么，怎么去做，但是卻不知道FFT之后的結果是什意思、如何決定要使用多少點來做FFT。

由DFT公式可知，使用的輸入值是經過ADC后的采樣值（采樣定理告訴我們，采樣頻率要大于信號頻率的兩倍），輸入采樣點的數量N決定了轉換的計算規模。

N個采樣點，經過FFT之后，就可以得到N個點的FFT結果。為了方便進行FFT運算，通常N取2的整數次方（參見FFT原理）。FFT運算量：Nlog2N（2為對數的底）。

變換后的頻譜輸出包含同樣數量的采樣點N，但是其中有一半的值是冗余的，通常不會顯示在頻譜中，所以真正有用的信息是N/2+1個點（依據采樣定理）。

工程應用分析

假設采樣頻率為Fs，信號頻率F，采樣點數為N。那么FFT之后結果就是一個為N點的復數。每一個點就對應著一個頻率點。這個點的模值，就是該頻率值下的幅度特性。

縱坐標--幅值

假設原始信號的峰值為A，那么FFT的結果的每個點（除了第一個點直流分量之外）的模值就是A的N/2倍。而第一個點就是直流分量，它的模值就是直流分量的N倍。而每個點的相位呢，就是在該頻率下的信號的相位。

橫坐標--頻率

第一個點表示直流分量（即0Hz），而最后一個點N的再下一個點則表示采樣頻率Fs，這中間被N-1個點平均分成N等份，每個點的頻率依次增加。例如某點n所表示的頻率為：Fn=(n-1)*Fs/N。

由上面的公式可以看出，Fn所能分辨到頻率為Fs/N，如果采樣頻率Fs為1024Hz，采樣點數N為1024點，則可以分辨到1Hz。

如果采樣N為2048點，則結果可以分辨到0.5Hz。

如果要提高頻率分辨力，則必須增加 采樣點數 ，也即 采樣時間（總采樣計算周期） 。但這在一些實際的應用中是不現實的，有些需要在較短的時間內完成分析。

舉個栗子

假設我們有一個信號，它含有2V的直流分量，頻率為0.5371Hz、幅度為73V的交流分量，以及一個頻率為1.025Hz、幅度為50V的交流分量。

用數學表達式就是如下：

S=2+73sin(2pi0.5371t)+50sin(2pi1.025t)

我們以50Hz的采樣率對這個信號進行采樣，采樣點N（1024）進行FFT運算。

按照我們上面的分析，Fn=(n-1)*Fs/N，我們可以知道，每兩個

點之間的間距就是50/1024Hz。我們的信號有3個頻率，在頻率點上出現峰值，其它各點應該 接近0（離散點的FT頻譜是連續的，而DFT只是做了連續頻譜的采樣） 。

運算結果如下：