快速傅立葉變換（FFT）

引言四種不同傅立葉變換對傅里葉級數(shù)(FS)：連續(xù)時間,離散頻率的傅里葉變換。連續(xù)傅里葉變換(FT)：連續(xù)時間,連續(xù)頻率的傅里葉變換。序列的傅里葉變換(DTFT):離散時間,連續(xù)頻率的傅里葉變換.離散傅里葉變換(DFT):離散時間,離散頻率的傅里葉變換傅立葉變換離散時間傅立葉變換傅立葉級數(shù)離散傅立葉變換時間

連續(xù)離散連續(xù)離散非周期周期非周期周期

頻率1.連續(xù)傅里葉變換(FT)非周期連續(xù)時間信號通過連續(xù)付里葉變換(FT)得到非周期連續(xù)頻譜密度函數(shù)。例子這以下變換對可以看出時域連續(xù)函數(shù)造成頻域是非周期的譜,而是時域的非周期造成頻域是連續(xù)的譜.2.傅里葉級數(shù)(FS)周期連續(xù)時間信號非周期離散頻譜密度函數(shù)。周期為Tp的周期性連續(xù)時間函數(shù)x(t)可展成傅里葉級數(shù)X(jkΩ0),是離散非周期性頻譜,表示為:FS例子通過以下變換對可以看出時域的連續(xù)函數(shù)造成頻域是非周期的頻譜函數(shù),而頻域的離散頻譜就與時域的周期時間函數(shù)對應(yīng).(頻域采樣，時域周期延拓)3.序列的傅里葉變換(DTFT)非周期離散的時間信號(經(jīng)過單位園上的Z變換(DTFT))得到周期性連續(xù)的頻率函數(shù)。例子同樣可看出,時域的離散造成頻域的周期延拓

,而時域的非周期對應(yīng)于頻域的連續(xù)

.4.離散傅里葉變換(DFT)上面討論的三種傅里葉變換對,都不適用在計算機上運算,因為至少在一個域(時域或頻域)中,函數(shù)是連續(xù)的.因為從數(shù)字計算角度,我們感興趣的是時域及頻域都是離散的情況,這就是我們這里要談到的離散傅里葉變換.周期性離散時間信號從上可以推斷：周期性時間信號可以產(chǎn)生頻譜是離散的離散時間信號可以產(chǎn)生頻譜是周期性的。得出其頻譜為周期性離散的。也即我們所希望的。二、四種付里葉變換形式的歸納DFS和DFT的導(dǎo)出出發(fā)點：如何利用離散頻譜表示離散時間信號以便用于計算機進(jìn)行數(shù)字信號處理計算機處理的基本要求：離散值(序列)有限長(存儲容量有限)DFT的變換總之，一個域的離散必然造成另一個域的周期延拓。數(shù)字計算機N足夠大計算機處理信號的流程

模擬信號的頻譜分析1.1離散傅立葉變換的定義1.1.1DFT的定義設(shè)x（n)是一個長度為M的有限長序列，則定義的N點離散傅立葉變換為其逆變換為：式中N為DFT變換區(qū)間長度。用DFT對信號進(jìn)行譜分析

1．DFT是連續(xù)傅里葉變換的近似

分析連續(xù)時間信號的頻譜,即求其傅里葉變換：

借助計算機分析其頻譜時，需要在時域和頻域離散化，即對的采樣序列求DFT

，這時，求出的X(k)是否能代表原信號的頻譜？精度如何保證？N點DFT時域頻域（1）采樣（離散化）→周期化（2）截?。ㄓ邢揲L）↓

↓

→波皺↓

采樣←↓

（3）周期化可見，DFT是對連續(xù)傅里葉變換的近似，誤差主要由采樣引起的頻譜混疊及信號截取引起的頻譜波皺所造成。（1）時域采樣間隔(T)應(yīng)足夠?。唬?）頻域采樣間隔(F)應(yīng)足夠??；（3）截取長度(T0)應(yīng)足夠大?！郉FT的點數(shù)應(yīng)足夠大?；虿扇〖訖?quán)技術(shù)以提高近似程度。為提高近似精度：1.1.2計算機處理DFT的運算量

k=0,1,2,…,N–1計算機運算時：運算式中有復(fù)數(shù)因子：N項

N個

∴計算一個N點DFT，共需次復(fù)乘。以做一次復(fù)乘1μs計，若N=4096，所需時間為由于計算量大，且要求相當(dāng)大的內(nèi)存，難以實現(xiàn)實時處理，限制了DFT的應(yīng)用。

長期以來，人們一直在尋求一種能提高DFT運算速度的方法。FFT便是Cooley&Tukey

