快速傅里葉變換FFT進(jìn)行串講

本文對離散信號的頻域分析（共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正變換為例。（順便說一句，大家要像熟悉自己的手機(jī)一樣熟悉旋轉(zhuǎn)因子，閉著眼睛都知道它）

觀察DFT正變換的公式，容易看出：每計(jì)算一個點(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ù)，至少要取成序列的長度，當(dāng)序列長度很長時(shí)，運(yùn)算量巨大！如下圖所示。

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

1965年，庫利（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個N/2點(diǎn)DFT分別計(jì)算，乘法的次數(shù)是1/2的N的平方，減少了一半；分成4個N/4點(diǎn)DFT，乘法的次數(shù)又減少了一半。如果能夠繼續(xù)下去，前景很讓人向往。

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

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

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

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

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

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

按頻率抽取的FFT算法——Decimation-in-Frequency，簡稱DIF-FFT。

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

4.2 兩種基2FFT算法

1. 按時(shí)間抽取（DIT）FFT算法

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

首先解決怎么分的問題。

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

然后解決怎么合的問題。

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

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

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

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

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

加法次數(shù)為

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

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

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

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

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

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

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

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

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

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

多少個蝶形呢？序列長度 N=2^M，共有 M級蝶形，每級N/2 個蝶形，共MN/2個。

而每個蝶形是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)算量減少了好幾個數(shù)量級。

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

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

4. 算法特點(diǎn)

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

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

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

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

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

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

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

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

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

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

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

4.3其他FFT算法簡介

1. 混合基FFT

2. Chirp-z變換

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

適用場合：窄帶信號的DFT。

3.Goertzel算法

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

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