FFT快速傅里葉變換蝶形算法詳解解析學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1FFT快速傅里葉變換蝶形算法詳解解析快速傅里葉變換蝶形算法詳解解析第一頁，編輯于星期六：十點(diǎn) 四十七分。2 第1頁/共53頁第二頁，編輯于星期六：十點(diǎn) 四十七分。3第2頁/共53頁第三頁，編輯于星期六：十點(diǎn) 四十七分。4設(shè)復(fù)序列x(n) 長(zhǎng)度為N點(diǎn)，其DFT為10( )( )NnkNnX kx n Wk=0，N-1 （1）計(jì)算一個(gè)X(k) 值的運(yùn)算量復(fù)數(shù)乘法次數(shù)： N復(fù)數(shù)加法次數(shù)： N1第3頁/共53頁第四頁，編輯于星期六：十點(diǎn) 四十七分。5（2）計(jì)算全部N個(gè)X(k) 值的運(yùn)算量復(fù)數(shù)乘法次數(shù)： N2復(fù)數(shù)加法次數(shù)： N(N1)（3）對(duì)應(yīng)的實(shí)數(shù)運(yùn)算量1100( )( )Re ( )Im (

2、 )ReImNNnknknkNNNnnX kx n Wx njx nWjW10Re ( ) ReIm ( ) ImNnknkNNnx nWx nWRe ( ) ImIm ( ) RenknkNNjx nWx nW第4頁/共53頁第五頁，編輯于星期六：十點(diǎn) 四十七分。6一次復(fù)數(shù)乘法： 4次實(shí)數(shù)乘法 2次實(shí)數(shù)加法 一個(gè)X(k) ：4N次實(shí)數(shù)乘法2N+2(N-1)= 2(2N-1)次實(shí)數(shù)加法 所以 整個(gè)N點(diǎn)DFT運(yùn)算共需要：N2(2N-1)= 2N(2N-1)實(shí)數(shù)乘法次數(shù)：4 N2實(shí)數(shù)加法次數(shù)：第5頁/共53頁第六頁，編輯于星期六：十點(diǎn) 四十七分。7N點(diǎn)DFT的復(fù)數(shù)乘法次數(shù)舉例NN2NN224644

