-第章快速傅里葉變換

1、2022-1-1Ch.4 FFT1n直接計算直接計算DFT的問題及改進的途徑的問題及改進的途徑 2022-1-1Ch.4 FFT2 2022-1-1Ch.4 FFT3 設復序列設復序列x(n) 長度為長度為N點，其點，其DFT為為10( )( )NnkNnX kx n Wk=0，N-1 （1）計算一個）計算一個X(k) 值的運算量值的運算量復數(shù)乘法次數(shù)：復數(shù)乘法次數(shù)： N復數(shù)加法次數(shù)：復數(shù)加法次數(shù)： N12022-1-1Ch.4 FFT4（2）計算全部）計算全部N個個X(k) 值的運算量值的運算量復數(shù)乘法次數(shù)：復數(shù)乘法次數(shù)： N2復數(shù)加法次數(shù)：復數(shù)加法次數(shù)： N(N1)（3）對應的實數(shù)運算量）

2、對應的實數(shù)運算量1100( )( )Re ( )Im ( )ReImNNnknknkNNNnnX kx n Wx njx nWjW10Re ( ) ReIm ( ) ImNnknkNNnx nWx nWRe ( ) ImIm ( ) RenknkNNjx nWx nW2022-1-1Ch.4 FFT5一次復數(shù)乘法一次復數(shù)乘法： 4次實數(shù)乘法次實數(shù)乘法 2次實數(shù)加法次實數(shù)加法 一個一個X(k) ：4N次實數(shù)乘法次實數(shù)乘法 2N+2(N-1)= 2(2N-1)次實數(shù)加法次實數(shù)加法 所以所以 整個整個N點點DFT運算共需要：運算共需要：N2(2N-1)= 2N(2N-1)實數(shù)乘法次數(shù)：實數(shù)乘法次數(shù)：

3、4 N2實數(shù)加法次數(shù)：實數(shù)加法次數(shù)：2022-1-1Ch.4 FFT6N點點DFT的復數(shù)乘法次數(shù)舉例的復數(shù)乘法次數(shù)舉例NN2NN22464404941612816384864256 65 536 16256512 262 144 3210281024 1 048 576 結論結論：當：當N很大時，其運算量很大，對實時性很強的信號很大時，其運算量很大，對實時性很強的信號處理來說，要求計算速度快，因此需要改進處理來說，要求計算速度快，因此需要改進DFT的計算的計算方法，以大大減少運算次數(shù)。方法，以大大減少運算次數(shù)。 2022-1-1Ch.4 FFT7 nkNW主要原理是利用系數(shù)主要原理是利用系數(shù)

