數(shù)字信號(hào)處理快速傅立葉變換PPT課件

1、4.1 4.1 引引 言言DFTDFT是數(shù)字信號(hào)分析與處理中的一種重要變換。但直接計(jì)算DFTDFT的計(jì)算量與變換區(qū)間長(zhǎng)度N N的平方成正比，當(dāng)N N較大時(shí)，計(jì)算量太大，所以在快速傅里葉變換FFT(Fast Fourier Transform)FFT(Fast Fourier Transform)出現(xiàn)以前，直接用DFTDFT算法進(jìn)行譜分析和信號(hào)的實(shí)時(shí)處理是不切實(shí)際的。直到19651965年提出DFTDFT的一種快速算法以后，情況才發(fā)生了根本的變化。第第4 4章章 快速傅立葉變換（快速傅立葉變換（FFTFFT）第1頁(yè)/共79頁(yè)4.2 4.2 基基2FFT2FFT算法算法 4.2.1 4.2.1 直

2、接計(jì)算DFTDFT的特點(diǎn)及減少運(yùn)算量的基本途徑1, 1 , 0 ,)()(10 NkWnxkXNnnkN 101, 1 , 0 ,)(1)(NknkNNnWkXNnx兩者的差別僅在指數(shù)的符號(hào)和因子兩者的差別僅在指數(shù)的符號(hào)和因子1/N.1/N.1. 1. 直接計(jì)算直接計(jì)算DFTDFT的運(yùn)算量的運(yùn)算量第第4 4章章 快速傅立葉變換（快速傅立葉變換（FFTFFT）第2頁(yè)/共79頁(yè) 計(jì)算一個(gè)計(jì)算一個(gè)X(k)X(k)的值：的值： N N次復(fù)數(shù)乘法運(yùn)算次復(fù)數(shù)乘法運(yùn)算 N-1 N-1 次復(fù)數(shù)加法運(yùn)算次復(fù)數(shù)加法運(yùn)算. .一個(gè)一個(gè)X(k)X(k)的值的工作量的值的工作量, ,如如X(1)X(1)1210) 1(

3、)2() 1 ()0() 1 ( NNNNNWNxWxWxWxXN N點(diǎn)點(diǎn)DFTDFT運(yùn)算量：運(yùn)算量：復(fù)數(shù)乘法：復(fù)數(shù)乘法： N N2 2 復(fù)數(shù)加法：復(fù)數(shù)加法： N(N-1)N(N-1)第第4 4章章 快速傅立葉變換（快速傅立葉變換（FFTFFT）第3頁(yè)/共79頁(yè)2 2 改進(jìn)的途徑改進(jìn)的途徑的對(duì)稱性、周期性、可約性的對(duì)稱性、周期性、可約性nkNW.),1( 1)2/(2/2kNNkNjNNNWWeWWN nkNnkNWW *)(對(duì)稱性: :mnkmNnmkmNnkNWWW可約性: :周期性: :) 1()(2)()( nkNnNNkNnkNknNNkNnNeWWWWW第第4 4章章 快速傅立葉變

4、換（快速傅立葉變換（FFTFFT）第4頁(yè)/共79頁(yè)4.2.2 4.2.2 時(shí)域抽取法基2FFT2FFT基本原理 10)()()(NnnkNWnxnxDFTkX 算法原理算法原理1, 1 , 0 ),() 12 (1, 1 , 0 ),()2 (2221 NNrrxrxrrxrx第第4 4章章 快速傅立葉變換（快速傅立葉變換（FFTFFT）第5頁(yè)/共79頁(yè) 10)12(10222)12()2(NNrkrNrrkNWrxWrx 1010)()()(NnNnnkNnkNWnxWnxkX(n為偶數(shù)) (n為奇數(shù))222)/(222NNNWeeWjjN 因?yàn)椋阂驗(yàn)椋?()()()()(kXWkXWrxW

5、WrxkXkNrrkkNrrkNNNN211021012222 1022102122)()(NNrrkNkNrrkNWrxWWrx第第4 4章章 快速傅立葉變換（快速傅立葉變換（FFTFFT）第6頁(yè)/共79頁(yè) (1) X(1) X1 1 (k),X(k),X2 2 (k)(k)均為N/2N/2點(diǎn)的DFTDFT。 (2) X(k)=X(2) X(k)=X1 1 (k)+W(k)+WN Nk k X X2 2 (k)(k)只能確定出X(k)X(k)的k= 0.1k= 0.1.N/2-1 .N/2-1 個(gè)，即前一半的結(jié)果。 10102210101122222222122NNNNNNNNrrkrrkr

6、rkrrkWrxWrxkXWrxWrxkX)()()()()()(第第4 4章章 快速傅立葉變換（快速傅立葉變換（FFTFFT）第7頁(yè)/共79頁(yè)3.X(k)3.X(k)的后一半的確的后一半的確定定)()2(11kXkNX )()2(22kXkNX 由于X1(k)和X2(k)均以N/2為周期，得)2()2()2(2)2(1NkXWNkXNkXNkN kNkNNWWWN 21, 1 , 0 )()()2k(221 NkNkkXWkXNX第第4 4章章 快速傅立葉變換（快速傅立葉變換（FFTFFT）第8頁(yè)/共79頁(yè)實(shí)現(xiàn)上式運(yùn)算的流圖稱作蝶形運(yùn)算（N/2個(gè)蝶形)122, 1 ,0k )()()(122

7、, 1 ,0k ()()(2121 NkXWkXkXNkXWkXkXkNkN后一半后一半）前一半）前一半(前一半)()()(kXWkXkXkN21(后一半)()()2(21kXWkXkNXkN 1 1 11-1-1)(1kX)(2kXkNW1次 復(fù)乘2次復(fù)加第第4 4章章 快速傅立葉變換（快速傅立葉變換（FFTFFT）第9頁(yè)/共79頁(yè)圖4.2.1 蝶形運(yùn)算符號(hào) CABA BCA BC第第4 4章章 快速傅立葉變換（快速傅立葉變換（FFTFFT）第10頁(yè)/共79頁(yè))(/kXDFTN142，得得點(diǎn)點(diǎn)的的進(jìn)進(jìn)行行 3 , 2 , 1 , 0)2()()(30430411 kWrxWrxkXrrkrr

8、k);()(),()(),()(),()(634221001111xxxxxxxx );6(),4(),2(),0(xxxx(1)n為偶數(shù)時(shí)為偶數(shù)時(shí), 記作記作:第11頁(yè)/共79頁(yè));()(),()(),()(),()(735231102222xxxxxxxx 3 , 2 , 1 , 0)12()()(30430422 kWrxWrxkXrrkrrk)(/kXDFTN242，得得點(diǎn)點(diǎn)的的進(jìn)進(jìn)行行 3 , 2 , 1 , 0),()()4()()()(2121 kkXWkXkXkXWkXkXkNkN第12頁(yè)/共79頁(yè))0()0(1xx )2()1(1xx )4()2(1xx )6()3(1xx

9、點(diǎn)DFT2N)3()2() 1 ()0(1111XXXX)1()0(2xx )3()1(2xx )5()2(2xx )7()3(2xx 點(diǎn)DFT2N)3()2() 1 ()0(2222XXXX)0(X)4(X0NW) 1 (X)5(X1NW)2(X)6(X2NW)3(X)7(X3NW-1-1-1-1一個(gè)一個(gè)N N點(diǎn)點(diǎn)DFTDFT分解為兩個(gè)分解為兩個(gè)N N/2/2點(diǎn)點(diǎn)DFTDFT的信號(hào)流圖的信號(hào)流圖 3 , 2 , 1 , 0),()()4()()()(2121 kkXWkXkXkXWkXkXkNkN第13頁(yè)/共79頁(yè)圖4.2.2 N點(diǎn)DFT的一次時(shí)域抽取分解圖(N=8) N/2點(diǎn)DFTWN0N

10、/2點(diǎn)DFTWN1WN2WN3x(0)X1(0)x(2)x(4)x(6)x(1)x(3)x(5)x(7)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)第第4 4章章 快速傅立葉變換（快速傅立葉變換（FFTFFT）第14頁(yè)/共79頁(yè)經(jīng)過(guò)一次分解后，計(jì)算1個(gè)N點(diǎn)DFT共需要計(jì)算兩個(gè)N/2點(diǎn)DFT和N/2個(gè)蝶形運(yùn)算。而計(jì)算一個(gè)N/2點(diǎn)DFT需要(N/2)2次復(fù)數(shù)乘法和N/2(N/21)次復(fù)數(shù)加法。所以，計(jì)算N點(diǎn)DFT時(shí)，總共需要的復(fù)數(shù)乘法次數(shù)為 221122222()NNNN NN222122NNNN第第4 4章

11、章 快速傅立葉變換（快速傅立葉變換（FFTFFT）第15頁(yè)/共79頁(yè) 由于由于N=2N=2M M , ,所以所以 N/2N/2仍為偶數(shù)仍為偶數(shù), ,可以進(jìn)一步把每個(gè)可以進(jìn)一步把每個(gè)N/2N/2點(diǎn)的點(diǎn)的序列再按其奇偶部分分解為兩個(gè)序列再按其奇偶部分分解為兩個(gè)N/4N/4的子序列。的子序列。( (二) N/4) N/4點(diǎn)DFTDFT3241( )(2 ),0,1,1( )(21)4x lxlNlx lxl那么，X1(k)又可表示為 /4 1/4 12(21)11/21/200/4 1/4 13/4/24/4003/24( )(2 )(21)( )( )( )( ),0,1,/ 4 1NNklklN

12、NiiNNklkklNNNiikNX kxl WxlWx l WWx l WXkWXk kN第第4 4章章 快速傅立葉變換（快速傅立葉變換（FFTFFT）第16頁(yè)/共79頁(yè)式中 /4 133/43/40/4 144/44/40( )( )( )( )( )( )NklNNiNklNNiXkx l WDFT x lXkx l WDFT x l 同理，由X3(k)和X4(k)的周期性和Wm N/2的對(duì)稱性 Wk+N/4 N/2=-Wk N/2 最后得到： 132413240 14 14/( )( )( ), ,/(/ )( )( )kNkNX kXkWXkkNX kNXkWXk(4.2.10) 第

13、第4 4章章 快速傅立葉變換（快速傅立葉變換（FFTFFT）第17頁(yè)/共79頁(yè)用同樣的方法可計(jì)算出25/2625/26( )( )( ),0,1,/4 1(/4)( )( )kNkNXkX kWXkkNXkNX kWXk(4.2.11)其中 5262/4 155/450/4 166/460( )(2 ),0,1,/ 4 1( )(21)( )( )( )( )( )( )NklNiNklNix lxllNx lxlXkx l WDFT x lXkx l WDFT x l第第4 4章章 快速傅立葉變換（快速傅立葉變換（FFTFFT）第18頁(yè)/共79頁(yè))0()0(1xx )2()1(1xx )4(

14、)2(1xx )6()3(1xx 點(diǎn)DFT2N)3()2() 1 ()0(1111XXXX)1()0(2xx )3()1(2xx )5()2(2xx )7()3(2xx 點(diǎn)DFT2N)3()2() 1 ()0(2222XXXX)0(X)4(X0NW) 1 (X)5(X1NW)2(X)6(X2NW)3(X)7(X3NW-1-1-1-1第第4 4章章 快速傅立葉變換（快速傅立葉變換（FFTFFT）第19頁(yè)/共79頁(yè)) 0() 0(1xx ) 2() 1 (1xx ) 4() 2(1xx ) 6() 3(1xx 點(diǎn)DFT2N) 3 () 2 () 1 () 0 (1111XXXX第第4 4章章 快速

15、傅立葉變換（快速傅立葉變換（FFTFFT）第20頁(yè)/共79頁(yè)偶中偶偶中奇)0()0()0(13xxx )4()2()1(13xxx )2()1()0(14xxx )6()3()1(14xxx ) 1 () 0 (33XX) 1 () 0 (44XX02NW12NWDFT點(diǎn)點(diǎn)4N-1) 0 (1X) 2 (1X-1) 1 (1X) 3 (1XN/2N/2點(diǎn)點(diǎn)DFTDFT分解為兩個(gè)分解為兩個(gè)N/4N/4點(diǎn)點(diǎn)DFTDFT的信號(hào)流圖的信號(hào)流圖 DFT點(diǎn)點(diǎn)4N第第4 4章章 快速傅立葉變換（快速傅立葉變換（FFTFFT）132413244/( )( )( )(/ )( )( )kNkNX kXkWXkX

16、 kNXkWXk第21頁(yè)/共79頁(yè)奇中偶奇中奇)1()0()0(55xxx )5()2()1(25xxx )3()1()0(26xxx )7()3()1(26xxx ) 1 () 0 (55XX) 1 () 0 (66XX02NW12NW-1) 0 (2X) 2 (2X-1) 1 (2X) 3 (2XDFT點(diǎn)點(diǎn)4NDFT點(diǎn)點(diǎn)4N第第4 4章章 快速傅立葉變換（快速傅立葉變換（FFTFFT）第22頁(yè)/共79頁(yè)) 0 () 0 (1xx ) 2() 1 (1xx ) 4 () 2(1xx ) 6 () 3(1xx 點(diǎn)DFT2N) 1 () 0 (2xx ) 3() 1 (2xx ) 5 () 2(

17、2xx ) 7 () 3(2xx 點(diǎn)DFT2N) 3 () 2 () 1 () 0 (1111XXXX) 3 () 2 () 1 () 0 (2222XXXX) 0 (X) 4 (X0NW) 1 (X) 5 (X1NW) 2 (X) 6 (X2NW) 3 (X) 7 (X3NW-1-1-1-1) 1 () 0 () 0 (55xxx ) 5 () 2() 1 (25xxx ) 3 () 1 () 0 (26xxx ) 7 () 3() 1 (26xxx ) 1 () 0 (55XX) 1 () 0 (66XX02NW12NW-1-1 點(diǎn)點(diǎn)DFT4N 點(diǎn)點(diǎn)DFT4N) 0 () 0 () 0 (

18、13xxx ) 4() 2() 1 (13xxx ) 2 () 1 () 0 (14xxx ) 6 () 3 () 1 (14xxx ) 1 () 0 (33XX) 1 () 0 (44XX02NW12NW 點(diǎn)點(diǎn)DFT4N-1 點(diǎn)點(diǎn)DFT4N第第4 4章章 快速傅立葉變換（快速傅立葉變換（FFTFFT）第23頁(yè)/共79頁(yè)) 1 () 0 () 0 (55xxx ) 5 () 2() 1 (25xxx ) 3 () 1 () 0 (26xxx ) 7 () 3() 1 (26xxx ) 3 () 2 () 1 () 0 (1111XXXX) 3 () 2 () 1 () 0 (2222XXXX)

19、 0 (X) 4 (X0NW) 1 (X) 5 (X1NW) 2 (X) 6 (X2NW) 3 (X) 7 (X3NW-1-1-1-1-1) 1 () 0 (55XX) 1 () 0 (66XX0NW2NW-1-1) 0 () 0 () 0 (13xxx ) 4() 2() 1 (13xxx ) 2 () 1 () 0 (14xxx ) 6 () 3 () 1 (14xxx ) 1 () 0 (33XX) 1 () 0 (44XX0NW2NW 點(diǎn)點(diǎn)DFT4N-1 點(diǎn)點(diǎn)DFT4N 點(diǎn)點(diǎn)DFT4N 點(diǎn)點(diǎn)DFT4N一個(gè)一個(gè)N N=8=8點(diǎn)點(diǎn)DFTDFT分解為四個(gè)分解為四個(gè)N N/4/4點(diǎn)點(diǎn)DFTDF

20、T的信號(hào)流圖的信號(hào)流圖 第24頁(yè)/共79頁(yè)圖4.2.3 N點(diǎn)DFT的第二次時(shí)域抽取分解圖(N=8) N/4點(diǎn)DFTWN12WN12WN0WN1WN2WN3X1(0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)x(0)X3(0)X3(1)X4(0)X4(1)x(4)x(2)x(6)x(1)x(5)x(3)x(7)N/4點(diǎn)DFTN/4點(diǎn)DFTN/4點(diǎn)DFTWN02WN02第第4 4章章 快速傅立葉變換（快速傅立葉變換（FFTFFT）第25頁(yè)/共79頁(yè))4()0()1()0()1()4()0()1()0()0(

21、03330333xWxxxXxWxxxXNN )6()2()1()0()1()6()2()1()0()0(04440444xWxxxXxWxxxXNN ( (三) N/4) N/4點(diǎn)DFTDFT第第4 4章章 快速傅立葉變換（快速傅立葉變換（FFTFFT）第26頁(yè)/共79頁(yè))5() 1 () 1 ()0() 1 ()5() 1 () 1 ()0()0(05550555xWxxxXxWxxxXNN ) 7 () 3() 1 () 0 () 1 () 7 () 3() 1 () 0 () 0 (06660666xWxxxXxWxxxXNN 第第4 4章章 快速傅立葉變換（快速傅立葉變換（FFTFF

22、T）第27頁(yè)/共79頁(yè)) 1 () 0 () 0 (55xxx ) 5 () 2() 1 (25xxx ) 3 () 1 () 0 (26xxx ) 7 () 3() 1 (26xxx ) 0 () 0 () 0 (13xxx ) 4() 2() 1 (13xxx ) 2 () 1 () 0 (14xxx ) 6 () 3 () 1 (14xxx ) 3 () 2 () 1 () 0 (1111XXXX) 3 () 2 () 1 () 0 (2222XXXX) 0 (X) 4 (X0NW) 1 (X) 5 (X1NW) 2 (X) 6 (X2NW) 3 (X) 7 (X3NW-1-1-1-1)

23、 1 () 0 (33XX) 1 () 0 (44XX0NW2NW-1-1) 1 () 0 (55XX) 1 () 0 (66XX0NW2NW-1-10NW-1 點(diǎn)點(diǎn)DFT4N 點(diǎn)點(diǎn)DFT4N 點(diǎn)點(diǎn)DFT4N 點(diǎn)點(diǎn)DFT4N0NW-10NW-10NW-1第第4 4章章 快速傅立葉變換（快速傅立葉變換（FFTFFT）第28頁(yè)/共79頁(yè) 圖4.2.4 N點(diǎn)DITFFT運(yùn)算流圖(N=8) WN0WN1WN2WN3WN0WN2WN0WN2WN0WN0WN0WN0 x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(0)A(

24、1)A(2)A(3)A(4)A(5)A(6)A(7)A(0)A(7)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)第第4 4章章 快速傅立葉變換（快速傅立葉變換（FFTFFT）第29頁(yè)/共79頁(yè)4.2.3 DITFFT4.2.3 DITFFT算法與直接計(jì)算DFTDFT運(yùn)算量的比較l 每一級(jí)運(yùn)算都需要N/2次復(fù)數(shù)乘和N次復(fù)數(shù)加(每個(gè)蝶形需要兩次復(fù)數(shù)加法)。所以，M級(jí)運(yùn)算總共需要的復(fù)數(shù)乘次數(shù)為2222loglogMANNCMNCN MNN復(fù)數(shù)加次數(shù)為 例如，N=210=1024時(shí)221048576204.8(/2)l

25、og5120NNN第第4 4章章 快速傅立葉變換（快速傅立葉變換（FFTFFT）第30頁(yè)/共79頁(yè)圖4.2.5 FFT算法與直接計(jì)算DFT所需乘法次數(shù)的比較曲線 第第4 4章章 快速傅立葉變換（快速傅立葉變換（FFTFFT）第31頁(yè)/共79頁(yè) 1. 1.原位計(jì)算原位計(jì)算 由圖4.2.4可以看出，DITFFT的運(yùn)算過(guò)程很有規(guī)律。N=2M點(diǎn)的FFT共進(jìn)行M級(jí)運(yùn)算，每級(jí)由N/2個(gè)蝶形運(yùn)算組成。在N點(diǎn)DIT-FFT運(yùn)算流圖中，每級(jí)都有N/2個(gè)蝶形。每個(gè)蝶形都要乘以因子，稱其為旋轉(zhuǎn)因子，p為旋轉(zhuǎn)因子的指數(shù)。但各級(jí)的旋轉(zhuǎn)因子和循環(huán)方式都有所不同。為了編寫(xiě)計(jì)算程序，應(yīng)先找出旋轉(zhuǎn)因子與運(yùn)算級(jí)數(shù)的關(guān)系。用L表示

26、從左到右的運(yùn)算級(jí)數(shù)(L=1，2，M)。觀察圖4.2.4不難發(fā)現(xiàn)，第L級(jí)共有2L1個(gè)不同的旋轉(zhuǎn)因子。N=23=8時(shí)的各級(jí)旋轉(zhuǎn)因子表示如下：pNWpNW 4.2.4 DITFFT的運(yùn)算規(guī)律及編程思想 2 2旋轉(zhuǎn)因子的變化規(guī)律旋轉(zhuǎn)因子的變化規(guī)律第32頁(yè)/共79頁(yè)對(duì)N=2M的一般情況，第L級(jí)的旋轉(zhuǎn)因子為3,2, 1,0 31,0 20 1222/24/JWWWLJWWWLJWWWLJJNpNJJNpNJJNpNLLL時(shí)時(shí)時(shí)2120 1 2212, , ,M LL MPJJLNNNMLWWWJpJ12,0,1,2,212222LpJLNLML ML MWWJN第33頁(yè)/共79頁(yè) 3. 3. 蝶形運(yùn)算規(guī)律

27、蝶形運(yùn)算規(guī)律 設(shè)序列x(n)經(jīng)時(shí)域抽選(倒序)后，存入數(shù)組X中。如果蝶形運(yùn)算的兩個(gè)輸入數(shù)據(jù)相距B個(gè)點(diǎn)，應(yīng)用原位計(jì)算，則蝶形運(yùn)算可表示成如下形式： AL (J) AL - 1(J)+A L -1(J+B)WpN AL(J+B) AL - 1(J)-A L -1(J+B)WpN 式中 p=J2 M-L；J=0,1,，2 L-1-1；L=1,2,，M 下標(biāo)L表示第L級(jí)運(yùn)算，AL(J)則表示第L級(jí)運(yùn)算后數(shù)組元素A(J)的值。而AL1(J)表示第L級(jí)運(yùn)算前A(J)的值（即第L級(jí)蝶形的輸入數(shù)據(jù)）第34頁(yè)/共79頁(yè) 4. 4. 編程思想及程序框圖編程思想及程序框圖圖4.2.6 DITFFT運(yùn)算和程序框圖 開(kāi)

28、 始送入x(n)， MN2 M倒 序L1 , M0 , B 1P2 M LJk J , N1 , 2LpNpNWBkXkXBkXWBkXkXkX)()()()()()(輸 出結(jié) 束B(niǎo) 2 L1第35頁(yè)/共79頁(yè) DITFFT算法的輸入序列的排序看起來(lái)似乎很亂，但仔細(xì)分析就會(huì)發(fā)現(xiàn)這種倒序是很有規(guī)律的。由于N=2M，所以順序數(shù)可用M位二進(jìn)制數(shù)(nM-1nM-2n1n0)表示。 圖4.2.7 形成倒序的樹(shù)狀圖(N=23) 01010101010101(n2n1n0)2000042615371000101100011010111115. 5. 序列的倒序序列的倒序第36頁(yè)/共79頁(yè)表4.2.1 順序和

29、倒序二進(jìn)制數(shù)對(duì)照表 第37頁(yè)/共79頁(yè) 圖4.2.8 倒序規(guī)律 x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)第38頁(yè)/共79頁(yè) 圖4.2.9 倒序程序框圖 221NNLHJNLHI1 , N1I JTJAJXIAIXT)()()()(J KLHK KJJ2KKKJJNNY第39頁(yè)/共79頁(yè) 算法原理算法原理 10)()(NnnkNWnxkX 12/10)()(2NNnnkNnnkNWn

30、xWnxN 10)(10222)2()(NNNnknNnnkNWNnxWnx第第4 4章章 快速傅立葉變換（快速傅立葉變換（FFTFFT）第40頁(yè)/共79頁(yè)nkNnkNWWNnxnxNN 1022)2()(, 12 jNeWNkkNNW)( 12 nkNnkWNnxnxkXN 102)2()1()()(1, 1 ,0Nk第第4 4章章 快速傅立葉變換（快速傅立葉變換（FFTFFT）第41頁(yè)/共79頁(yè)nrNnWNnxnxrXN2102)2()()2( k k為偶數(shù)時(shí)：nrnNNWNnxnx2210)2()( 1, 1 , 02 Nr)(1nxk k為奇數(shù)時(shí)：nrnnNNNWWNnxnx2210)

