fft算法是什么

　　FFT算法（fast Fourier transform），即快速傅里葉變換，是指利用計(jì)算機(jī)計(jì)算離散傅里葉變換（DFT）的高效、快速計(jì)算方法的統(tǒng)稱，簡(jiǎn)稱FFT。快速傅里葉變換是1965年由J.W.庫(kù)利和T.W.圖基提出的。采用這種算法能使計(jì)算機(jī)計(jì)算離散傅里葉變換所需要的乘法次數(shù)大為減少，特別是被變換的抽樣點(diǎn)數(shù)N越多，F(xiàn)FT算法計(jì)算量的節(jié)省就越顯著。

　　概念

　　有限長(zhǎng)序列可以通過(guò)離散傅里葉變換（DFT）將其頻域也離散化成有限長(zhǎng)序列。但其計(jì)算量太大，很難實(shí)時(shí)地處理問(wèn)題，因此引出了快速傅里葉變換（FFT）。 1965年，Cooley和Tukey提出了計(jì)算離散傅里葉變換（DFT）的快速算法，將DFT的運(yùn)算量減少了幾個(gè)數(shù)量級(jí)。從此，對(duì)快速傅里葉變換（FFT）算法的研究便不斷深入，數(shù)字信號(hào)處理這門新興學(xué)科也隨FFT的出現(xiàn)和發(fā)展而迅速發(fā)展。根據(jù)對(duì)序列分解與選取方法的不同而產(chǎn)生了FFT的多種算法，基本算法是基2DIT和基2DIF。FFT在離散傅里葉反變換、線性卷積和線性相關(guān)等方面也有重要應(yīng)用。

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

　　設(shè)x（n）為N項(xiàng)的復(fù)數(shù)序列，由DFT變換，任一X（m）的計(jì)算都需要N次復(fù)數(shù)乘法和N-1次復(fù)數(shù)加法，而一次復(fù)數(shù)乘法等于四次實(shí)數(shù)乘法和兩次實(shí)數(shù)加法，一次復(fù)數(shù)加法等于兩次實(shí)數(shù)加法，即使把一次復(fù)數(shù)乘法和一次復(fù)數(shù)加法定義成一次“運(yùn)算”（四次實(shí)數(shù)乘法和四次實(shí)數(shù)加法），那么求出N項(xiàng)復(fù)數(shù)序列的X（m），即N點(diǎn)DFT變換大約就需要N^2次運(yùn)算。當(dāng)N=1024點(diǎn)甚至更多的時(shí)候，需要N2=1048576次運(yùn)算，在FFT中，利用WN的周期性和對(duì)稱性，把一個(gè)N項(xiàng)序列（設(shè)N=2k，k為正整數(shù)），分為兩個(gè)N/2項(xiàng)的子序列，每個(gè)N/2點(diǎn)DFT變換需要（N/2）^2次運(yùn)算，再用N次運(yùn)算把兩個(gè)N/2點(diǎn)的DFT變換組合成一個(gè)N點(diǎn)的DFT變換。這樣變換以后，總的運(yùn)算次數(shù)就變成N+2*（N/2）^2=N+N^2/2。繼續(xù)上面的例子，N=1024時(shí)，總的運(yùn)算次數(shù)就變成了525312次，節(jié)省了大約50%的運(yùn)算量。而如果我們將這種“一分為二”的思想不斷進(jìn)行下去，直到分成兩兩一組的DFT運(yùn)算單元，那么N點(diǎn)的DFT變換就只需要Nlog2N次的運(yùn)算，N在1024點(diǎn)時(shí)，運(yùn)算量?jī)H有10240次，是先前的直接算法的1%，點(diǎn)數(shù)越多，運(yùn)算量的節(jié)約就越大，這就是FFT的優(yōu)越性。

　　如何提高fft算法分辨率

　　FFT程序，輸入是一組復(fù)數(shù)，輸出也是一組復(fù)數(shù)，想問(wèn)一下輸入到底應(yīng)該輸入什么，輸出的復(fù)數(shù)的含義是什么。

　　給定一組序列的抽樣值，如何用FFT確定它的頻率。

　　首先，fft函數(shù)出來(lái)的應(yīng)該是個(gè)復(fù)數(shù)，每一個(gè)點(diǎn)分實(shí)部虛部?jī)刹糠帧?/p>

　　假設(shè)采用1024點(diǎn)fft，采樣頻率是fs，那么第一個(gè)點(diǎn)對(duì)應(yīng)0頻率點(diǎn)，第512點(diǎn)對(duì)應(yīng)的就是fs/2的頻率點(diǎn)。　　然后從頭開(kāi)始找模值最大的那個(gè)點(diǎn)，其所對(duì)應(yīng)的頻率值應(yīng)該就是要的基波頻率了。

　　FFT是離散傅立葉變換的快速算法，可以將一個(gè)信號(hào)變換到頻域。

　　有些信號(hào)在時(shí)域上是很難看出什么特征的，但是如果變換到頻域之后，就很容易看出特征了。

　　這就是很多信號(hào)分析采用FFT變換的原因。

　　另外，F(xiàn)FT可以將一個(gè)信號(hào)的頻譜提取出來(lái)，這在頻譜分析方面也是經(jīng)常用的。

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

　　一個(gè)模擬信號(hào)，經(jīng)過(guò)ADC采樣之后，就變成了數(shù)字信號(hào)。

　　采樣定理告訴，采樣頻率要大于信號(hào)頻率的兩倍，這些就不在此羅嗦了。

　　采樣得到的數(shù)字信號(hào)，就可以做FFT變換了。

　　N個(gè)采樣點(diǎn)，經(jīng)過(guò)FFT之后，就可以得到N個(gè)點(diǎn)的FFT結(jié)果。

　　為了方便進(jìn)行FFT運(yùn)算，通常N取2的整數(shù)次方。