本文對(duì)離散信號(hào)的頻域分析（共5節(jié)）中的第4節(jié)——快速傅里葉變換FFT（Fast- Fourier Transform）進(jìn)行串講。

首先大家需要知道的是，F(xiàn)FT并不是一種新的變換，它僅僅是作為DFT的快速算法。本節(jié)包括下列內(nèi)容：

4.1 改進(jìn)DFT計(jì)算的方法

1. DFT計(jì)算量分析

觀察正變換和反變換的公式可知，二者的運(yùn)算方式和運(yùn)算量是完全相同的。下面的分析均以DFT正變換為例。（順便說(shuō)一句，大家要像熟悉自己的手機(jī)一樣熟悉旋轉(zhuǎn)因子，閉著眼睛都知道它）

觀察DFT正變換的公式，容易看出：每計(jì)算一個(gè)點(diǎn)的數(shù)據(jù)，需要N次復(fù)數(shù)乘法、N-1次復(fù)數(shù)加法，所以，N點(diǎn)DFT，需要N的平方次復(fù)數(shù)乘法，N(N-1)次復(fù)數(shù)加法。我們知道，DFT的點(diǎn)數(shù)，至少要取成序列的長(zhǎng)度，當(dāng)序列長(zhǎng)度很長(zhǎng)時(shí)，運(yùn)算量巨大！如下圖所示。

以1024點(diǎn)為例，復(fù)數(shù)乘法的次數(shù)100萬(wàn)次之多。

1965年，庫(kù)利（J.W.Cooley）和圖基（J.W.Tukey）在《Mathmatics of Computation》上發(fā)表了《AnAlgorithm for the Machine Calculation of Complex Fourier Series》，提出一種高效DFT運(yùn)算的快速算法，后人稱為快速傅里葉變換（Fast Fourier Transform ——FFT）。

2. 改進(jìn)DFT計(jì)算效率的基本途徑

N點(diǎn)DFT，直接計(jì)算，需要N的平方次乘法；分成2個(gè)N/2點(diǎn)DFT分別計(jì)算，乘法的次數(shù)是1/2的N的平方，減少了一半；分成4個(gè)N/4點(diǎn)DFT，乘法的次數(shù)又減少了一半。如果能夠繼續(xù)下去，前景很讓人向往。

為了能夠一直分下去，我們限定N為2的整數(shù)次冪，即：N=2^M，稱為基2FFT。

由此可見，F(xiàn)FT的基本思想是：把長(zhǎng)序列分成幾個(gè)較短的序列。

但怎么分？不能隨便亂分，基本原則是：要保證這幾個(gè)短序列的DFT組合起來(lái)后，能夠很方便地構(gòu)成原來(lái)長(zhǎng)序列的DFT。

所以，DFT快速算法要解決的兩個(gè)核心問(wèn)題是：怎么分？怎么合？

根據(jù)分與合的方式不同，有兩種基2FFT算法，分別稱為：

按時(shí)間抽取的FFT算法——Decimation-in-Time，簡(jiǎn)稱DIT-FFT。

按頻率抽取的FFT算法——Decimation-in-Frequency，簡(jiǎn)稱DIF-FFT。

下面我們分別來(lái)歸納總結(jié)兩種基2FFT算法。

4.2 兩種基2FFT算法

1. 按時(shí)間抽?。―IT）FFT算法

以第一次分解（N點(diǎn)分為2個(gè)N/2點(diǎn)）為例來(lái)說(shuō)明算法原理。

首先解決怎么分的問(wèn)題。

通俗地說(shuō)，就是：大家列隊(duì)、報(bào)數(shù)（從0開始）。報(bào)偶數(shù)的一組，奇數(shù)的一組。

然后解決怎么合的問(wèn)題。

我們略過(guò)看似艱苦卓絕實(shí)際很簡(jiǎn)單的推導(dǎo)過(guò)程，直接上結(jié)論：

公式不好看，有人畫了一幅圖，并且起了個(gè)好聽的名字：蝶形運(yùn)算符號(hào)。

下面的動(dòng)圖演示了蝶形運(yùn)算的過(guò)程：

