快速傅立葉變換（FFT）

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

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

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

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

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

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

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

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

借助計(jì)算機(jī)分析其頻譜時(shí)，需要在時(shí)域和頻域離散化，即對(duì)的采樣序列求DFT

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

↓

→波皺↓

采樣←↓

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

k=0,1,2,…,N–1計(jì)算機(jī)運(yùn)算時(shí)：運(yùn)算式中有復(fù)數(shù)因子：N項(xiàng)

N個(gè)

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

長(zhǎng)期以來(lái)，人們一直在尋求一種能提高DFT運(yùn)算速度的方法。FFT便是Cooley&Tukey

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

1．利用的特點(diǎn)∴具有

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

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

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

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

1.2.2.序列的逆序排列

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

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

1.2.4.FFT的運(yùn)算量

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

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

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

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

求兩個(gè)N/2

點(diǎn)DFT

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

1．基本算法為蝶形運(yùn)算；

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

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

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

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

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

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