快速傅里葉變換蝶形算法演示文稿目前一頁\總數(shù)五十二頁\編于十一點（優(yōu)選）快速傅里葉變換蝶形算法詳解目前二頁\總數(shù)五十二頁\編于十一點本章目錄直接計算DFT的問題及改進的途徑按時間抽取的基2-FFT算法

按頻率抽取的基2-FFT算法

快速傅里葉逆變換(IFFT)算法

Matlab實現(xiàn)3目前三頁\總數(shù)五十二頁\編于十一點5.1引言

DFT在實際應用中很重要:可以計算信號的頻譜、功率譜和線性卷積等。直接按DFT變換進行計算，當序列長度N很大時，計算量非常大，所需時間會很長。FFT并不是一種與DFT不同的變換，而是DFT的一種快速計算的算法。

4目前四頁\總數(shù)五十二頁\編于十一點5.2直接計算DFT的問題及改進的途徑

DFT的運算量

設復序列x(n)長度為N點，其DFT為k=0，，…，N-1（1）計算一個X(k)值的運算量復數(shù)乘法次數(shù)：N復數(shù)加法次數(shù)：N－15目前五頁\總數(shù)五十二頁\編于十一點5.2.1DFT的運算量（2）計算全部N個X(k)值的運算量復數(shù)乘法次數(shù)：N2復數(shù)加法次數(shù)：N(N－1)（3）對應的實數(shù)運算量6目前六頁\總數(shù)五十二頁\編于十一點一次復數(shù)乘法：4次實數(shù)乘法2次實數(shù)加法＋一個X(k)：4N次實數(shù)乘法＋2N+2(N-1)=2(2N-1)次實數(shù)加法所以整個N點DFT運算共需要：N×2(2N-1)=2N(2N-1)實數(shù)乘法次數(shù)：4N2實數(shù)加法次數(shù)：7目前七頁\總數(shù)五十二頁\編于十一點DFT運算量的結論N點DFT的復數(shù)乘法次數(shù)舉例NN2NN22464404941612816384864256655361625651226214432102810241048576結論：當N很大時，其運算量很大，對實時性很強的信號處理來說，要求計算速度快，因此需要改進DFT的計算方法，以大大減少運算次數(shù)。8目前八頁\總數(shù)五十二頁\編于十一點

5.2.2減少運算工作量的途徑

主要原理是利用系數(shù)的以下特性對DFT進行分解：（1）對稱性（2）周期性（3）可約性另外，9目前九頁\總數(shù)五十二頁\編于十一點5.3按時間抽取的基2-FFT算法

算法原理按時間抽取基-2FFT算法與直接計算DFT運算量的比較按時間抽取的FFT算法的特點按時間抽取FFT算法的其它形式流程圖10目前十頁\總數(shù)五十二頁\編于十一點5.3.1算法原理

設N＝2L，將x(n)按n的奇偶分為兩組：

r=0，1，…，則11目前十一頁\總數(shù)五十二頁\編于十一點式中，X1(k)和X2(k)分別是x1(n)和x2(n)的N/2的DFT。另外，式中k的取值范圍是：0，1，…，N/2－1。12目前十二頁\總數(shù)五十二頁\編于十一點因此，只能計算出X(k)的前一半值。后一半X(k)值，N/2，N/2＋1，…，N？利用可得到同理可得13目前十三頁\總數(shù)五十二頁\編于十一點考慮到因此可得后半部分X(k)及前半部分X(k)k=0，1，…，N/2－1k=0，1，…，N/2－114目前十四頁\總數(shù)五十二頁\編于十一點蝶形運算蝶形運算式蝶形運算信號流圖符號因此，只要求出2個N/2點的DFT，即X1(k)和X2(k)，再經(jīng)過蝶形運算就可求出全部X(k)的值，運算量大大減少。15目前十五頁\總數(shù)五十二頁\編于十一點以8點為例第一次按奇偶分解以N=8為例，分解為2個4點的DFT，然后做8/2=4次蝶形運算即可求出所有8點X(k)的值。16目前十六頁\總數(shù)五十二頁\編于十一點蝶形運算量比較復數(shù)乘法次數(shù)：

