原理簡介
由于計算機技術的快速發展，在70年代中期，美國和日本的一些電子設備企業開始設計和生産數字式傅裡葉分析儀，但是由于離散傅裡葉變換的計算量較大，直到DFT的快速算法(FFT)發現之後，有限離散傅裡葉變換(DFT)才真正獲得了廣泛的應用 [2] 。
FFT是一種DFT的高效算法，稱為快速傅立葉變換（fast Fourier transform）。FFT算法可分為按時間抽取算法和按頻率抽取算法，先簡要介紹FFT的基本原理。從DFT運算開始，說明FFT的基本原理。
DFT的運算為：
式中
由這種方法計算DFT對于X（K）的每個K值，需要進行4N次實數相乘和（4N-2）次相加，對于N個k值，共需N*N乘和N（4N-2）次實數相加。改進DFT算法，減小它的運算量，利用DFT中 的周期性和對稱性，使整個DFT的計算變成一系列叠代運算，可大幅度提高運算過程和運算量，這就是FFT的基本思想。
分類
FFT基本上可分為兩類，時間抽取法和頻率抽取法，而一般的時間抽取法和頻率抽取法隻能處理長度N=2M的情況，另外還有組合數基四FFT來處理一般長度的FFT。
所謂抽選，就是把長序列分為短序列的過程，可在時域也可在頻域進行。最常用的時域抽選方法是按奇偶将長序列不斷地變為短序列，結果使輸入序列為倒序，輸出序列為順序排列，這就是Coolly—Tukey算法。
時間抽取
設N點序列x(n), ,将x(n)按奇偶分組，公式如圖2所示：
改寫為：
一個N點DFT分解為兩個 N/2點的DFT，
和
繼續分解，叠代下去，其運算量約為
其算法有如下規律：
兩個4點組成的8點DFT：
四個2點組成的8點DFT：
按時間抽取的8點DFT：
原位計算
當數據輸入到存儲器中以後，每一級運算的結果仍然儲存在同一組存儲器中，直到最後輸出，中間無需其它存儲器。
序數重排
對按時間抽取FFT的原位運算結構，當運算完畢時，這種結構存儲單元A(1)、A(2)，…，A(8)中正好順序存放着X(0)，X(1)，X(2)，…，X(7)，因此可直接按順序輸出，但這種原位運算的輸入x(n)卻不能按這種自然順序存入存儲單元中，而是按X(0)，X(4)，X(2)，X(6)，…，X(7)的順序存入存儲單元，這種順序看起來相當雜亂，然而它也是有規律的。當用二進制表示這個順序時，它正好是“碼位倒置”的順序。
蝶形類型随叠代次數成倍增加。
每次叠代的蝶形類型比上一次蝶代增加一倍，數據點間隔也增大一倍。
頻率抽取
頻率抽取2FFT算法是按頻率進行抽取的算法。
設N=2M，将x(n)按前後兩部分進行分解，
按K的奇偶分為兩組，即
得到兩個N/2 點的DFT運算。如此分解，并叠代，總的計算量和時間抽取（DIT）基2FFT算法相同。
算法規律如下：
蝶形結構和時間抽取不一樣但是蝶形個數一樣，同樣具有原位計算規律，其叠代次數成倍減小。
組合數基四FFT
N≠2M時，可采取補零使其成為N=2，或者先分解為兩個p、q的序列，其中p*q=N，然後進行計算。
Chirp-z變換
前面介紹，采用FFT算法可以很快算出全部N點DFT值，即z變換X（z）在z平面單位圓上的全部等間隔取樣值。實際中也許①不需要計算整個單位圓上z變換的取樣，如對于窄帶信号，隻需要對信号所在的一段頻帶進行分析，這時希望頻譜的采樣集中在這一頻帶内，以獲得較高的分辨率，而頻帶以外的部分可不考慮，②或者對其它圍線上的z變換取樣感興趣，例如語音信号處理中，需要知道z變換的極點所在頻率，如極點位置離單位圓較遠，則其單位圓上的頻譜就很平滑，這時很難從中識别出極點所在的頻率，如果采樣不是沿單位圓而是沿一條接近這些極點的弧線進行，則在極點所在頻率上的頻譜将出現明顯的尖峰，由此可較準确地測定極點頻率。③或者要求能有效地計算當N是素數時序列的DFT，因此提高DFT計算的靈活性非常有意義。
螺旋線采樣是一種适合于這種需要的變換，且可以采用FFT來快速計算，這種變換也稱作Chirp-z變換。
應用
FFT計算IDFT
DFT變換則說明對于時間有限的信号（有限長序列），也可以對其進行頻域采樣，而不丢失任何信息。所以隻要時間序列足夠長，采樣足夠密，頻域采樣也就可較好地反映信号的頻譜趨勢，所以FFT可以用以進行連續信号的頻譜分析。
當然，這裡作了幾次近似處理：
1、用離散采樣信号的傅立葉變換來代替連續信号的頻譜，隻有在嚴格滿足采樣定理的前提下，頻譜才不會有畸變，否則隻是近似；
2、用有限長序列來代替無限長離散采樣信号。
FFT計算線性卷積
線性卷積是求離散系統響應的主要方法之一,許多重要應用都建立在這一理論基礎上,如卷積濾波等。
以前曾讨論了用圓周卷積計算線性卷積的方法歸納如下:
将長為N2的序列x(n)延長到L,補L-N2個零
将長為N1的序列h(n)延長到L,補L-N1個零
如果L≥N1+N2-1,則圓周卷積與線性卷積相等，此時，可有FFT計算線性卷積，方法如下:
a.計算X(k)=FFT[x(n)]
b.求H(k)=FFT[h(n)]
c.求Y(k)=H(k)Y(k) k=0～L-1
d.求y(n)=IFFT[Y(k)] n=0～L-1
可見，隻要進行二次FFT,一次IFFT就可完成線性卷積計算。計算表明,L>32時,上述計算線性卷積的方法比直接計算線卷積有明顯的優越性,因此,也稱上述圓周卷積方法為快速卷積法
FFT計算相關函數
互相關和自相關函數的計算可利用FFT實現。由于離散付裡葉變換隐含着周期性，所以用FFT計算離散相關函數也是對周期序列而言的。直接做N點FFT相當于對兩個N點序列x(n)、y(n)作周期延拓，作相關後再取主值（類似圓周卷積）。而實際一般要求的是兩個有限長序列的線性相關，為避免混淆，需采用與圓周卷積求線性卷積相類似的方法，先将序列延長補0後再用上述方法。
實數序列FFT
信号是實數序列，任何實數都可看成虛部為零的複數，例如，求某實信号y(n)的複譜,可認為是将實信号加上數值為零的虛部變成複信号(x(n)+j0)，再用FFT求其離散付裡葉變換。這種作法很不經濟，因為把實序列變成複序列，存儲器要增加一倍，且計算機運行時，即使虛部為零，也要進行涉及虛部的運算，浪費了運算量。合理的解決方法是利用複數據FFT對實數據進行有效計算，下面介紹方法。
一個N點FFT同時計算兩個N點實序列的DFT
設x1(n)，x2(n)是彼此獨立的兩個N點實序列,且X1(k)=DFT[x1(n)]，X2(k)=DFT[x2(n)]
可通過一次FFT運算同時獲得X1(k)，X2(k)。算法如下：
首先将x1(n)，x2(n)分别當作一複序列的實部及虛部,令
x(n)=x1(n)+jx2(n)
通過FFT運算可獲得x(n)的DFT值 X(k)=DFT[x1(n)]+jDFT[x2(n)]=X1(k)+jX2(k)
利用離散付裡葉變換的共轭對稱性
X1(K)=1/2*[X(k)+[X(N-k)共轭]]
X2(K)=1/2*[X(k)-[X(N-k)共轭]]
有了x(n)的FFT運算結果X(k),由上式即可得到X1(k),X2(k)的值。