3、04941612816384864256 65 536 16256512 262 144 3210281024 1 048 576 結(jié)論：當(dāng)N很大時(shí)，其運(yùn)算量很大，對(duì)實(shí)時(shí)性很強(qiáng)的信號(hào)處理來說，要求計(jì)算速度快，因此需要改進(jìn)DFT的計(jì)算方法，以大大減少運(yùn)算次數(shù)。 第6頁/共53頁第七頁，編輯于星期六：十點(diǎn) 四十七分。8 nkNW主要原理是利用系數(shù) 的以下特性對(duì)DFT進(jìn)行分解： nkNW（1）對(duì)稱性 ()nkNW()k N nNW（2）周期性 ()()n N kn kNnkNNNWWW（3）可約性 mnknkmNNWW/nknk mNN mWW另外，12/NNWkNNkNWW)2/(第7頁/共53頁

4、第八頁，編輯于星期六：十點(diǎn) 四十七分。9第8頁/共53頁第九頁，編輯于星期六：十點(diǎn) 四十七分。101(2 )( )xrx r設(shè)N2L，將x(n)按 n 的奇偶分為兩組： 2(21)( )xrx rr =0，1， 12N10( ) ( )( )NnkNnX kDFT x nx n W則1010)()(NnnnkNNnnnkNWnxWnx為奇數(shù)為偶數(shù)第9頁/共53頁第十頁，編輯于星期六：十點(diǎn) 四十七分。11120)12(1202) 12()2(NrkrNNrrkNWrxWrx1202212021)()(NrrkNkNNrrkNWrxWWrx)()(21kXWkXkN1010)()(NnnnkNNn

5、nnkNWnxWnx為奇數(shù)為偶數(shù)式中，X1(k)和X2(k)分別是x1(n)和x2(n)的N/2的DFT。另外，式中k的取值范圍是：0，1， ，N/21 。第10頁/共53頁第十一頁，編輯于星期六：十點(diǎn) 四十七分。12因此， 只能計(jì)算出X(k)的前一半值。12( )( )( )kNX kX kW Xk后一半X(k) 值， N/2 ， N/2 1， ，N ？rkNW2(2)2r NkNW利用可得到 1()2NXk2 1(2)120( )Nr NkNrx r W2 1120( )NrkNrx r W)(1kX同理可得22()( )2NXkXk第11頁/共53頁第十二頁，編輯于星期六：十點(diǎn) 四十七分

6、。13考慮到 kNkNNNkNNWWWW2)2(因此可得后半部分X(k) )2()2()2(221NkXWNkXNkXNkN12( )( )( )kNX kX kW Xk及前半部分X(k) )()(21kXWkXkNk=0，1， ，N/21k=0，1， ，N/21第12頁/共53頁第十三頁，編輯于星期六：十點(diǎn) 四十七分。1412( )( )( )kNX kX kW Xk12( )( )( )kNX kX kW Xk蝶形運(yùn)算式蝶形運(yùn)算信號(hào)流圖符號(hào) 因此，只要求出2個(gè)N/2點(diǎn)的DFT，即X1(k)和X2(k)，再經(jīng)過蝶形運(yùn)算就可求出全部X(k)的值，運(yùn)算量大大減少。第13頁/共53頁第十四頁，編輯

7、于星期六：十點(diǎn) 四十七分。150NW1NW2NW3NW以N=8為例，分解為2個(gè)4點(diǎn)的DFT，然后做8/2=4次蝶形運(yùn)算即可求出所有8點(diǎn)X(k)的值。第14頁/共53頁第十五頁，編輯于星期六：十點(diǎn) 四十七分。16復(fù)數(shù)乘法次數(shù)： N2復(fù)數(shù)加法次數(shù)： N(N1)復(fù)數(shù)乘法次數(shù)： 2*(N/2)2+N/2=N2/2+N/2復(fù)數(shù)加法次數(shù)： 2*(N/2)(N/21)+2*N/2=N2/2nN點(diǎn) 第15頁/共53頁第十六頁，編輯于星期六：十點(diǎn) 四十七分。17 由于N2L，因而N/2仍是偶數(shù) ，可以進(jìn)一步把每個(gè)N/2點(diǎn)子序列再按其奇偶部分分解為兩個(gè)N/4點(diǎn)的子序列。 以N/2點(diǎn)序列x1(r)為例 1314(2

8、 )( )0,1,1(21)( )4xlx lNlxlx l則有 rkNNrWrxkX212011)()(klNNllkNNlWlxWlx)12(21401221401) 12()2(lkNNlkNlkNNlWlxWWlx41404241403)()()()(42/3kXWkXkNk=0,1, 14N第16頁/共53頁第十七頁，編輯于星期六：十點(diǎn) 四十七分。18且13/24( )( )4kNNXkXkWXkk=0,1, 14N由此可見，一個(gè)N/2點(diǎn)DFT可分解成兩個(gè)N/4點(diǎn)DFT。 同理，也可對(duì)x2(n)進(jìn)行同樣的分解，求出X2(k)。 第17頁/共53頁第十八頁，編輯于星期六：十點(diǎn) 四十七分

9、。19第18頁/共53頁第十九頁，編輯于星期六：十點(diǎn) 四十七分。2013/40( )lkNlx l W02(0)(4)xW x0(0)(4)NxW x 對(duì)此例N=8，最后剩下的是4個(gè)N/4= 2點(diǎn)的DFT，2點(diǎn)DFT也可以由蝶形運(yùn)算來完成。以X3(k)為例。 /4 133/40( )( )NlkNlXkx l Wk=0, 1即03323(0)(0)(1)XxW x13323(1)(0)(1)XxW x12(0)(4)xW x0(0)(4)NxW x這說明，N=2M的DFT可全部由蝶形運(yùn)算來完成。第19頁/共53頁第二十頁，編輯于星期六：十點(diǎn) 四十七分。21N=8按時(shí)間抽取法FFT信號(hào)流圖 第2

10、0頁/共53頁第二十一頁，編輯于星期六：十點(diǎn) 四十七分。22由按時(shí)間抽取法FFT的信號(hào)流圖可知，當(dāng)N=2L時(shí)，共有 級(jí)蝶形運(yùn)算；每級(jí)都由 個(gè)蝶形運(yùn)算組成，而每個(gè)蝶形有 次復(fù)乘、 次復(fù)加，因此每級(jí)運(yùn)算都需 次復(fù)乘和 次復(fù)加。 LN/2 N/2 12N第21頁/共53頁第二十二頁，編輯于星期六：十點(diǎn) 四十七分。23這樣 級(jí)運(yùn)算總共需要： L復(fù)數(shù)乘法： NNLN2log22復(fù)數(shù)加法： NNLN2log直接DFT算法運(yùn)算量 復(fù)數(shù)乘法： 復(fù)數(shù)加法： N2N(N1)直接計(jì)算DFT與FFT算法的計(jì)算量之比為MNNNNNM222log2log2第22頁/共53頁第二十三頁，編輯于星期六：十點(diǎn) 四十七分。24N

11、N2計(jì)算量之比M NN2計(jì)算量之比M 2414.012816 38444836.641644.025665 5361 02464.0864125.4512262 1442 304113.816256328.010241 048 5765 120204.83210288012.820484 194 30411 264372.464404919221.4NN2log2NN2log2第23頁/共53頁第二十四頁，編輯于星期六：十點(diǎn) 四十七分。25n序列的逆序排列n同址運(yùn)算（原位運(yùn)算）n蝶形運(yùn)算兩節(jié)點(diǎn)間的距離n 的確定rNW第24頁/共53頁第二十五頁，編輯于星期六：十點(diǎn) 四十七分。26)(01221

12、)()(BINMMDECnnnnnn 由于 x(n) 被反復(fù)地按奇、偶分組，所以流圖輸入端的排列不再是順序的，但仍有規(guī)律可循： 因?yàn)?N=2M ， 對(duì)于任意 n（0n N-1)，可以用M個(gè)二進(jìn)制碼表示為：10,01221nnnnnMM n 反復(fù)按奇、偶分解時(shí)，即按二進(jìn)制碼的“0” “1” 分解。n序列的逆序排列第25頁/共53頁第二十六頁，編輯于星期六：十點(diǎn) 四十七分。27第26頁/共53頁第二十七頁，編輯于星期六：十點(diǎn) 四十七分。28自然順序自然順序 n二進(jìn)制數(shù)二進(jìn)制數(shù)倒位序二進(jìn)制數(shù)倒位序二進(jìn)制數(shù)倒位序順序數(shù)倒位序順序數(shù)000000001001100420100102301111064100

