FFT--快速傅里葉變換

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

理論介紹 & 工程應(yīng)用

理論介紹

1

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

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

2

快速傅里葉變換

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

FFT是基于DFT的一種算法，目的是為了加快DFT的計(jì)算速度。當(dāng)采樣點(diǎn)N=65536=2^16，DFT的計(jì)算量約是FFT的4096倍。

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

3

物理意義

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

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

工程應(yīng)用

編程原理

FFT計(jì)算的快速性簡單來講就是數(shù)學(xué)家利用上面提到的旋轉(zhuǎn)因子W的周期性，對(duì)稱性等性質(zhì)進(jìn)行公式化簡。在算法編程中則是不斷利用已經(jīng)計(jì)算過的點(diǎn)來算新的點(diǎn)，即：舊點(diǎn)算新點(diǎn)。

FFT中的采樣序列經(jīng)拆分抽取成很多的蝶形圖，對(duì)于N=8的時(shí)間抽取如下：

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

將上圖大的蝴蝶組，拆分想象成一個(gè)個(gè)的蝴蝶并聯(lián)及串聯(lián)組成，單個(gè)蝴蝶計(jì)算如下：

后面的蝴蝶使用前面蝴蝶的計(jì)算后的節(jié)點(diǎn)，從而舊點(diǎn)算新點(diǎn)，循環(huán)計(jì)算多層，便可得到最后的頻譜數(shù)列。

碼位倒序及蝴蝶圖的編程實(shí)現(xiàn)可知乎查找《C語言系列之FFT算法實(shí)現(xiàn)》，推導(dǎo)與編程實(shí)現(xiàn)講的非常詳細(xì)。

結(jié)果分析

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

由DFT公式可知，使用的輸入值是經(jīng)過ADC后的采樣值（采樣定理告訴我們，采樣頻率要大于信號(hào)頻率的兩倍），輸入采樣點(diǎn)的數(shù)量N決定了轉(zhuǎn)換的計(jì)算規(guī)模。

N個(gè)采樣點(diǎn)，經(jīng)過FFT之后，就可以得到N個(gè)點(diǎn)的FFT結(jié)果。為了方便進(jìn)行FFT運(yùn)算，通常N取2的整數(shù)次方（參見FFT原理）。FFT運(yùn)算量：Nlog2N（2為對(duì)數(shù)的底）。

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

工程應(yīng)用分析

假設(shè)采樣頻率為Fs，信號(hào)頻率F，采樣點(diǎn)數(shù)為N。那么FFT之后結(jié)果就是一個(gè)為N點(diǎn)的復(fù)數(shù)。每一個(gè)點(diǎn)就對(duì)應(yīng)著一個(gè)頻率點(diǎn)。這個(gè)點(diǎn)的模值，就是該頻率值下的幅度特性。

縱坐標(biāo)--幅值

假設(shè)原始信號(hào)的峰值為A，那么FFT的結(jié)果的每個(gè)點(diǎn)（除了第一個(gè)點(diǎn)直流分量之外）的模值就是A的N/2倍。而第一個(gè)點(diǎn)就是直流分量，它的模值就是直流分量的N倍。而每個(gè)點(diǎn)的相位呢，就是在該頻率下的信號(hào)的相位。

橫坐標(biāo)--頻率

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

由上面的公式可以看出，F(xiàn)n所能分辨到頻率為Fs/N，如果采樣頻率Fs為1024Hz，采樣點(diǎn)數(shù)N為1024點(diǎn)，則可以分辨到1Hz。

如果采樣N為2048點(diǎn)，則結(jié)果可以分辨到0.5Hz。

如果要提高頻率分辨力，則必須增加 采樣點(diǎn)數(shù) ，也即 采樣時(shí)間（總采樣計(jì)算周期） 。但這在一些實(shí)際的應(yīng)用中是不現(xiàn)實(shí)的，有些需要在較短的時(shí)間內(nèi)完成分析。

舉個(gè)栗子

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

用數(shù)學(xué)表達(dá)式就是如下：

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

我們以50Hz的采樣率對(duì)這個(gè)信號(hào)進(jìn)行采樣，采樣點(diǎn)N（1024）進(jìn)行FFT運(yùn)算。

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

點(diǎn)之間的間距就是50/1024Hz。我們的信號(hào)有3個(gè)頻率，在頻率點(diǎn)上出現(xiàn)峰值，其它各點(diǎn)應(yīng)該 接近0（離散點(diǎn)的FT頻譜是連續(xù)的，而DFT只是做了連續(xù)頻譜的采樣） 。

運(yùn)算結(jié)果如下：