4、的以下特性對的以下特性對DFT進行分解：進行分解： nkNW（1）對稱性）對稱性 ()nkNW()k N nNW（2）周期性）周期性 ()()n N kn k NnkNNNWWW（3）可約性）可約性 mnknkmNNWW/nknk mNN mWW另外，另外，12/NNWkNNkNWW)2/(2022-1-1Ch.4 FFT8授課思路授課思路2022-1-1Ch.4 FFT91(2 )( )xrx r設設N2L，將，將x(n)按按 n 的奇偶分為兩組：的奇偶分為兩組： 2(21)( )xrx rr =0，1， 12N10( ) ( )( )NnkNnX kDFT x nx n W則則1010)(

5、)(NnnnkNNnnnkNWnxWnx為奇數(shù)為偶數(shù)120)12(1202) 12()2(NrkrNNrrkNWrxWrx2022-1-1Ch.4 FFT10120)12(1202) 12()2(NrkrNNrrkNWrxWrx1202212021)()(NrrkNkNNrrkNWrxWWrx)()(21kXWkXkN1010)()(NnnnkNNnnnkNWnxWnx為奇數(shù)為偶數(shù)式中，式中，X1(k)和和X2(k)分別是分別是x1(n)和和x2(n)的的N/2的的DFT。另外，式中另外，式中k的取值范圍是：的取值范圍是：0，1， ，N/21 。2022-1-1Ch.4 FFT11因此，因此，

6、 只能計算出只能計算出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()( )2NXkXk2022-1-1Ch.4 FFT12考慮到考慮到 kNkNNNkNNWWWW2)2(因此可得后半部分因此可得后半部分X(k) )2()2()2(221NkXWNkXNkXNkN12( )( )( )kNX kX kW Xk及前半部

7、分及前半部分X(k) )()(21kXWkXkNk=0，1， ，N/21k=0，1， ，N/212022-1-1Ch.4 FFT1312( )( )( )kNX kX kW Xk12( )( )( )kNX kX kW Xk蝶形運算式蝶形運算式蝶形運算信蝶形運算信號流圖符號號流圖符號 因此，只要求出因此，只要求出2個個N/2點的點的DFT，即，即X1(k)和和X2(k)，再，再經(jīng)過蝶形運算就可求出全部經(jīng)過蝶形運算就可求出全部X(k)的值，運算量大大減少。的值，運算量大大減少。2022-1-1Ch.4 FFT14以以N=8為例，為例，分解為分解為2個個4點點的的DFT，然后，然后做做8/2=4次

8、蝶形次蝶形運算即可求出運算即可求出所有所有8點點X(k)的的值。值。2022-1-1Ch.4 FFT15復數(shù)乘法次數(shù)： N2復數(shù)加法次數(shù)： N(N1)復數(shù)乘法次數(shù)： 2*(N/2)2+N/2=N2/2+N/2復數(shù)加法次數(shù)： 2*(N/2)(N/21)+2*N/2=N2/2nN點 2022-1-1Ch.4 FFT16 由于N2L，因而N/2仍是偶數(shù) ，可以進一步把每個N/2點子序列再按其奇偶部分分解為兩個N/4點的子序列。 以N/2點序列x1(r)為例 1314(2 )( )0,1,1(21)( )4xlx lNlxlx l則有 rkNNrWrxkX212011)()(klNNllkNNlWlx

9、Wlx)12(21401221401) 12()2(4 14 13444002( )( )NNNlkklkNNllx l WWx l W/234( )( )NkXkWXkk=0,1, 14N2022-1-1Ch.4 FFT17且且13/24( )( )4kNNXkXkWXkk=0,1, 14N由此可見，一個由此可見，一個N/2點點DFT可分解成兩個可分解成兩個N/4點點DFT。 同理，也可對同理，也可對x2(n)進行同樣的分解，求出進行同樣的分解，求出X2(k)。 2022-1-1Ch.4 FFT182022-1-1Ch.4 FFT1913/40( )lkNlx l W02(0)(4)xW x

10、0(0)(4)NxW x 對此例對此例N=8，最后剩下的是，最后剩下的是4個個N/4= 2點的點的DFT，2點點DFT也可以由蝶形運算來完成。以也可以由蝶形運算來完成。以X3(k)為例。為例。 /4 133/40( )( )NlkNlXkx l Wk=0, 1即即03323(0)(0)(1)XxW x13323(1)(0)(1)XxW x21(0)(4)xW x0(0)(4)NxW x這說明，這說明，N=2M的的DFT可全部由蝶形運算來完成?？扇坑傻芜\算來完成。2022-1-1Ch.4 FFT20N=8按時間抽取法按時間抽取法FFT信號流圖信號流圖 2022-1-1Ch.4 FFT21由按

11、時間抽取法FFT的信號流圖可知，當N=2L時，共有 級蝶形運算；每級都由 個蝶形運算組成，而每個蝶形有 次復乘、 次復加，因此每級運算都需 次復乘和 次復加。 LN/2 N/2 12N2022-1-1Ch.4 FFT22這樣這樣 級運算總共需要：級運算總共需要： L復數(shù)乘法： NNLN2log22復數(shù)加法： NNLN2log直接直接DFT算法運算量算法運算量 復數(shù)乘法： 復數(shù)加法： N2N(N1)直接計算直接計算DFT與與FFT算法的計算量之比為算法的計算量之比為MNNNNNM222log2log22022-1-1Ch.4 FFT23NN2計算量之比M NN2計算量之比M 2414.01281

12、6 38444836.641644.025665 5361 02464.0864125.4512262 1442 304113.816256328.010241 048 5765 120204.83210288012.820484 194 30411 264372.464404919221.4NN2log2NN2log22022-1-1Ch.4 FFT24n序列的逆序排列n同址運算（原位運算）n蝶形運算兩節(jié)點間的距離n 的確定rNW算法特點概述2022-1-1Ch.4 FFT25)(01221)()(BINMMDECnnnnnn 由于由于 x(n) 被反復地按奇、偶分組，所以流圖輸被反復地按奇

13、、偶分組，所以流圖輸入端的入端的排列不再是順序的，但仍有規(guī)律可循：排列不再是順序的，但仍有規(guī)律可循： 因為因為 N=2M ， 對于任意對于任意 n（0n N-1)，可以用可以用M個個二進制碼表示為：二進制碼表示為：10,01221nnnnnMM n 反復按奇、偶分解時，即按二進制碼的反復按奇、偶分解時，即按二進制碼的“0” “1” 分解。分解。n序列的逆序排列2022-1-1Ch.4 FFT262022-1-1Ch.4 FFT27自然順序自然順序 n二進制數(shù)二進制數(shù)倒位序二進制數(shù)倒位序二進制數(shù)倒位序順序數(shù)倒位序順序數(shù)000000001001100420100102301111064100001

