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

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

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

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

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

5、WrxkXkNrrkkNrrkNNNN211021012222 1022102122)()(NNrrkNkNrrkNWrxWWrx第第4 4章章 快速傅立葉變換（快速傅立葉變換（FFTFFT）第6頁/共79頁 (1) X(1) X1 1 (k),X(k),X2 2 (k)(k)均為N/2N/2點的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 個，即前一半的結(jié)果。 10102210101122222222122NNNNNNNNrrkrrkr

6、rkrrkWrxWrxkXWrxWrxkX)()()()()()(第第4 4章章 快速傅立葉變換（快速傅立葉變換（FFTFFT）第7頁/共79頁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頁/共79頁實現(xiàn)上式運算的流圖稱作蝶形運算（N/2個蝶形)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頁/共79頁圖4.2.1 蝶形運算符號 CABA BCA BC第第4 4章章 快速傅立葉變換（快速傅立葉變換（FFTFFT）第10頁/共79頁)(/kXDFTN142，得得點點的的進進行行 3 , 2 , 1 , 0)2()()(30430411 kWrxWrxkXrrkrr

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

9、點DFT2N)3()2() 1 ()0(1111XXXX)1()0(2xx )3()1(2xx )5()2(2xx )7()3(2xx 點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一個一個N N點點DFTDFT分解為兩個分解為兩個N N/2/2點點DFTDFT的信號流圖的信號流圖 3 , 2 , 1 , 0),()()4()()()(2121 kkXWkXkXkXWkXkXkNkN第13頁/共79頁圖4.2.2 N點DFT的一次時域抽取分解圖(N=8) N/2點DFTWN0N

10、/2點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頁/共79頁經(jīng)過一次分解后，計算1個N點DFT共需要計算兩個N/2點DFT和N/2個蝶形運算。而計算一個N/2點DFT需要(N/2)2次復(fù)數(shù)乘法和N/2(N/21)次復(fù)數(shù)加法。所以，計算N點DFT時，總共需要的復(fù)數(shù)乘法次數(shù)為 221122222()NNNN NN222122NNNN第第4 4章

11、章 快速傅立葉變換（快速傅立葉變換（FFTFFT）第15頁/共79頁 由于由于N=2N=2M M , ,所以所以 N/2N/2仍為偶數(shù)仍為偶數(shù), ,可以進一步把每個可以進一步把每個N/2N/2點的點的序列再按其奇偶部分分解為兩個序列再按其奇偶部分分解為兩個N/4N/4的子序列。的子序列。( (二) N/4) N/4點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頁/共79頁式中 /4 133/43/40/4 144/44/40( )( )( )( )( )( )NklNNiNklNNiXkx l WDFT x lXkx l WDFT x l 同理，由X3(k)和X4(k)的周期性和Wm N/2的對稱性 Wk+N/4 N/2=-Wk N/2 最后得到： 132413240 14 14/( )( )( ), ,/(/ )( )( )kNkNX kXkWXkkNX kNXkWXk(4.2.10) 第

13、第4 4章章 快速傅立葉變換（快速傅立葉變換（FFTFFT）第17頁/共79頁用同樣的方法可計算出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頁/共79頁)0()0(1xx )2()1(1xx )4(

14、)2(1xx )6()3(1xx 點DFT2N)3()2() 1 ()0(1111XXXX)1()0(2xx )3()1(2xx )5()2(2xx )7()3(2xx 點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頁/共79頁) 0() 0(1xx ) 2() 1 (1xx ) 4() 2(1xx ) 6() 3(1xx 點DFT2N) 3 () 2 () 1 () 0 (1111XXXX第第4 4章章 快速

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

16、 kNXkWXk第21頁/共79頁奇中偶奇中奇)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點點4NDFT點點4N第第4 4章章 快速傅立葉變換（快速傅立葉變換（FFTFFT）第22頁/共79頁) 0 () 0 (1xx ) 2() 1 (1xx ) 4 () 2(1xx ) 6 () 3(1xx 點DFT2N) 1 () 0 (2xx ) 3() 1 (2xx ) 5 () 2(

17、2xx ) 7 () 3(2xx 點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 點點DFT4N 點點DFT4N) 0 () 0 () 0 (

18、13xxx ) 4() 2() 1 (13xxx ) 2 () 1 () 0 (14xxx ) 6 () 3 () 1 (14xxx ) 1 () 0 (33XX) 1 () 0 (44XX02NW12NW 點點DFT4N-1 點點DFT4N第第4 4章章 快速傅立葉變換（快速傅立葉變換（FFTFFT）第23頁/共79頁) 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 點點DFT4N-1 點點DFT4N 點點DFT4N 點點DFT4N一個一個N N=8=8點點DFTDFT分解為四個分解為四個N N/4/4點點DFTDF

