本文對離散信號的頻域分析（共5節）中的第4節——快速傅里葉變換FFT（Fast- Fourier Transform）進(jìn)行串講。
首先大家需要知道的是，FFT并不是一種新的變換，它僅僅是作為DFT的快速算法。本節包括下列內容：
4.1 改進(jìn)DFT計算的方法
1. DFT計算量分析
觀(guān)察正變換和反變換的公式可知，二者的運算方式和運算量是完全相同的。下面的分析均以DFT正變換為例。（順便說(shuō)一句，大家要像熟悉自己的手機一樣熟悉旋轉因子，閉著(zhù)眼睛都知道它）
觀(guān)察DFT正變換的公式，容易看出：每計算一個(gè)點(diǎn)的數據，需要N次復數乘法、N-1次復數加法，所以，N點(diǎn)DFT，需要N的平方次復數乘法，N(N-1)次復數加法。我們知道，DFT的點(diǎn)數，至少要取成序列的長(cháng)度，當序列長(cháng)度很長(cháng)時(shí)，運算量巨大！如下圖所示。
以1024點(diǎn)為例，復數乘法的次數100萬(wàn)次之多。
1965年，庫利（J.W.Cooley）和圖基（J.W.Tukey）在《Mathmatics of Computation》上發(fā)表了《AnAlgorithm for the Machine Calculation of Complex Fourier Series》，提出一種高效DFT運算的快速算法，后人稱(chēng)為快速傅里葉變換（Fast Fourier Transform ——FFT）。
2. 改進(jìn)DFT計算效率的基本途徑
N點(diǎn)DFT，直接計算，需要N的平方次乘法；分成2個(gè)N/2點(diǎn)DFT分別計算，乘法的次數是1/2的N的平方，減少了一半；分成4個(gè)N/4點(diǎn)DFT，乘法的次數又減少了一半。如果能夠繼續下去，前景很讓人向往。
為了能夠一直分下去，我們限定N為2的整數次冪，即：N=2^M，稱(chēng)為基2FFT。
由此可見(jiàn)，FFT的基本思想是：把長(cháng)序列分成幾個(gè)較短的序列。
但怎么分？不能隨便亂分，基本原則是：要保證這幾個(gè)短序列的DFT組合起來(lái)后，能夠很方便地構成原來(lái)長(cháng)序列的DFT。
所以，DFT快速算法要解決的兩個(gè)核心問(wèn)題是：怎么分？怎么合？
根據分與合的方式不同，有兩種基2FFT算法，分別稱(chēng)為：
按時(shí)間抽取的FFT算法——Decimation-in-Time，簡(jiǎn)稱(chēng)DIT-FFT。
按頻率抽取的FFT算法——Decimation-in-Frequency，簡(jiǎn)稱(chēng)DIF-FFT。
下面我們分別來(lái)歸納總結兩種基2FFT算法。
4.2 兩種基2FFT算法
1. 按時(shí)間抽?。―IT）FFT算法
以第一次分解（N點(diǎn)分為2個(gè)N/2點(diǎn)）為例來(lái)說(shuō)明算法原理。
首先解決怎么分的問(wèn)題。
通俗地說(shuō)，就是：大家列隊、報數（從0開(kāi)始）。報偶數的一組，奇數的一組。
然后解決怎么合的問(wèn)題。
我們略過(guò)看似艱苦卓絕實(shí)際很簡(jiǎn)單的推導過(guò)程，直接上結論：
公式不好看，有人畫(huà)了一幅圖，并且起了個(gè)好聽(tīng)的名字：蝶形運算符號。
下面的動(dòng)圖演示了蝶形運算的過(guò)程：
以8點(diǎn)長(cháng)序列為例，我們來(lái)看分解為2個(gè)4點(diǎn)長(cháng)DFT，是如何通過(guò)蝶形運算合成8點(diǎn)DFT的：
經(jīng)過(guò)第一次分解之后，總的運算量=兩個(gè)N/2點(diǎn)DFT的運算+N/2個(gè)蝶形的運算。而每次蝶形運算，只需要1次乘法，2次加法。所以，總的乘法次數為
加法次數為
當N很大時(shí)，運算量減少了近一半。
這就給了我們信心，說(shuō)明這種分解思路是可以有效減少運算量的。我們繼續分解下去，經(jīng)過(guò)M-1次分解，分解為N/2 個(gè) 2 點(diǎn)長(cháng)序列。
而2點(diǎn)DFT也用蝶形運算來(lái)表示（因為計算機最擅長(cháng)一致而重復的東西），就得到下面的流圖：
2. 按頻率抽?。―IF）FFT算法
仍以第一次分解（N點(diǎn)分為2個(gè)N/2點(diǎn)）為例來(lái)說(shuō)明算法原理。
以8點(diǎn)長(cháng)序列為例，我們來(lái)看分解為2個(gè)4點(diǎn)長(cháng)DFT，是如何通過(guò)蝶形運算合成8點(diǎn)DFT的：
注意到，輸出的頻率數據，序號是按照偶數一組、奇數一組的順序排列的，所以這種算法稱(chēng)為：按頻率抽取。
我們繼續分解下去，經(jīng)過(guò)M-1次分解，分解為N/2 個(gè) 2 點(diǎn)長(cháng)序列，就得到下面的流圖：
3. 運算量分析
通過(guò)前面的分析可見(jiàn)，兩種基2FFT算法，運算量是一樣的，N點(diǎn)DFT，就分解成了若干個(gè)蝶形的運算而已。
多少個(gè)蝶形呢？序列長(cháng)度 N=2^M，共有 M級蝶形，每級N/2 個(gè)蝶形，共MN/2個(gè)。
而每個(gè)蝶形是1次復數乘法，2次復數加法。所以總的運算量為：
以N=1024=2^10為例，直接計算DFT，需要1024的平方=1048576
次乘法，而采用FFT只需要（1024/2）×10=5120次乘法，二者的比值為204.8。運算量減少了好幾個(gè)數量級。
頻率作為自然界的一個(gè)基本物理量，是很多領(lǐng)域研究的重要內容。人們很早就認識到，用DFT的方法可以有效進(jìn)行信號的頻率分析。但是因為DFT算法運算量很大，在數字計算機發(fā)明以前，運算效率普遍很低的情況下，DFT也更多的是一種理論分析工具，很難被用于實(shí)際的信號處理。
FFT的出現，破解了這一歷史性難題，極大地促進(jìn)了數字信號處理這門(mén)學(xué)科的應用和發(fā)展。有人甚至以FFT算法提出的1965年作為數字信號處理這門(mén)學(xué)科的誕生之年。
4. 算法特點(diǎn)
在計算機看來(lái)，這兩種算法是非常相像的。
首先來(lái)看第一個(gè)特點(diǎn)：同址運算（又稱(chēng)同位運算或原位運算），每完成一個(gè)蝶形運算，輸入的兩個(gè)數據就沒(méi)有用的，這就意味著(zhù)，不需要再重新開(kāi)辟新的存儲單元來(lái)保存輸出數據，計算結果仍保留在原輸入數據占據的存儲單元即可。
再來(lái)看第二個(gè)特點(diǎn)：輸入/輸出數據的順序。這是兩種算法的不同之處。以DIT-FFT為例來(lái)說(shuō)明為什么會(huì )輸入倒位序。
還是以8點(diǎn)長(cháng)數據為例，輸入數據的正常順序是x(0)、x(1)、x(2)......x(7)，我們稱(chēng)之為 自然順序。按照序號的奇偶分為兩組，第一組是x(0)、x(2)、x(4)、x(6)，第二組是x(1)、x(3)、x(5)、x(7)。每個(gè)新的組再重新排隊報數，按奇偶分，第一組又分成兩個(gè)組，分別是x(0)、x(4)和x(2)、x(6)，第二組分成兩個(gè)組，分別是x(1)、x(5)和x(3)、x(7)。
也就是說(shuō)，8點(diǎn)長(cháng)序列的DIT-FFT，輸入數據的順序是：x(0)、x(4)、x(2)、x(6)、x(1)、x(5)、x(3)、x(7)。這個(gè)序號的順序乍看雜亂無(wú)章，其實(shí)有規律性。0、1、2、3、4、5、6、7的順序與0、4、2、6、1、3、5、7有何關(guān)系的呢？用二進(jìn)制來(lái)寫(xiě)一目了然，看下面的動(dòng)圖：
倒位序，是將二進(jìn)制數的最高有效位到最低有效位的位序進(jìn)行顛倒排列而得到的二進(jìn)制數。
DIT-FFT算法中，對時(shí)域序列按照序號的奇偶進(jìn)行分解，造成輸入序列的序號按照倒位序排列。
最后再說(shuō)一說(shuō)蝶形運算的規律。兩種FFT算法，最終都是轉換成了M列、每列N/2個(gè)、一共MN/2個(gè)蝶形運算。但二者蝶形運算的規律有差異。
第一個(gè)差異：基本蝶形不同。DIT是先乘旋轉因子，再加或減；而DIF是先加或減，再乘旋轉因子。
第二個(gè)差異：兩種算法，蝴蝶翅膀的距離（即節點(diǎn)間的距離）和旋轉因子的數目恰好相反。
仔細觀(guān)察兩種算法的流圖，我們會(huì )發(fā)現，二者互為轉置。
4.3 其他FFT算法簡(jiǎn)介
1. 混合基FFT
2. Chirp-z變換
實(shí)際應用中，有時(shí)只對信號的某一頻段感興趣，即只需要計算單位圓上某一段的頻譜值，而不需要計算[0，Π]區間的所有頻譜采樣值。此時(shí)，可以用”Chirp-z變換“（CZT）。
適用場(chǎng)合：窄帶信號的DFT。
3. Goertzel算法
在某些應用場(chǎng)合，只需計算很少幾個(gè)頻率點(diǎn)的頻譜值。例如，雙音多頻信號（DTMF）的檢測。此時(shí)可以采用卡澤爾（Goertzel）算法。
除此之外，傅里葉變換的快速算法還有很多種。不過(guò)應用最廣泛的依然能是基2FFT算法，它是數字信號處理最經(jīng)典算法之一，幾乎各種主流的計算機編程語(yǔ)言都有現成的函數可以調用。不同型號的芯片，硬件開(kāi)發(fā)商也都會(huì )給出優(yōu)化后的FFT算法源代碼，一般情況下直接調用就可以。
下一篇，我們將講述FFT算法在實(shí)際中的應用。
聯(lián)系客服