N2復數(shù)加法次數(shù)：

N(N－1)復數(shù)乘法次數(shù)：

2*(N/2)2+N/2=N2/2+N/2復數(shù)加法次數(shù)：

2*(N/2)(N/2－1)+2*N/2=N2/2N點DFT的運算量

分解一次后所需的運算量＝2個N/2的DFT＋N/2蝶形：因此通過一次分解后，運算工作量減少了差不多一半。

17目前十七頁\總數(shù)五十二頁\編于十一點進一步按奇偶分解由于N＝2L，因而N/2仍是偶數(shù)，可以進一步把每個N/2點子序列再按其奇偶部分分解為兩個N/4點的子序列。以N/2點序列x1(r)為例

則有

k=0,1,…,

18目前十八頁\總數(shù)五十二頁\編于十一點且k=0,1,…,由此可見，一個N/2點DFT可分解成兩個N/4點DFT。同理，也可對x2(n)進行同樣的分解，求出X2(k)。19目前十九頁\總數(shù)五十二頁\編于十一點以8點為例第二次按奇偶分解20目前二十頁\總數(shù)五十二頁\編于十一點算法原理對此例N=8，最后剩下的是4個N/4=2點的DFT，2點DFT也可以由蝶形運算來完成。以X3(k)為例。k=0,1即這說明，N=2M的DFT可全部由蝶形運算來完成。21目前二十一頁\總數(shù)五十二頁\編于十一點以8點為例第三次按奇偶分解N=8按時間抽取法FFT信號流圖22目前二十二頁\總數(shù)五十二頁\編于十一點5.3.2按時間抽取基2-FFT算法與直接計算DFT運算量的比較

由按時間抽取法FFT的信號流圖可知，當N=2L時，共有

級蝶形運算；每級都由

個蝶形運算組成，而每個蝶形有

次復乘、

次復加，因此每級運算都需

次復乘和

次復加。

LN/2

N/2

12N23目前二十三頁\總數(shù)五十二頁\編于十一點這樣

級運算總共需要：L復數(shù)乘法：

復數(shù)加法：

直接DFT算法運算量復數(shù)乘法：

復數(shù)加法：

N2N(N－1)直接計算DFT與FFT算法的計算量之比為M24目前二十四頁\總數(shù)五十二頁\編于十一點FFT算法與直接DFT算法運算量的比較NN2計算量之比MNN2計算量之比M2414.01281638444836.641644.025665536102464.0864125.45122621442304113.816256328.0102410485765120204.83210288012.82048419430411264372.464404919221.425目前二十五頁\總數(shù)五十二頁\編于十一點5.3.3按時間抽取的FFT算法的特點序列的逆序排列同址運算（原位運算）蝶形運算兩節(jié)點間的距離的確定26目前二十六頁\總數(shù)五十二頁\編于十一點序列的逆序排列由于x(n)被反復地按奇、偶分組，所以流圖輸入端的排列不再是順序的，但仍有規(guī)律可循：因為N=2M，對于任意n（0≤n≤N-1)，可以用M個二進制碼表示為：

n反復按奇、偶分解時，即按二進制碼的“0”“1”分解。序列的逆序排列27目前二十七頁\總數(shù)五十二頁\編于十一點倒位序的樹狀圖（N=8）

28目前二十八頁\總數(shù)五十二頁\編于十一點碼位的倒位序(N=8)

自然順序n二進制數(shù)倒位序二進制數(shù)倒位序順序數(shù)000000001001100420100102301111064100001151011015611001137111111729目前二十九頁\總數(shù)五十二頁\編于十一點倒位序的變址處理（N=8）30目前三十頁\總數(shù)五十二頁\編于十一點同址運算（原位運算）某一列任何兩個節(jié)點k和j的節(jié)點變量進行蝶形運算后，得到結果為下一列k、j兩節(jié)點的節(jié)點變量，而和其他節(jié)點變量無關。這種原位運算結構可以節(jié)省存儲單元，降低設備成本。運算前運算后例同址運算（原位運算）31目前三十一頁\總數(shù)五十二頁\編于十一點觀察原位運算規(guī)律32目前三十二頁\總數(shù)五十二頁\編于十一點蝶形運算兩節(jié)點間的距離