31、2()( )(2nx1, 1 , 02 Nr)12(102)2()()12( rnNnWNnxnxrXN第第4 4章章 快速傅立葉變換（快速傅立葉變換（FFTFFT）第42頁(yè)/共79頁(yè)1, 1 ,0 )2()()()2()()(221 NnNnWNnxnxnxNnxnxnx1,1,0 )()12()()2(21202120122 NnrNnnrNnrWnxrXWnxrXNN第第4 4章章 快速傅立葉變換（快速傅立葉變換（FFTFFT）第43頁(yè)/共79頁(yè))2()()(1Nnxnxnx 1, 1 , 02 NnnNWNnxnxnx )2()()(2進(jìn)行如下碟形運(yùn)算：進(jìn)行如下碟形運(yùn)算：和和)2()(

32、Nnxnx -1-1nNW)2(Nnx)(nx第第4 4章章 快速傅立葉變換（快速傅立葉變換（FFTFFT）第44頁(yè)/共79頁(yè)圖4.2.10 DIFFFT蝶形運(yùn)算流圖符號(hào) 第第4 4章章 快速傅立葉變換（快速傅立葉變換（FFTFFT）第45頁(yè)/共79頁(yè) N=8 N=8時(shí)時(shí), ,按按k k的奇偶分解過(guò)程先蝶形運(yùn)算的奇偶分解過(guò)程先蝶形運(yùn)算, ,后作后作DFT:DFT:- -1 1- -1 1-1-1- -1 1)0( x) 1 ( x)5( x)4( x) 3( x)2( x)7( x)6( x)0(X)4(X)6(X) 1 (X)5(X)3(X)7(X)2(XDFTN點(diǎn)點(diǎn)2DFTN點(diǎn)點(diǎn)21NW2

33、NW3NW0NW第第4 4章章 快速傅立葉變換（快速傅立葉變換（FFTFFT）第46頁(yè)/共79頁(yè)X(0)X(6)X(4)X(2)X(1)X(5)X(3)X(7)0NW1NW2NW3NW- -1 1- -1 1- -1 1- -1 1x(0)x(3)x(1)x(2)x(4)x(5)x(6)x(7)0NW2NW2點(diǎn)DFT- -1 1- -1 12NW0NW- -1 1- -1 12點(diǎn)DFT2點(diǎn)DFT2點(diǎn)DFT第47頁(yè)/共79頁(yè)- -1 1- -1 1- -1 1- -1 1- -1 1- -1 1- -1 1- -1 1- -1 1- -1 1- -1 1- -1 1)0( x) 1 ( x)5(

34、 x)4( x) 3( x)2( x)7( x)6( x)0(X)2(X)6(X) 1 (X) 3(X)5(X)7(X)4(X1NW2NW3NW0NW2NW0NW0NW2NW0NW0NW0NW0NW第第4 4章章 快速傅立葉變換（快速傅立葉變換（FFTFFT）第48頁(yè)/共79頁(yè)圖4.2.11 DIFFFT一次分解運(yùn)算流圖(N=8) N/2點(diǎn)DFTWN0N/2點(diǎn)DFTWN1WN2WN3X(0)x1(0)X(2)X(4)X(6)X(1)X(3)X(5)X(7)x1(1)x1(2)x1(3)x2(0)x2(1)x2(2)x2(3)x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)第49