13、0011510110156110011371111117 n第27頁/共53頁第二十八頁，編輯于星期六：十點(diǎn) 四十七分。29第28頁/共53頁第二十九頁，編輯于星期六：十點(diǎn) 四十七分。30 某一列任何兩個(gè)節(jié)點(diǎn)k 和j 的節(jié)點(diǎn)變量進(jìn)行蝶形運(yùn)算后，得到結(jié)果為下一列k、j兩節(jié)點(diǎn)的節(jié)點(diǎn)變量，而和其他節(jié)點(diǎn)變量無關(guān)。這種原位運(yùn)算結(jié)構(gòu)可以節(jié)省存儲(chǔ)單元，降低設(shè)備成本。)(kX)2(NkX)(1kX)(2kXkNW運(yùn)算前運(yùn)算后)2(NkA)(kA)2(NkA)(kA例n同址運(yùn)算（原位運(yùn)算）第29頁/共53頁第三十頁，編輯于星期六：十點(diǎn) 四十七分。31第30頁/共53頁第三十一頁，編輯于星期六：十點(diǎn) 四十七分。3

14、2以N=8為例：第一級(jí)蝶形，距離為：第二級(jí)蝶形，距離為：第三級(jí)蝶形，距離為：規(guī)律：對(duì)于共L級(jí)的蝶形而言，其m級(jí)蝶形運(yùn)算的節(jié) 點(diǎn)間的距離為12412mn蝶形運(yùn)算兩節(jié)點(diǎn)間的距離 第31頁/共53頁第三十二頁，編輯于星期六：十點(diǎn) 四十七分。33rNW以N=8為例：0,10224/jWWWWmjjNrNm時(shí)，1 , 0,2422/jWWWWmjjjNrNm時(shí)，3 , 2 , 1 , 0,382jWWWWmjjjNrNm時(shí)，級(jí)：第LNM,212 , 2 , 1 , 0,12LjrNjWWLMLMLMLN2222LMLMMLMLjNjNjjNjjNrNWeeWW222222rNWn 的確定 第32頁/共5

15、3頁第三十三頁，編輯于星期六：十點(diǎn) 四十七分。34再把輸出X(k)按k的奇偶分組先把輸入按n的順序分成前后兩半設(shè)序列長(zhǎng)度為N=2L，L為整數(shù) 前半子序列x(n) 后半子序列)2(Nnx 0n12N0n12N第33頁/共53頁第三十四頁，編輯于星期六：十點(diǎn) 四十七分。3510( )( )NnkNnX kx n W由DFT定義得/2 110/2( )( )NNnknkNNnn Nx n Wx n W12/0)2(12/0)2()(NnkNnNNnnkNWNnxWnx12/02)2()(NnnkNkNNWWNnxnxk=0，1， ，N第34頁/共53頁第三十五頁，編輯于星期六：十點(diǎn) 四十七分。36由

16、于 1222jNNjNNeeW/2 120( )( )()2NNknkNNnNX kx nx nWW所以kkNNW) 1(2則 12/0)2() 1()()(NnnkNkWNnxnxkXk=0，1， ，N第35頁/共53頁第三十六頁，編輯于星期六：十點(diǎn) 四十七分。37然后按k的奇偶可將X(k)分為兩部分 221krkrr=0，1， ，12N則式 12/0)2() 1()()(NnnkNkWNnxnxkX可轉(zhuǎn)化為 nrNNnWNnxnxrX212/0)2()()2(12/02/)2()(NnnrNWNnxnx)12(12/0)2()() 12(rnNNnWNnxnxrXnrNnNNnWWNnxn

17、x212/0)2()(第36頁/共53頁第三十七頁，編輯于星期六：十點(diǎn) 四十七分。38/2 1/20(2 )( )()2NnrNnNXrx nx nW令 nNWNnxnxnxNnxnxnx)2()()()2()()(21n=0，1， ，12N代入 /2 120(21) ( )()2NnnrNNnNXrx nx nWWnrNNnnrNNnWnxrWnxr2120221201)() 12()()2(r=0，1， ，12N可得為2個(gè)N/2點(diǎn)的DFT，合起來正好是N點(diǎn)X(k)的值。第37頁/共53頁第三十八頁，編輯于星期六：十點(diǎn) 四十七分。39nNWNnxnxnxNnxnxnx)2()()()2()(

18、)(21將稱為蝶形運(yùn)算與時(shí)間抽選基2FFT算法中的蝶形運(yùn)算符號(hào)略有不同。第38頁/共53頁第三十九頁，編輯于星期六：十點(diǎn) 四十七分。40例 按頻率抽取，將N點(diǎn)DFT分解為兩個(gè)N/2點(diǎn)DFT的組合(N=8) 第39頁/共53頁第四十頁，編輯于星期六：十點(diǎn) 四十七分。41 與時(shí)間抽取法的推導(dǎo)過程一樣，由于 N=2L，N/2仍然是一個(gè)偶數(shù)，因而可以將每個(gè)N/2點(diǎn)DFT的輸出再分解為偶數(shù)組與奇數(shù)組，這就將N/2點(diǎn)DFT進(jìn)一步分解為兩個(gè)N/4點(diǎn)DFT。 N=8第40頁/共53頁第四十一頁，編輯于星期六：十點(diǎn) 四十七分。42第41頁/共53頁第四十二頁，編輯于星期六：十點(diǎn) 四十七分。43MN 2IDFT公

19、式 10)(1NknkNWkXNkXIDFTnxDFT公式 nkNNnWnxnxDFTkX10)()()(比較可以看出， nkNWnkNWMN211IDFT多出M個(gè)1/2可分解到M級(jí)蝶形運(yùn)算中。第42頁/共53頁第四十三頁，編輯于星期六：十點(diǎn) 四十七分。44第43頁/共53頁第四十四頁，編輯于星期六：十點(diǎn) 四十七分。4510)(1)(NknkNWkXNkXIDFT10)(1NknkNWkXN10)(1NknkNWkXN1( )( )IFFT X kFFT XkN( )X k 求共軛( )XkFFT 求( )FFT Xk( )FFT XkN 除以( )x n 求共軛第44頁/共53頁第四十五頁，

20、編輯于星期六：十點(diǎn) 四十七分。46n在在Matlab中使用的線性調(diào)頻中使用的線性調(diào)頻z變換函數(shù)為變換函數(shù)為czt，其調(diào)用格式為其調(diào)用格式為nX= czt(x, M, W, A)n其中，其中，x是待變換的時(shí)域信號(hào)是待變換的時(shí)域信號(hào)x(n)，其長(zhǎng)度為，其長(zhǎng)度為N，M是是變換的長(zhǎng)度，變換的長(zhǎng)度，W確定變換的步長(zhǎng)，確定變換的步長(zhǎng)，A確定變換的起確定變換的起點(diǎn)。若點(diǎn)。若M= N，A= 1，則，則CZT變成變成DFT。第45頁/共53頁第四十六頁，編輯于星期六：十點(diǎn) 四十七分。47例5.1 設(shè)模擬信號(hào) ，以 tn (n=0: N-1) 進(jìn)行取樣，試用fft函數(shù)對(duì)其做頻譜分析。N分別為：(1) N=45；(

21、2) N=50；(3) N=55；(2) N=60。 ( )2sin(4)5cos(8)x ttt程序清單如下 %計(jì)算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(FFT N=45)第46頁/共53頁第四十七頁，編輯于星期六：十點(diǎn) 四十七分。48%計(jì)算N=50的FFT并繪出其幅頻曲線N=50;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,2