設x（N）為N點有限長離散序列，代入式（8－3）、式（8－4），並令 其傅裏葉變換（DFT）為
地球物理數據處理基礎
反變換（IDFT）為
地球物理數據處理基礎
兩者的差異只在於W的指數符號不同，以及差壹個常數1/N，因此下面我們只討論DFT正變換式（8－5）的運算量，其反變換式（8－6）的運算是完全相同的。
壹般來說，W是復數，因此，X（j）也是復數，對於式（8－5）的傅裏葉變換（DFT），計算壹個X（j）值需要N次復數乘法和N－1次復數加法。而X（j）壹***有N個值（j＝0，1，…，N－1），所以完成整個DFT運算總***需要N2次復數乘法和N（N－1）次復數加法。
直接計算DFT，乘法次數和加法次數都是與N2成正比的，當N很大時，運算量會很大，例如，當N＝8時，DFT需64次復數乘法；而當N＝1024時，DFT所需乘法為1048576次，即壹百多萬次的復數乘法運算，對運算速度要求高。所以需要改進DFT的計算方法，以減少運算次數。
分析Wjk，表面上有N2個數值，由於其周期性，實際上僅有N個不同的值W0，W1，…，WN－1。對於N＝2m時，由於其對稱性，只有N/2個不同的值W0，W1，…，
地球物理數據處理基礎
因此可以把長序列的DFT分解為短序列DFT，而前面已經分析DFT與N2成正比，所以N越小越有利。同時，利用ab＋ac＝a（b＋c）結合律法則，可以將同壹個Wr對應的系數x（k）相加後再乘以Wr，就能大大減少運算次數。這就是快速傅裏葉變換（FFT）的算法思路。下面，我們來分析N＝2m情況下的FFT算法。
1.N＝4的FFT算法
對於m＝2，N＝4，式（8－5）傅裏葉變換為
地球物理數據處理基礎
將式（8－7）寫成矩陣形式
地球物理數據處理基礎
為了便於分析，將上式中的j，k寫成二進制形式，即
地球物理數據處理基礎
代入式（8－7），得
地球物理數據處理基礎
分析Wjk的周期性來減少乘法次數
地球物理數據處理基礎
則 代回式（8－9），整理得
地球物理數據處理基礎
上式可分層計算，先計算內層，再計算外層時就利用內層計算的結果，可避免重復計算。寫成分層形式
地球物理數據處理基礎
則X（j1 j0）＝X2（j1 j0）。
上式表明對於N＝4的FFT，利用Wr的周期關系可分為m＝2步計算。實際上，利用Wr的對稱性，仍可以對式（8－11）進行簡化計算。考慮到
地球物理數據處理基礎
式（8－11）可以簡化為
地球物理數據處理基礎
令j＝j0；k＝k0，並把上式表示為十進制，得
地球物理數據處理基礎
可以看到，完成上式N＝4的FFT計算（表8－1）需要N·（m－1）/2＝2次復數乘法和N·m＝8次復數加法，比N＝4的DFT算法的N2＝16次復數乘法和N·（N－1）＝12次復數加法要少得多。
表8－1 N＝4的FFT算法計算過程
註：W0＝1；W1＝－i。
［例1］求N＝4樣本序列1，3，3，1的頻譜（表8－2）。
表8－2 N＝4樣本序列
2.N＝8的FFT算法
類似N＝4的情況，用二進制形式表示，有
地球物理數據處理基礎
寫成分層計算的形式：
地球物理數據處理基礎
則X（j2 j1 j0）＝X3（j2 j1 j0）。
對式（8－14）的X1（k1 k0 j0）進行展開，有
地球物理數據處理基礎
還原成十進制，並令k＝2k1＋k0，即k＝0，1，2，3，有
地球物理數據處理基礎
用類似的方法對式（8－14）的X2（k0 j1 j0），X3（j2 j1 j0）進行展開，整理得
地球物理數據處理基礎
用式（8－16）、式（8－17）逐次計算到X3（j）＝X（j）（j＝0，1，…，7），即完成N＝23＝8的FFT計算，其詳細過程見表8－3。
表8－3 N＝8的FFT算法計算過程
註：對於正變換 對於反變換 所
［例2］求N＝8樣本序列（表8－4）x（k）＝1，2，1，1，3，2，1，2的頻譜。
表8－4 N＝8樣本序列
3.任意N＝2m的FFT算法
列出N＝4，N＝8的FFT計算公式，進行對比
地球物理數據處理基礎
觀察式（8－18）、式（8－19），不難看出，遵循如下規律：
（1）等式左邊的下標由1遞增到m，可用q＝1，2，…，m代替，則等式右邊為q－1；
（2）k的上限為奇數且隨q的增大而減小，至q＝m時為0，所以其取值範圍為k＝0，1，2，…，（2m－q－1）；
（3）j的上限為奇數且隨q的增大而增大，且q＝1時為0，其取值範圍為j＝0，1，2，…，（2q－1－1）；
（4）k的系數，在等式左邊為2q，等式右邊為2q－1（包括W的冪指數）；
（5）等式左邊序號中的常數是2的乘方形式，且冪指數比下標q小1，即2q－1；等式右邊m對式子序號中的常數都是定值2m－1。
歸納上述規則，寫出對於任意正整數m，N＝2m的FFT算法如下：
由X0（p）＝x（p）（p＝0，1，…，N－1）開始：
（1）對q＝1，2，…，m，執行（2）～（3）步；
（2）對k＝0，1，2，…，（2m－q－1）及j＝0，1，2，…，（2q－1－1），執行
地球物理數據處理基礎
（3）j，k循環結束；
（4）q循環結束；由Xm（p）（p＝0，1，…，N－1）輸出原始序列x（p）的頻譜X（p）。
在計算機上很容易實現上述FFT算法程序，僅需要三個復數數組，編程步驟如下：
（1）設置復數數組X1（N－1），X2（N－1）和 （數組下界都從0開始）；
（2）把樣本序列x賦給X1，即X1（k）＝x（k）（k＝0，1，…，N－1）；
（3）計算W，即正變換 反變換
（4）q＝1，2，…，m，若q為偶數，執行（6），否則執行第（5）步；
（5）k＝0，1，2，…，（2m－q－1）和j＝0，1，2，…，（2q－1－1）循環，作
X2（2qk＋j）＝X1（2q－1k＋j）＋X1（2q－1k＋j＋2m－1）
X2（2qk＋j＋2q－1）＝［X1（2q－1k＋j）－X1（2q－1k＋j＋2m－1）］W（2q－1k）
至k，j循環結束；
（6）k＝0，1，2，…，（2m－q－1）和j＝0，1，2，…，（2q－1－1）循環，作
X1（2qk＋j）＝X2（2q－1k＋j）＋X2（2q－1k＋j＋2m－1）
X1（2qk＋j＋2q－1）＝［X2（2q－1k＋j）－X2（2q－1k＋j＋2m－1）］W（2q－1k）
至k，j循環結束；
（7）q循環結束，若m為偶數，輸出X1（j），否則輸出X2（j）（j＝0，1，…，N－1），即為所求。