上一回說到，為了節(jié)省電腦的計算時間，實現(xiàn)數(shù)字信號的實時處理，科學界千方百計減少離散傅里葉變換（DFT）的計算量。

1965年，庫利（T.W.Cooley）和圖基（J.W.Tukey）發(fā)表《一個復數(shù)傅立葉級數(shù)之機械計算算法》論文，首次提出了DFT運算的一種快速算法。此后科學界創(chuàng)造出了各種各樣的DFT快速算法，逐漸發(fā)展完善形成了一整套行之有效的算法設計思想和方法。這就是快速傅立葉變換（Fast Fouier Transform），簡稱FFT。

可見所謂的快速傅里葉變換（FFT），并不是一種新的傅立葉分析理論，而是減少DFT計算量的算法設計思想和DFT各種快速算法的統(tǒng)稱。

上一回我們知道了：DFT的計算量與點數(shù)N的平方成正比。DFT的變換因子（也叫旋轉(zhuǎn)因子）：

（1）

具有周期性和對稱性。也就是說：

1、以N為周期，即：

（2）

2、復共軛對稱性（關于實軸對稱），即：

（3）

3、中心對稱性（關于原點對稱），即：

（4）

FFT算法設計的基本思想，就是充分利用DFT的周期性和對稱性，減少重復的計算量；并把N點長序列分成幾個短序列，減少每個序列長度，可大大減少計算量。

實踐中使用最多的FFT是“基2”算法。所謂“基2”，就是令DFT的點數(shù)N滿足

（5）

FFT基2算法分為時域抽取法（Decimation In Time）和頻域抽取法（Decimation In Frequency）兩大類。本文重點介紹其中的時域抽取法快速傅里葉變換（DIT－FFT），算法設計思想要點如下：

1、把長度為N的時域序列x（n）按n的奇偶分為兩組，變成兩個序列，長度均為N/2。即

（6）

其中一個N/2點的DFT為

（7）

另一個N/2點的DFT為

（8）

2、不難推出原序列x（n）的N/2點DFT為

（9）

注意：上式僅是X（k）的前一半即N/2點運算，整個N點DFT結(jié)果還要加上后一半計算。如果老老實實計算后一半N/2點DFT，則并沒有減少任何計算量。

但考慮可利用DFT及其變換因子的周期性和對稱性，并利用前一半計算結(jié)果，后一半計算可表示為

（10）

這種“一分為二”的DFT算法叫做蝶形運算。可以看出其計算量為

（11）

和

（12）

與普通的DFT相比，計算量減少了一半！

3、同理，如果把式（6）表示的時間序列“二分為四”，長度均為N/4，同時把式（9）、（10）中的N/2點DFT分解為N/4點的DFT，反復使用蝶形運算的方法，即

（13）

后一半DFT為

（14）

而

（15）

后一半DFT為

（16）

計算量可在式（11）和（12）的基礎上再減少一半!

4、依此類推，直到把長度為N的序列細分成N/2個2點序列為止，循環(huán)使用蝶形運算的方法，即把N點DFT分解成N/2個2點DFT運算。這樣，計算量大大減少。由式（5）知

（17）

則復數(shù)乘法總次數(shù)從原來的N2減少為：

（18）

復數(shù)加法總次數(shù)從原來的約N2減少為：

（19）

假設N=1024，復數(shù)乘法從原來直接DFT計算的104萬次，減少為5120次，計算速度提高約200倍！

綜上所述，快速傅里葉變換（FFT）大大降低了數(shù)字信號處理中的運算量，它的價值在于節(jié)省了CPU的處理時間，使得更多更復雜的數(shù)字信號得以快速的處理，為實現(xiàn)信息的實時處理開辟了廣闊的發(fā)展前景。因此，F(xiàn)FT是數(shù)字信號處理技術發(fā)展史上的一個重要里程碑。

作為其快速算法設計思想精髓的典型代表，基2算法的時域抽取法快速傅里葉變換（DIT－FFT）中的蝶形運算式（9）、（10）和（13）、（14）、（15）、（16）等公式，被英國科學期刊《物理世界》2004年10月號公布為讀者選出的“科學界歷來最偉大的公式”之一，并且名列第九。

同期推選出的“科學界歷來最偉大的公式”還有許多，有興趣的朋友們請查閱周法哲的博文《科學的皇后》欄目。

（作者：周法哲2009-8-9于廣東）