以8點(diǎn)長(zhǎng)序列為例，我們來(lái)看分解為2個(gè)4點(diǎn)長(zhǎng)DFT，是如何通過(guò)蝶形運(yùn)算合成8點(diǎn)DFT的：

經(jīng)過(guò)第一次分解之后，總的運(yùn)算量=兩個(gè)N/2點(diǎn)DFT的運(yùn)算+N/2個(gè)蝶形的運(yùn)算。而每次蝶形運(yùn)算，只需要1次乘法，2次加法。所以，總的乘法次數(shù)為

加法次數(shù)為

當(dāng)N很大時(shí)，運(yùn)算量減少了近一半。

這就給了我們信心，說(shuō)明這種分解思路是可以有效減少運(yùn)算量的。我們繼續(xù)分解下去，經(jīng)過(guò)M-1次分解，分解為N/2 個(gè) 2 點(diǎn)長(zhǎng)序列。

而2點(diǎn)DFT也用蝶形運(yùn)算來(lái)表示（因?yàn)橛?jì)算機(jī)最擅長(zhǎng)一致而重復(fù)的東西），就得到下面的流圖：

2. 按頻率抽?。―IF）FFT算法

仍以第一次分解（N點(diǎn)分為2個(gè)N/2點(diǎn)）為例來(lái)說(shuō)明算法原理。

以8點(diǎn)長(zhǎng)序列為例，我們來(lái)看分解為2個(gè)4點(diǎn)長(zhǎng)DFT，是如何通過(guò)蝶形運(yùn)算合成8點(diǎn)DFT的：

注意到，輸出的頻率數(shù)據(jù)，序號(hào)是按照偶數(shù)一組、奇數(shù)一組的順序排列的，所以這種算法稱為：按頻率抽取。

我們繼續(xù)分解下去，經(jīng)過(guò)M-1次分解，分解為N/2 個(gè) 2 點(diǎn)長(zhǎng)序列，就得到下面的流圖：

3. 運(yùn)算量分析

通過(guò)前面的分析可見，兩種基2FFT算法，運(yùn)算量是一樣的，N點(diǎn)DFT，就分解成了若干個(gè)蝶形的運(yùn)算而已。

多少個(gè)蝶形呢？序列長(zhǎng)度 N=2^M，共有 M級(jí)蝶形，每級(jí)N/2 個(gè)蝶形，共MN/2個(gè)。

而每個(gè)蝶形是1次復(fù)數(shù)乘法，2次復(fù)數(shù)加法。所以總的運(yùn)算量為：

以N=1024=2^10為例，直接計(jì)算DFT，需要1024的平方=1048576

次乘法，而采用FFT只需要（1024/2）×10=5120次乘法，二者的比值為204.8。運(yùn)算量減少了好幾個(gè)數(shù)量級(jí)。

頻率作為自然界的一個(gè)基本物理量，是很多領(lǐng)域研究的重要內(nèi)容。人們很早就認(rèn)識(shí)到，用DFT的方法可以有效進(jìn)行信號(hào)的頻率分析。但是因?yàn)镈FT算法運(yùn)算量很大，在數(shù)字計(jì)算機(jī)發(fā)明以前，運(yùn)算效率普遍很低的情況下，DFT也更多的是一種理論分析工具，很難被用于實(shí)際的信號(hào)處理。

FFT的出現(xiàn)，破解了這一歷史性難題，極大地促進(jìn)了數(shù)字信號(hào)處理這門學(xué)科的應(yīng)用和發(fā)展。有人甚至以FFT算法提出的1965年作為數(shù)字信號(hào)處理這門學(xué)科的誕生之年。

4. 算法特點(diǎn)

在計(jì)算機(jī)看來(lái)，這兩種算法是非常相像的。

首先來(lái)看第一個(gè)特點(diǎn)：同址運(yùn)算（又稱同位運(yùn)算或原位運(yùn)算），每完成一個(gè)蝶形運(yùn)算，輸入的兩個(gè)數(shù)據(jù)就沒(méi)有用的，這就意味著，不需要再重新開辟新的存儲(chǔ)單元來(lái)保存輸出數(shù)據(jù)，計(jì)算結(jié)果仍保留在原輸入數(shù)據(jù)占據(jù)的存儲(chǔ)單元即可。