14、1510110156110011371111117 n2022-1-1Ch.4 FFT282022-1-1Ch.4 FFT29 某一列任何兩個節(jié)點某一列任何兩個節(jié)點k 和和j 的節(jié)點變量進行蝶形運算的節(jié)點變量進行蝶形運算后，得到結果為下一列后，得到結果為下一列k、j兩節(jié)點的節(jié)點變量，而和其他兩節(jié)點的節(jié)點變量，而和其他節(jié)點變量無關。這種原位運算結構可以節(jié)省存儲單元，節(jié)點變量無關。這種原位運算結構可以節(jié)省存儲單元，降低設備成本。降低設備成本。運算前運算前運算后運算后)2(NkA)(kA)2(NkA)(kA例例n同址運算（原位運算）2022-1-1Ch.4 FFT302022-1-1Ch.4 FFT

15、31以以N=8為例：為例：第一級蝶形，距離為：第一級蝶形，距離為：第二級蝶形，距離為：第二級蝶形，距離為：第三級蝶形，距離為：第三級蝶形，距離為：規(guī)律規(guī)律：對于共：對于共L級的蝶形而言，其級的蝶形而言，其m級蝶形運算的節(jié)級蝶形運算的節(jié) 點間的距離為點間的距離為12412mn蝶形運算兩節(jié)點間的距離 2022-1-1Ch.4 FFT32 rNW以N=8為例：0,10224/jWWWWmjjNrNm時，1 , 0,2422/jWWWWmjjjNrNm時，3 , 2 , 1 , 0,382jWWWWmjjjNrNm時，級：第LNM,212 , 2 , 1 , 0,12LjrNjWWLMLMLMLN22

16、22LMLMMLMLjNjNjjNjjNrNWeeWW222222rNWn 的確定 2022-1-1Ch.4 FFT33n算法原理算法原理 再把輸出再把輸出X(k)按按k的奇偶分組的奇偶分組先把輸入先把輸入按按n的順序的順序分成前后兩半分成前后兩半設序列長度為設序列長度為N=2L，L為整數(shù)為整數(shù) 前半子序列前半子序列x(n) 后半子序列后半子序列 0n0n2022-1-1Ch.4 FFT3410( )( )NnkNnX kx n W由由DFT定義得定義得1/2/2 10( )( )NnknkNNNnnNx n Wx n W12/0)2(12/0)2()(NnkNnNNnnkNWNnxWnx12

17、/02)2()(NnnkNkNNWWNnxnxk=0，1， ，N2022-1-1Ch.4 FFT35由于由于 1222jNNjNNeeW/2 120( )( )()2NNknkNNnNX kx nx nWW所以所以2( 1)NkkNW 則則 /2 10( )( )( 1)()2NknkNnNX kx nx nW k=0，1， ，N2022-1-1Ch.4 FFT36然后按然后按k的奇偶可將的奇偶可將X(k)分為兩部分分為兩部分 221krkrr=0，1， ，則式則式 /2 10( )( )( 1)()2NknkNnNX kx nx nW 可轉化為可轉化為 /2 120()( )()22NnrN

18、nrNXx nx nW12/02/)2()(NnnrNWNnxnx/2 1(21)0() ( )2()21NnrNnNXx nx nWr/2 120 ( )()2NNnrNnnWNx nx nW2022-1-1Ch.4 FFT37/2 1/20(2 )( )()2NnrNnNXrx nx nW令令 nNWNnxnxnxNnxnxnx)2()()()2()()(21n=0，1， ，代入代入 /2 120(21) ( )()2NnnrNNnNXrx nx nWWnrNNnnrNNnWnxrWnxr2120221201)() 12()()2(r=0，1， ，可得可得為為2個個N/2點的點的DFT，合

19、起來正好是，合起來正好是N點點X(k)的值。的值。2022-1-1Ch.4 FFT38nNWNnxnxnxNnxnxnx)2()()()2()()(21將將稱為蝶形運算稱為蝶形運算與時間抽選基與時間抽選基2FFT算法中的蝶形運算符號略有不同。算法中的蝶形運算符號略有不同。2022-1-1Ch.4 FFT39例例 按頻率抽取，將按頻率抽取，將N點點DFT分解為兩個分解為兩個N/2點點DFT的組合的組合(N=8) 2022-1-1Ch.4 FFT40 與時間抽取法的推導過程一樣，由于與時間抽取法的推導過程一樣，由于 N=2L，N/2仍然是仍然是一個偶數(shù)，因而可以將每個一個偶數(shù)，因而可以將每個N/2

20、點點DFT的輸出再分解為偶數(shù)組的輸出再分解為偶數(shù)組與奇數(shù)組，這就將與奇數(shù)組，這就將N/2點點DFT進一步分解為兩個進一步分解為兩個N/4點點DFT。 N=82022-1-1Ch.4 FFT41n頻率抽取法輸入是自然順序，輸出是倒位序的；時間抽取法正好相反。n頻率抽取法的基本蝶形與時間抽取法的基本蝶形有所不同。n頻率抽取法運算量與時間抽取法相同。n頻率抽取法與時間抽取法的基本蝶形是互為轉置的。 2022-1-1Ch.4 FFT42MN2IDFT公式公式 10)(1NknkNWkXNkXIDFTnxDFT公式公式 nkNNnWnxnxDFTkX10)()()(比較可以看出，比較可以看出， nkNW

21、nkNWMN211IDFT多出多出M個個1/2可分解到可分解到M級蝶形運算中。級蝶形運算中。2022-1-1Ch.4 FFT432022-1-1Ch.4 FFT4410)(1)(NknkNWkXNkXIDFT10)(1NknkNWkXN10)(1NknkNWkXN1( )( )IFFT X kFFT XkN( )X k 求共軛( )XkFFT 求( )FFT Xk( )FFT XkN 除以( )x n 求共軛2022-1-1Ch.4 FFT45n用用FFT進行譜分析的進行譜分析的Matlab實現(xiàn)實現(xiàn)n用用CZT進行譜分析的進行譜分析的Matlab實現(xiàn)實現(xiàn)n在在Matlab中使用的線性調頻中使用

22、的線性調頻z變換函數(shù)為變換函數(shù)為czt，其調用，其調用格式為格式為nX= czt(x, M, W, A)n其中，其中，x是待變換的時域信號是待變換的時域信號x(n)，其長度為，其長度為N，M是變換的是變換的長度，長度，W確定變換的步長，確定變換的步長，A確定變換的起點。若確定變換的起點。若M= N，A= 1，則，則CZT變成變成DFT。2022-1-1Ch.4 FFT46例例4.1 設模擬信號設模擬信號 ，以，以 t= 0.01n (n=0: N-1) 進行取樣，試用進行取樣，試用fft函數(shù)對其做頻譜分析。函數(shù)對其做頻譜分析。N分別分別為：為：(1) N=45；(2) N=50；(3) N=5

23、5；(2) N=60。 ( )2sin(4)5cos(8)x ttt程序清單如下程序清單如下 %計算計算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)2022-1-1Ch.4 FFT47%計算計算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)plot(q,abs(y)title(FFT N=50)2022-1-1Ch.4 FFT48%計算計算N=55的的FFT并繪出其幅頻曲線并繪出其幅頻曲線N=55;n=0:N-1;t=0.01*n;q=n*2*pi/N;x=2*sin(4*pi*t)+5*cos(8