在1965年提出的的快速算法，它可以使運算速度提高幾百倍，從而使數(shù)字信號處理學(xué)科成為一個新興的應(yīng)用學(xué)科。1.1.3FFT算法的設(shè)計思想

1．利用的特點∴具有

1）周期性2）共軛性3）對稱性4）5）2．把N點DFT化為幾組點數(shù)較少的DFT運算N點DFT運算的復(fù)乘次數(shù)為次，若將N點DFT化為2組，則復(fù)乘次數(shù)約為次。1.2

基２FFT按時間抽取算法（Cooley-Tukey算法）1.2.1.算法的推導(dǎo)

設(shè)，將x(n)按n的奇偶分為兩組：根據(jù)這組表達(dá)式，可畫出X(k)與之間的運算關(guān)系流圖。X(k)為N點DFT運算，而與為當(dāng)時，可利用的周期性。這樣，可以寫出N點的關(guān)系式：X(k)與減少運算量化簡蝶形運算流圖經(jīng)以上分解，各為、，即分次復(fù)乘，而將別進(jìn)行了與合成為X(k)時，需進(jìn)行次復(fù)乘：顯然，這樣的分解是有效的。由于,可繼續(xù)照此辦法分解，即將按r

的奇、偶各分為兩組，于是，仿照X(k)，可寫出如此分解下去,直到分解為兩點,以N=8為例?！鄰?fù)乘次數(shù)

1.2.2.序列的逆序排列

由于x(n)被反復(fù)地按奇、偶分組，所以流圖輸入端的的排列不再是順序的，但仍有規(guī)律可循：對于任意n

可以用M個二進(jìn)制碼表示為：當(dāng)n反復(fù)按奇、偶分解時，即按二進(jìn)制碼的“0”，“1”分解。n001n10101n201010101…01010101010101010101010101010101逆序（碼位倒置）比較順序BINDEC00010001011000110101111104261537BINDEC01234567000001010011100101110111運算前運算后1.2.3.同址運算對于算法流圖中的任意一個蝶形運算。

1.2.4.FFT的運算量

∴可進(jìn)行M次分解，即N點FFT可經(jīng)過M次迭代運算得到，每次迭代中的蝶形運算為個,每個蝶形運算中有一次復(fù)乘，∴復(fù)乘次數(shù)

例如FFT：復(fù)乘次數(shù)DFT：復(fù)乘次數(shù)相差1260倍！

1.3基２ＦＦＴ按頻率抽取算法（sande-Tukey算法）

頻域抽取基－2FFT算法（DIF-FFT）算法的推導(dǎo)頻域抽取算法是把時間序列前后對半分解為兩個長為N/2點的序列，則：當(dāng)k取偶數(shù)時（k=2r，r=0,1,...,N/2－1）∴的N點DFT按k的奇偶分組可分為兩個N/2的DFT當(dāng)k取奇數(shù)時（k=2r＋1，r=0,1,...,N/2－1）這一結(jié)論表明：求的N點DFT再次分解成

求兩個N/2

點DFT

DIF-FFT的蝶式運算流圖DIF-FFT的一次分解運算流圖先蝶式運算，后DFT。例如：N=8時DIF-FFT1.3.1.算法的推導(dǎo)將x(n)按前后分為兩組：1.3.2.流圖的轉(zhuǎn)置頻域中的第l點與時域中的第r點的關(guān)系為頻域中的第r點與時域中的第l點的關(guān)系為從流圖中也可看到：流圖轉(zhuǎn)置：X(?)改寫為x(?)，序號不變；x(?)改寫為X(?)，序號不變；所有箭頭反向，系數(shù)不變。DIT-FFTDIF-FFT時間抽取頻率抽取1.3.3.兩種蝶形運算流圖的區(qū)別1.4FFT算法的軟件實現(xiàn)(下頁)（框圖）1.4.1.算法的特點

1．基本算法為蝶形運算；

2．運算分為次迭代進(jìn)行；3．運算可原址進(jìn)行；

4．輸入數(shù)據(jù)需進(jìn)行逆序重排；

5．迭代過程中，基本蝶形運算的兩個點之間的間距及系數(shù)的變化有規(guī)律可循。在第L

輪迭代中（1）有種蝶形運算系數(shù)（2）系數(shù)分別為

（3）每種系數(shù)對應(yīng)的蝶形運算有個，相距點（4）參加同一蝶形運算的兩個點之間的間距為點（返回）1.4.2.算法的程序框圖開始逆序重排蝶形運算結(jié)束L=1,M輸出J=0,B-1蝶形運算三層循環(huán)：N1為相同系數(shù)的蝶形運算的間距（N1=2L

）2）中間層為蝶形運算組次J（J=1，2，…，3）最內(nèi)層為基本蝶形運算1）最外層為迭代輪次L（L=1，2，…，M）2E-E1-1）