再來(lái)看第二個(gè)特點(diǎn)：輸入/輸出數(shù)據(jù)的順序。這是兩種算法的不同之處。以DIT-FFT為例來(lái)說(shuō)明為什么會(huì)輸入倒位序。

還是以8點(diǎn)長(zhǎng)數(shù)據(jù)為例，輸入數(shù)據(jù)的正常順序是x(0)、x(1)、x(2)......x(7)，我們稱之為自然順序。按照序號(hào)的奇偶分為兩組，第一組是x(0)、x(2)、x(4)、x(6)，第二組是x(1)、x(3)、x(5)、x(7)。每個(gè)新的組再重新排隊(duì)報(bào)數(shù)，按奇偶分，第一組又分成兩個(gè)組，分別是x(0)、x(4)和x(2)、x(6)，第二組分成兩個(gè)組，分別是x(1)、x(5)和x(3)、x(7)。

也就是說(shuō)，8點(diǎn)長(zhǎng)序列的DIT-FFT，輸入數(shù)據(jù)的順序是：x(0)、x(4)、x(2)、x(6)、x(1)、x(5)、x(3)、x(7)。這個(gè)序號(hào)的順序乍看雜亂無(wú)章，其實(shí)有規(guī)律性。0、1、2、3、4、5、6、7的順序與0、4、2、6、1、3、5、7有何關(guān)系的呢？用二進(jìn)制來(lái)寫一目了然，看下面的動(dòng)圖：

倒位序，是將二進(jìn)制數(shù)的最高有效位到最低有效位的位序進(jìn)行顛倒排列而得到的二進(jìn)制數(shù)。

DIT-FFT算法中，對(duì)時(shí)域序列按照序號(hào)的奇偶進(jìn)行分解，造成輸入序列的序號(hào)按照倒位序排列。

最后再說(shuō)一說(shuō)蝶形運(yùn)算的規(guī)律。兩種FFT算法，最終都是轉(zhuǎn)換成了M列、每列N/2個(gè)、一共MN/2個(gè)蝶形運(yùn)算。但二者蝶形運(yùn)算的規(guī)律有差異。

第一個(gè)差異：基本蝶形不同。DIT是先乘旋轉(zhuǎn)因子，再加或減；而DIF是先加或減，再乘旋轉(zhuǎn)因子。

第二個(gè)差異：兩種算法，蝴蝶翅膀的距離（即節(jié)點(diǎn)間的距離）和旋轉(zhuǎn)因子的數(shù)目恰好相反。

仔細(xì)觀察兩種算法的流圖，我們會(huì)發(fā)現(xiàn)，二者互為轉(zhuǎn)置。

4.3其他FFT算法簡(jiǎn)介

1. 混合基FFT

2. Chirp-z變換

實(shí)際應(yīng)用中，有時(shí)只對(duì)信號(hào)的某一頻段感興趣，即只需要計(jì)算單位圓上某一段的頻譜值，而不需要計(jì)算[0，Π]區(qū)間的所有頻譜采樣值。此時(shí)，可以用”Chirp-z變換“（CZT）。

適用場(chǎng)合：窄帶信號(hào)的DFT。

3.Goertzel算法

在某些應(yīng)用場(chǎng)合，只需計(jì)算很少幾個(gè)頻率點(diǎn)的頻譜值。例如，雙音多頻信號(hào)（DTMF）的檢測(cè)。此時(shí)可以采用卡澤爾（Goertzel）算法。

除此之外，傅里葉變換的快速算法還有很多種。不過(guò)應(yīng)用最廣泛的依然能是基2FFT算法，它是數(shù)字信號(hào)處理最經(jīng)典算法之一，幾乎各種主流的計(jì)算機(jī)編程語(yǔ)言都有現(xiàn)成的函數(shù)可以調(diào)用。不同型號(hào)的芯片，硬件開發(fā)商也都會(huì)給出優(yōu)化后的FFT算法源代碼，一般情況下直接調(diào)用就可以。