35、頁(yè)/共79頁(yè)圖4.2.12 DIFFFT二次分解運(yùn)算流圖(N=8) N/4點(diǎn)DFTWN0WN1WN2WN3x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)X(0)X(4)X(2)X(6)X(1)X(5)X(3)X(7)WN0WN2WN0WN2N/4點(diǎn)DFTN/4點(diǎn)DFTN/4點(diǎn)DFT第50頁(yè)/共79頁(yè)圖4.2.13 DIFFFT運(yùn)算流圖(N=8) WN0WN1WN2WN3WN0WN2WN0WN2WN0WN0WN0WN0X(0)X(4)X(2)X(6)X(1)X(5)X(3)X(7)x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)第51頁(yè)/共79頁(yè) FFTFFT算

36、法的特點(diǎn)算法的特點(diǎn)l分級(jí)運(yùn)算分級(jí)運(yùn)算l同址運(yùn)算同址運(yùn)算l倒序輸入，順序輸出倒序輸入，順序輸出(DIT),(DIT),正序輸入，正序輸入，倒序輸出倒序輸出(DIF)(DIF)lDIT-FFTDIT-FFT蝶形先乘后加蝶形先乘后加( (減減) )，而，而DIF- DIF- FFTFFT蝶形先加蝶形先加( (減減) )后相乘。后相乘。第第4 4章章 快速傅立葉變換（快速傅立葉變換（FFTFFT）第52頁(yè)/共79頁(yè)v 利用利用FFT計(jì)算計(jì)算IFFT的思路的思路1 1 10)(1)()(NknkNWkXNkXIDFTnxIDFTFFTNWWDFTnkNnkN算法都可以用來(lái)運(yùn)算算法都可以用來(lái)運(yùn)算或頻率抽取

37、或頻率抽取抽取抽取）那么以上討論的時(shí)間）那么以上討論的時(shí)間（將運(yùn)算結(jié)果都除以將運(yùn)算結(jié)果都除以改成改成運(yùn)算中的每個(gè)系數(shù)運(yùn)算中的每個(gè)系數(shù)只要把只要把3)2()1( 10)()()(NknkNWnxnxDFTkX第第4 4章章 快速傅立葉變換（快速傅立葉變換（FFTFFT）第53頁(yè)/共79頁(yè)把把FFT的時(shí)間抽取法，用于的時(shí)間抽取法，用于IDFT運(yùn)算時(shí)，由于運(yùn)算時(shí)，由于輸入變量由時(shí)間序列輸入變量由時(shí)間序列x(n)改成頻率序列改成頻率序列X(k)，原原來(lái)按來(lái)按x(n)的奇、偶次序分組的時(shí)間抽取法的奇、偶次序分組的時(shí)間抽取法FFT，現(xiàn)在就變成了按現(xiàn)在就變成了按X(k)的奇偶次序抽取了。的奇偶次序抽取了。頻

38、率抽取的頻率抽取的FFT運(yùn)算用于運(yùn)算用于IDFT運(yùn)算時(shí)，也應(yīng)改運(yùn)算時(shí)，也應(yīng)改變?yōu)闀r(shí)間抽取的變?yōu)闀r(shí)間抽取的IFFT。第第4 4章章 快速傅立葉變換（快速傅立葉變換（FFTFFT）第54頁(yè)/共79頁(yè)圖4.2.16 DITIFFT運(yùn)算流圖 WN0WN1WN2WN3WN0WN0N1x(0)x(4)x(2)x(6)x(4)x(5)x(3)x(7)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)WN2WN2N1N1N1N1N1N1N1第第4 4章章 快速傅立葉變換（快速傅立葉變換（FFTFFT）第55頁(yè)/共79頁(yè)圖4.2.17 DITIFFT運(yùn)算流圖(防止溢出) WN02121x(0)x(

39、4)x(2)x(6)x(1)x(5)x(3)x(7)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)212121WN121WN221WN3212121WN021WN2212121WN021WN22121WN02121WN0212121WN021WN021第第4 4章章 快速傅立葉變換（快速傅立葉變換（FFTFFT）第56頁(yè)/共79頁(yè)nkNNkWkXNnx 10)(1)(此DFT可用FFT程序v 利用利用FFT計(jì)算計(jì)算IFFT的思路的思路2nkNNkWkXNnx 10*)(1)(取共軛再取共軛）取共軛再取共軛）()(1)(*10*nkNNkWkXNnx *)(1kXDFTN 直接

40、調(diào)用FFT子程序計(jì)算IFFT的方法：共軛FFT共軛乘1/ N( )X k*( )Xk( )x n第第4 4章章 快速傅立葉變換（快速傅立葉變換（FFTFFT）第57頁(yè)/共79頁(yè)1) 0( x1) 2 ( x2) 1 ( x3) 3 ( x5) 0 ( XjX 2) 1 (5) 2 ( XjX 2)3(2)1(0)0(11XX1) 1 (5) 0(22 XX04WjW 14-1-104W-104W-1例：有限長(zhǎng)序x(n)=1,2,-1,3按FFT運(yùn)算流圖求X(k)，在由X(k) 按IFFT反求x(n)DFT過(guò)程：第第4 4章章 快速傅立葉變換（快速傅立葉變換（FFTFFT）第58頁(yè)/共79頁(yè)1)

41、 0( x1) 2( x2) 1 ( x3) 3 ( x5) 0 ( XjX 2) 1 (5) 2 ( XjX 2)3(10)1(0)0(11xxjxx2) 1 (4) 0(22 IDFT過(guò)程：04WjW 14-1-104W-104W-11/41/41/41/4第第4 4章章 快速傅立葉變換（快速傅立葉變換（FFTFFT）第59頁(yè)/共79頁(yè)由DIT-FFT運(yùn)算流圖已得出結(jié)論，N=2M點(diǎn)FFT共需要MN/2次復(fù)數(shù)乘法。由(4.2.12)式，當(dāng)L=1時(shí)，只有一種旋轉(zhuǎn)因子 ，所以，第一級(jí)不需要乘法運(yùn)算。當(dāng)L=2 時(shí)，共有兩個(gè)旋轉(zhuǎn)因子： 和 ，因此，第二級(jí)也不需要乘法運(yùn)算。在DFT中，又稱其值為1和j

42、的旋轉(zhuǎn)因子為無(wú)關(guān)緊要的旋轉(zhuǎn)因子，如 ， ， 等。10NW10NWjWNN4/0NW2/NNW4/NNW第第4 4章章 快速傅立葉變換（快速傅立葉變換（FFTFFT）第60頁(yè)/共79頁(yè)先除去第一、二兩級(jí)后，所需復(fù)數(shù)乘法次數(shù)應(yīng)是0NW4/NNW當(dāng)L=3時(shí)，有兩個(gè)無(wú)關(guān)緊要的旋轉(zhuǎn)因子和，因?yàn)橥恍D(zhuǎn)因子對(duì)應(yīng)著2ML=N/2L個(gè)碟形運(yùn)算，所以第三級(jí)共有2N/23=N/4 個(gè)碟形不需要復(fù)數(shù)乘法運(yùn)算。依此類推，當(dāng)L3時(shí)，第L級(jí)的2個(gè)無(wú)關(guān)緊要的旋轉(zhuǎn)因子減少?gòu)?fù)數(shù)乘法的次數(shù)為2N/2L=N/2L1。這樣，從L=3至L=M共減少?gòu)?fù)數(shù)乘法次數(shù)為 (2)2MNCM(4.3.1)第第4 4章章 快速傅立葉變換（快速傅立葉