以N=8為例：第一級蝶形，距離為：第二級蝶形，距離為：第三級蝶形，距離為：規(guī)律：對于共L級的蝶形而言，其m級蝶形運算的節(jié)點間的距離為124蝶形運算兩節(jié)點間的距離

33目前三十三頁\總數(shù)五十二頁\編于十一點

的確定

以N=8為例：的確定

34目前三十四頁\總數(shù)五十二頁\編于十一點5.4按頻率抽取的基2-FFT算法

算法原理再把輸出X(k)按k的奇偶分組先把輸入按n的順序分成前后兩半設序列長度為N=2L，L為整數(shù)前半子序列x(n)后半子序列

0≤n≤0≤n≤35目前三十五頁\總數(shù)五十二頁\編于十一點5.4.1算法原理由DFT定義得k=0，1，…，N36目前三十六頁\總數(shù)五十二頁\編于十一點由于所以則k=0，1，…，N37目前三十七頁\總數(shù)五十二頁\編于十一點然后按k的奇偶可將X(k)分為兩部分r=0，1，…，則式可轉化為38目前三十八頁\總數(shù)五十二頁\編于十一點令n=0，1，…，代入r=0，1，…，可得為2個N/2點的DFT，合起來正好是N點X(k)的值。39目前三十九頁\總數(shù)五十二頁\編于十一點蝶形運算將稱為蝶形運算與時間抽選基2FFT算法中的蝶形運算符號略有不同。40目前四十頁\總數(shù)五十二頁\編于十一點例按頻率抽取(N=8)

例按頻率抽取，將N點DFT分解為兩個N/2點DFT的組合(N=8)41目前四十一頁\總數(shù)五十二頁\編于十一點與時間抽取法的推導過程一樣，由于N=2L，N/2仍然是一個偶數(shù)，因而可以將每個N/2點DFT的輸出再分解為偶數(shù)組與奇數(shù)組，這就將N/2點DFT進一步分解為兩個N/4點DFT。N=842目前四十二頁\總數(shù)五十二頁\編于十一點5.4.2頻率抽取法與時間抽取法的異同

頻率抽取法輸入是自然順序，輸出是倒位序的；時間抽取法正好相反。頻率抽取法的基本蝶形與時間抽取法的基本蝶形有所不同。頻率抽取法運算量與時間抽取法相同。頻率抽取法與時間抽取法的基本蝶形是互為轉置的。

43目前四十三頁\總數(shù)五十二頁\編于十一點5.5快速傅里葉逆變換(IFFT)算法IDFT公式DFT公式比較可以看出，IDFT多出M個1/2可分解到M級蝶形運算中。44目前四十四頁\總數(shù)五十二頁\編于十一點例頻率抽取IFFT流圖(N=8)

45目前四十五頁\總數(shù)五十二頁\編于十一點快速傅里葉逆變換另一種算法46目前四十六頁\總數(shù)五十二頁\編于十一點5.8Matlab實現(xiàn)用FFT進行譜分析的Matlab實現(xiàn)用CZT進行譜分析的Matlab實現(xiàn)在Matlab中使用的線性調頻z變換函數(shù)為czt，其調用格式為>>X=czt(x,M,W,A)其中，x是待變換的時域信號x(n)，其長度為N，M是變換的長度，W確定變換的步長，A確定變換的起點。若M=N，A=1，則CZT變成DFT。47目前四十七頁\總數(shù)五十二頁\編于十一點5.8.1用FFT進行譜分析的Matlab實現(xiàn)例5.1設模擬信號，以t=0.01n(n=0:N-1)進行取樣，試用fft函數(shù)對其做頻譜分析。N分別為：(1)N=45；(2)N=50；(3)N=55；(2)N=60。程序清單如下%計算N=45的FFT并繪出其幅頻曲線N=45;n=0:N-1;t=0.01*n;q=n*2*pi/N;x=2*sin(4*pi*t)+5*cos(8*pi*t);y=fft(x,N);figure(1)subplot(2,2,1)plot(q,abs(y))title('FFTN=45')48目前四