fft算法是什么

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

　　概念

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

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

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

　　如何提高fft算法分辨率

　　FFT程序，輸入是一組復數，輸出也是一組復數，想問一下輸入到底應該輸入什么，輸出的復數的含義是什么。

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

　　首先，fft函數出來的應該是個復數，每一個點分實部虛部兩部分。

　　假設采用1024點fft，采樣頻率是fs，那么第一個點對應0頻率點，第512點對應的就是fs/2的頻率點。　　然后從頭開始找模值最大的那個點，其所對應的頻率值應該就是要的基波頻率了。

　　FFT是離散傅立葉變換的快速算法，可以將一個信號變換到頻域。

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

　　這就是很多信號分析采用FFT變換的原因。

　　另外，FFT可以將一個信號的頻譜提取出來，這在頻譜分析方面也是經常用的。

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

　　一個模擬信號，經過ADC采樣之后，就變成了數字信號。

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

　　采樣得到的數字信號，就可以做FFT變換了。

　　N個采樣點，經過FFT之后，就可以得到N個點的FFT結果。

　　為了方便進行FFT運算，通常N取2的整數次方。