43、變換（FFTFFT）第61頁(yè)/共79頁(yè)(4.3.2)222122331NNNMLLMLL 下面再討論FFT中特殊的復(fù)數(shù)運(yùn)算，以便進(jìn)一步減少?gòu)?fù)數(shù)乘法次數(shù)。一般實(shí)現(xiàn)一次復(fù)數(shù)乘法運(yùn)算需要四次實(shí)數(shù)乘，兩次實(shí)數(shù)加。但對(duì)這一特殊復(fù)數(shù)，任一復(fù)數(shù)(x+jy)與其相乘時(shí)，2/2)1 (8/jWNN因此，DIT-FFT的復(fù)乘次數(shù)降至(2)2(3)2222MNNNCMM(4.3.3)第第4 4章章 快速傅立葉變換（快速傅立葉變換（FFTFFT）第62頁(yè)/共79頁(yè)IRyxyxyxyxyxj)( j)(22)jj(22)j)(j1 (22def)(22)(22)(22xyyxIyxR第第4 4章章 快速傅立葉變換（快速

44、傅立葉變換（FFTFFT）第63頁(yè)/共79頁(yè)只需要兩次實(shí)數(shù)加和兩次實(shí)數(shù)乘就可實(shí)現(xiàn)。這樣，對(duì)應(yīng)的每個(gè)蝶形節(jié)省兩次實(shí)數(shù)乘。在DIT-FFT運(yùn)算流圖中，從L=3至L=M級(jí)，每級(jí)都包含旋轉(zhuǎn)因子 ，第L級(jí)中， 對(duì)應(yīng)N/2L個(gè)蝶形運(yùn)算。因此從第三級(jí)至最后一級(jí)，旋轉(zhuǎn)因子 節(jié)省的實(shí)數(shù)乘次數(shù)與(4.3.2)式相同。所以從實(shí)數(shù)乘運(yùn)算考慮，計(jì)算N=2M點(diǎn)DIT-FFT所需實(shí)數(shù)乘法次數(shù)為 8/NNW8/NNW8/NNW8/NNW(4.3.4)134(3)22210222MNNRMNM第第4 4章章 快速傅立葉變換（快速傅立葉變換（FFTFFT）第64頁(yè)/共79頁(yè)若包含了所有旋轉(zhuǎn)因子，則稱該算法為一類碟形單元運(yùn)算；1m

45、NW 若去掉的旋轉(zhuǎn)因子，則稱之為二類碟形單元運(yùn) 算；(1j) 2 /2mNW若再判斷處理，則稱之為四類碟形運(yùn)算。jWrN若再去掉的旋轉(zhuǎn)因子，則稱為三類碟形單元運(yùn)算；后三種運(yùn)算稱為多類碟形單元運(yùn)算。顯然，碟形單元類型越多，編程就越復(fù)雜，但當(dāng)N較大時(shí)，乘法運(yùn)算的減少量是相當(dāng)可觀的。例如，N=4096時(shí)，三類碟形單元運(yùn)算的乘法次數(shù)為一類碟形單元運(yùn)算的75%。 第第4 4章章 快速傅立葉變換（快速傅立葉變換（FFTFFT）第65頁(yè)/共79頁(yè)l在FFT運(yùn)算中，旋轉(zhuǎn)因子l，求正弦和余弦函數(shù)值的計(jì)算量是很大的。所以編程時(shí)，產(chǎn)生旋轉(zhuǎn)因子的方法直接影響運(yùn)算速度。)/cos(NmWmN2 )/sin(Nmj2 l

46、產(chǎn)生旋轉(zhuǎn)因子的方法產(chǎn)生旋轉(zhuǎn)因子的方法: :l1. 在每級(jí)運(yùn)算中直接產(chǎn)生；mNWl2.在FFT程序開(kāi)始前預(yù)先計(jì)算出，m = 0，1，N/21， 存放在數(shù)組中，作為旋轉(zhuǎn)因子表，在程序執(zhí)行過(guò)程中直接查表得到所需旋轉(zhuǎn)因子值，不再計(jì)算。這樣使運(yùn)算速度大大提高，其不足之處是占用內(nèi)存較多。第第4 4章章 快速傅立葉變換（快速傅立葉變換（FFTFFT）第66頁(yè)/共79頁(yè)在實(shí)際工作中，數(shù)據(jù)x(n)常常是實(shí)數(shù)序列。如果直接按FFT運(yùn)算流圖計(jì)算，就是把x(n)看成一個(gè)虛部為零的復(fù)序列進(jìn)行計(jì)算，這就增加了存儲(chǔ)量和運(yùn)算時(shí)間。 l處理該問(wèn)題的方法有三種處理該問(wèn)題的方法有三種: :l早期提出的方法是用一個(gè)N點(diǎn)FFT計(jì)算兩個(gè)

47、N點(diǎn)實(shí)序列的FFT，一個(gè)實(shí)序列作為x(n)的實(shí)部，另一個(gè)作為虛部，計(jì)算完FFT后，根據(jù)DFT的共軛對(duì)稱性，由輸出X(k)分別得到兩個(gè)實(shí)序列的N點(diǎn)DFT。l第二種方法是用N/2點(diǎn)FFT計(jì)算一個(gè)N點(diǎn)實(shí)序列的DFT。l第三種方法是用離散哈特萊變換（DHT）1。第第4 4章章 快速傅立葉變換（快速傅立葉變換（FFTFFT）第67頁(yè)/共79頁(yè)設(shè)x(n)為N點(diǎn)實(shí)序列，取x(n)的偶數(shù)點(diǎn)和奇數(shù)點(diǎn)分別作為新構(gòu)造序列y(n)的實(shí)部和虛部，即12121222121 N10nnx jnxnyN10nnxnxnxnx，)()()()()()()(112212( )DFT( )( )0,1,( )DFT( )( )ep

48、opX kx nYkNkXkx njYk 對(duì)y(n)進(jìn)行N/2點(diǎn)FFT，輸出Y(k)，則用用N/2N/2點(diǎn)點(diǎn)FFTFFT計(jì)算一個(gè)計(jì)算一個(gè)N N點(diǎn)實(shí)序列的點(diǎn)實(shí)序列的DFTDFT的原理：的原理：第第4 4章章 快速傅立葉變換（快速傅立葉變換（FFTFFT）第68頁(yè)/共79頁(yè)由于x(n)為實(shí)序列，因此X(k)具有共軛對(duì)稱性，X(k)的另外N/2點(diǎn)的值為：)0(2 ),0(22211XNXXNX1210)()(*NkkXkNX，12N根據(jù)DIT-FFT的思想及式(4.2.7)和(4.2.8)，可得到X(k)的前 個(gè)值：210)()()(21NkkXWkXkXkN，(4.3.5)其中：第第4 4章章 快

49、速傅立葉變換（快速傅立葉變換（FFTFFT）第69頁(yè)/共79頁(yè) 計(jì)算 點(diǎn)FFT的復(fù)乘次數(shù)為 ，計(jì)算式(4.3.5)的復(fù)乘次數(shù)為，所以用這種算法, 計(jì)算X(k)所需復(fù)數(shù)乘法次數(shù)為。相對(duì)一般的N點(diǎn)FFT算法，上述算法的運(yùn)算效率為，當(dāng)N=2M=210時(shí)，=20/11，運(yùn)算速度提高近1倍。2N) 1(4MN2N) 1(42) 1(4MNNMN) 1/(2) 1(4/2MMMNMN第第4 4章章 快速傅立葉變換（快速傅立葉變換（FFTFFT）第70頁(yè)/共79頁(yè) 本章僅介紹算法最簡(jiǎn)單、編程最容易的基2FFT算法原理及其編程思想，使讀者建立快速傅里葉變換的基本概念，了解研究FFT算法的主要途徑和編程思路。其

50、他高效快速算法請(qǐng)讀者參考文獻(xiàn)1、3、12。例如，分裂基FFT算法、離散哈特萊變(換DHT)、基4FFT、基8FFT、基rFFT、混合基FFT，以及進(jìn)一步減少運(yùn)算量的途徑等內(nèi)容，對(duì)研究新的快速算法都是很有用的。本節(jié)簡(jiǎn)要介紹其他幾種快速算法的運(yùn)算量及其主要特點(diǎn)，以便讀者選擇快速算法時(shí)參考。第第4 4章章 快速傅立葉變換（快速傅立葉變換（FFTFFT）第71頁(yè)/共79頁(yè)l從理論上講，不同基數(shù)的FFT算法的運(yùn)算效率不同，實(shí)際中最常用的是基2FFT、基4 FFT、分裂基FFT和DHT 1。為此，下面簡(jiǎn)要介紹后三種FFT算法的特點(diǎn)和運(yùn)算效率，以擴(kuò)展讀者的視野。其具體算法請(qǐng)參考文獻(xiàn)1、12。l在基rFFT算法中，基4FFT算法運(yùn)算效率與基8FFT很接近，但基4FFT算法實(shí)現(xiàn)程序簡(jiǎn)單，且判斷開(kāi)銷少?？梢宰C明，當(dāng)FFT的基大于4時(shí)，不會(huì)明顯降低計(jì)算量?；?FFT要求N=4M，M為自然數(shù)。其復(fù)數(shù)乘法次數(shù)為12（4.4.1）