FFT---快速傅裡葉變換
基于離散傅立葉變換(DFT)，以擷取信号的頻域特征。傳統的DFT算法能夠擷取信号頻域特征，但是算法計算量大，耗時長，不利于計算機實時對信号進行處理，在工程中無法應用，作為DFT的一種快速實作算法，FFT很好的解決了這個問題。
DFT變換公式，由此公式，每計算一個頻率點X(k)均需要進行N次複數乘法和N-1次複數加法，計算N各點的X(k)共需要N^2次複數乘法和N*(N-1)次複數加法。當x(n)為實數的情況下，計算N點的DFT需要2*N^2次實數乘法，2*N*(N-1)次實數加法。計算量很大
正所謂“有需求就會有市場”，前人偉大的智慧，給出了一下幾種解決方法
1.基-2 FFT ---DFT點數為N = 2^M(M為整數)時的FFT，可以分為兩類：按時間抽取法（DIT-FFT）和按頻率抽取法FFT（DIF-FFT）
DIT-FFT
把長為N = 2^M點的時域序列x(n)按序号的奇偶逐級分解，最終得到N/2個2點時域序列。通過疊代計算2點的DFT，使DFT計算量減少（假設采樣序列點數為N=2^L，L為整數，如果不滿足這個條件可以人為地添加若幹個0以使采樣序列點數滿足這一要求）
X'(k’)為偶數項分支的離散傅立葉變換，X''(k’’)為奇數項分支的離散傅立葉變換，對于N點的FFT計算需要總共的實數乘法數量為：2×N×log2(N)；總的複數加法次數為：2xNxlog2(N)。
快速計算方法的流程：1.對于輸入資料序列進行倒位序變換。2.蝶形運算的循環結構。 3.浮點到定點轉換需要注意的關鍵問題 4.計算過程中的溢出問題