上一回說到，為了節(jié)省電腦的計(jì)算時(shí)間，實(shí)現(xiàn)數(shù)字信號的實(shí)時(shí)處理，科學(xué)界千方百計(jì)減少離散傅里葉變換（DFT）的計(jì)算量。
1965年，庫利（T.W.Cooley）和圖基（J.W.Tukey）發(fā)表《一個(gè)復(fù)數(shù)傅立葉級數(shù)之機(jī)械計(jì)算算法》論文，首次提出了DFT運(yùn)算的一種快速算法。此后科學(xué)界創(chuàng)造出了各種各樣的DFT快速算法，逐漸發(fā)展完善形成了一整套行之有效的算法設(shè)計(jì)思想和方法。這就是快速傅立葉變換（Fast Fouier Transform），簡稱FFT。
可見所謂的快速傅里葉變換（FFT），并不是一種新的傅立葉分析理論，而是減少DFT計(jì)算量的算法設(shè)計(jì)思想和DFT各種快速算法的統(tǒng)稱。
上一回我們知道了：DFT的計(jì)算量與點(diǎn)數(shù)N的平方成正比。DFT的變換因子（也叫旋轉(zhuǎn)因子）：
（1）
具有周期性和對稱性。也就是說：
1、以N為周期，即：
（2）
2、復(fù)共軛對稱性（關(guān)于實(shí)軸對稱），即：
（3）
3、中心對稱性（關(guān)于原點(diǎn)對稱），即：
（4）
FFT算法設(shè)計(jì)的基本思想，就是充分利用DFT的周期性和對稱性，減少重復(fù)的計(jì)算量；并把N點(diǎn)長序列分成幾個(gè)短序列，減少每個(gè)序列長度，可大大減少計(jì)算量。
實(shí)踐中使用最多的FFT是“基2”算法。所謂“基2”，就是令DFT的點(diǎn)數(shù)N滿足
（5）
FFT基2算法分為時(shí)域抽取法（Decimation In Time）和頻域抽取法（Decimation In Frequency）兩大類。本文重點(diǎn)介紹其中的時(shí)域抽取法快速傅里葉變換（DIT－FFT），算法設(shè)計(jì)思想要點(diǎn)如下：
1、把長度為N的時(shí)域序列x（n）按n的奇偶分為兩組，變成兩個(gè)序列，長度均為N/2。即
（6）
其中一個(gè)N/2點(diǎn)的DFT為
（7）
另一個(gè)N/2點(diǎn)的DFT為
（8）
2、不難推出原序列x（n）的N/2點(diǎn)DFT為
（9）
注意：上式僅是X（k）的前一半即N/2點(diǎn)運(yùn)算，整個(gè)N點(diǎn)DFT結(jié)果還要加上后一半計(jì)算。如果老老實(shí)實(shí)計(jì)算后一半N/2點(diǎn)DFT，則并沒有減少任何計(jì)算量。
但考慮可利用DFT及其變換因子的周期性和對稱性，并利用前一半計(jì)算結(jié)果，后一半計(jì)算可表示為
（10）
這種“一分為二”的DFT算法叫做蝶形運(yùn)算。可以看出其計(jì)算量為
（11）
和
（12）
與普通的DFT相比，計(jì)算量減少了一半！
3、同理，如果把式（6）表示的時(shí)間序列“二分為四”，長度均為N/4，同時(shí)把式（9）、（10）中的N/2點(diǎn)DFT分解為N/4點(diǎn)的DFT，反復(fù)使用蝶形運(yùn)算的方法，即
（13）
后一半DFT為
（14）
而
（15）
后一半DFT為
（16）
計(jì)算量可在式（11）和（12）的基礎(chǔ)上再減少一半!
4、依此類推，直到把長度為N的序列細(xì)分成N/2個(gè)2點(diǎn)序列為止，循環(huán)使用蝶形運(yùn)算的方法，即把N點(diǎn)DFT分解成N/2個(gè)2點(diǎn)DFT運(yùn)算。這樣，計(jì)算量大大減少。由式（5）知
（17）
則復(fù)數(shù)乘法總次數(shù)從原來的N2減少為：
（18）
復(fù)數(shù)加法總次數(shù)從原來的約N2減少為：
（19）
假設(shè)N=1024，復(fù)數(shù)乘法從原來直接DFT計(jì)算的104萬次，減少為5120次，計(jì)算速度提高約200倍！
綜上所述，快速傅里葉變換（FFT）大大降低了數(shù)字信號處理中的運(yùn)算量，它的價(jià)值在于節(jié)省了CPU的處理時(shí)間，使得更多更復(fù)雜的數(shù)字信號得以快速的處理，為實(shí)現(xiàn)信息的實(shí)時(shí)處理開辟了廣闊的發(fā)展前景。因此，F(xiàn)FT是數(shù)字信號處理技術(shù)發(fā)展史上的一個(gè)重要里程碑。
作為其快速算法設(shè)計(jì)思想精髓的典型代表，基2算法的時(shí)域抽取法快速傅里葉變換（DIT－FFT）中的蝶形運(yùn)算式（9）、（10）和（13）、（14）、（15）、（16）等公式，被英國科學(xué)期刊《物理世界》2004年10月號公布為讀者選出的“科學(xué)界歷來最偉大的公式”之一，并且名列第九。
同期推選出的“科學(xué)界歷來最偉大的公式”還有許多，有興趣的朋友們請查閱周法哲的博文《科學(xué)的皇后》欄目。
（作者：周法哲2009-8-9于廣東）