20、T的信號流圖的信號流圖 第24頁/共79頁圖4.2.3 N點DFT的第二次時域抽取分解圖(N=8) N/4點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點DFTN/4點DFTN/4點DFTWN02WN02第第4 4章章 快速傅立葉變換（快速傅立葉變換（FFTFFT）第25頁/共79頁)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點DFTDFT第第4 4章章 快速傅立葉變換（快速傅立葉變換（FFTFFT）第26頁/共79頁)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頁/共79頁) 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 點點DFT4N 點點DFT4N 點點DFT4N 點點DFT4N0NW-10NW-10NW-1第第4 4章章 快速傅立葉變換（快速傅立葉變換（FFTFFT）第28頁/共79頁 圖4.2.4 N點DITFFT運算流圖(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頁/共79頁4.2.3 DITFFT4.2.3 DITFFT算法與直接計算DFTDFT運算量的比較l 每一級運算都需要N/2次復(fù)數(shù)乘和N次復(fù)數(shù)加(每個蝶形需要兩次復(fù)數(shù)加法)。所以，M級運算總共需要的復(fù)數(shù)乘次數(shù)為2222loglogMANNCMNCN MNN復(fù)數(shù)加次數(shù)為 例如，N=210=1024時221048576204.8(/2)l

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

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

27、蝶形運算規(guī)律 設(shè)序列x(n)經(jīng)時域抽選(倒序)后，存入數(shù)組X中。如果蝶形運算的兩個輸入數(shù)據(jù)相距B個點，應(yīng)用原位計算，則蝶形運算可表示成如下形式： 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 下標L表示第L級運算，AL(J)則表示第L級運算后數(shù)組元素A(J)的值。而AL1(J)表示第L級運算前A(J)的值（即第L級蝶形的輸入數(shù)據(jù)）第34頁/共79頁 4. 4. 編程思想及程序框圖編程思想及程序框圖圖4.2.6 DITFFT運算和程序框圖 開

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

29、倒序二進制數(shù)對照表 第37頁/共79頁 圖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頁/共79頁 圖4.2.9 倒序程序框圖 221NNLHJNLHI1 , N1I JTJAJXIAIXT)()()()(J KLHK KJJ2KKKJJNNY第39頁/共79頁 算法原理算法原理 10)()(NnnkNWnxkX 12/10)()(2NNnnkNnnkNWn

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

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

32、Nnxnx -1-1nNW)2(Nnx)(nx第第4 4章章 快速傅立葉變換（快速傅立葉變換（FFTFFT）第44頁/共79頁圖4.2.10 DIFFFT蝶形運算流圖符號 第第4 4章章 快速傅立葉變換（快速傅立葉變換（FFTFFT）第45頁/共79頁 N=8 N=8時時, ,按按k k的奇偶分解過程先蝶形運算的奇偶分解過程先蝶形運算, ,后作后作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點點2DFTN點點21NW2

33、NW3NW0NW第第4 4章章 快速傅立葉變換（快速傅立葉變換（FFTFFT）第46頁/共79頁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點DFT- -1 1- -1 12NW0NW- -1 1- -1 12點DFT2點DFT2點DFT第47頁/共79頁- -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頁/共79頁圖4.2.11 DIFFFT一次分解運算流圖(N=8) N/2點DFTWN0N/2點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、頁/共79頁圖4.2.12 DIFFFT二次分解運算流圖(N=8) N/4點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點DFTN/4點DFTN/4點DFT第50頁/共79頁圖4.2.13 DIFFFT運算流圖(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頁/共79頁 FFTFFT算

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

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

38、率抽取的頻率抽取的FFT運算用于運算用于IDFT運算時，也應(yīng)改運算時，也應(yīng)改變?yōu)闀r間抽取的變?yōu)闀r間抽取的IFFT。第第4 4章章 快速傅立葉變換（快速傅立葉變換（FFTFFT）第54頁/共79頁圖4.2.16 DITIFFT運算流圖 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頁/共79頁圖4.2.17 DITIFFT運算流圖(防止溢出) 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頁/共79頁nkNNkWkXNnx 10)(1)(此DFT可用FFT程序v 利用利用FFT計算計算IFFT的思路的思路2nkNNkWkXNnx 10*)(1)(取共軛再取共軛）取共軛再取共軛）()(1)(*10*nkNNkWkXNnx *)(1kXDFTN 直接

40、調(diào)用FFT子程序計算IFFT的方法：共軛FFT共軛乘1/ N( )X k*( )Xk( )x n第第4 4章章 快速傅立葉變換（快速傅立葉變換（FFTFFT）第57頁/共79頁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例：有限長序x(n)=1,2,-1,3按FFT運算流圖求X(k)，在由X(k) 按IFFT反求x(n)DFT過程：第第4 4章章 快速傅立葉變換（快速傅立葉變換（FFTFFT）第58頁/共79頁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過程：04WjW 14-1-104W-104W-11/41/41/41/4第第4 4章章 快速傅立葉變換（快速傅立葉變換（FFTFFT）第59頁/共79頁由DIT-FFT運算流圖已得出結(jié)論，N=2M點FFT共需要MN/2次復(fù)數(shù)乘法。由(4.2.12)式，當(dāng)L=1時，只有一種旋轉(zhuǎn)因子 ，所以，第一級不需要乘法運算。當(dāng)L=2 時，共有兩個旋轉(zhuǎn)因子： 和 ，因此，第二級也不需要乘法運算。在DFT中，又稱其值為1和j

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

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

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

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

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

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

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

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

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