第6章 快速傅立葉變換(FFT)

1、第第6 6章章 快速傅立葉變換快速傅立葉變換(FFT)(FFT) 雖然頻譜分析和雖然頻譜分析和DFTDFT運(yùn)算很重要，但在很長(zhǎng)一段運(yùn)算很重要，但在很長(zhǎng)一段時(shí)間里，由于時(shí)間里，由于DFTDFT運(yùn)算復(fù)雜，并沒有得到真正的運(yùn)用，運(yùn)算復(fù)雜，并沒有得到真正的運(yùn)用，而頻譜分析仍大多采用模擬信號(hào)濾波的方法解決，而頻譜分析仍大多采用模擬信號(hào)濾波的方法解決，直到直到19651965年首次提出年首次提出DFTDFT運(yùn)算的一種快速算法以后，運(yùn)算的一種快速算法以后，情況才發(fā)生了根本變化，人們開始認(rèn)識(shí)到情況才發(fā)生了根本變化，人們開始認(rèn)識(shí)到DFTDFT運(yùn)算的運(yùn)算的一些內(nèi)在規(guī)律，從而很快地發(fā)展和完善了一套高速一些內(nèi)在規(guī)律，

2、從而很快地發(fā)展和完善了一套高速有效的運(yùn)算方法有效的運(yùn)算方法快速付里變換（快速付里變換（FFTFFT）算法。）算法。FFTFFT的出現(xiàn)，使的出現(xiàn)，使DFTDFT的運(yùn)算大大簡(jiǎn)化，運(yùn)算時(shí)間縮短的運(yùn)算大大簡(jiǎn)化，運(yùn)算時(shí)間縮短一二個(gè)數(shù)量級(jí)，使一二個(gè)數(shù)量級(jí)，使DFTDFT的運(yùn)算在實(shí)際中得到廣泛應(yīng)的運(yùn)算在實(shí)際中得到廣泛應(yīng)用。用。6.1 6.1 引言引言一一.DFT.DFT的計(jì)算工作量的計(jì)算工作量 兩者的差別僅在指數(shù)的符號(hào)和兩者的差別僅在指數(shù)的符號(hào)和因子因子1/N1/N. . 1, 1 , 0 ,)()(10NkWnxkXNnnkN101, 1 , 0 ,)(1)(NknkNNnWkXNnx 通常通常x(n)x

3、(n)和和都是復(fù)數(shù)都是復(fù)數(shù), ,所以計(jì)算一個(gè)所以計(jì)算一個(gè)X(k)X(k)的值需要的值需要N N次復(fù)數(shù)乘法運(yùn)算次復(fù)數(shù)乘法運(yùn)算, ,和和 次復(fù)數(shù)加法運(yùn)次復(fù)數(shù)加法運(yùn)算算. .那么那么, ,計(jì)算全部計(jì)算全部N N點(diǎn)的點(diǎn)的X(k)X(k)就要就要N N2 2次復(fù)數(shù)乘法運(yùn)次復(fù)數(shù)乘法運(yùn)算算, ,N(N-1)N(N-1)次復(fù)數(shù)加法運(yùn)算次復(fù)數(shù)加法運(yùn)算. .一般來說一般來說, ,乘法運(yùn)算乘法運(yùn)算要比相加運(yùn)算復(fù)雜要比相加運(yùn)算復(fù)雜, ,為討論簡(jiǎn)單起見為討論簡(jiǎn)單起見, ,我們以復(fù)數(shù)我們以復(fù)數(shù)乘法運(yùn)算次數(shù)近似作為運(yùn)算工作量的衡量標(biāo)準(zhǔn)乘法運(yùn)算次數(shù)近似作為運(yùn)算工作量的衡量標(biāo)準(zhǔn). .當(dāng)當(dāng)N N很大時(shí)很大時(shí), ,運(yùn)算量將是驚人的

4、運(yùn)算量將是驚人的, ,如如N=1024,N=1024,則要完則要完成成1048576 1048576 次次( (一百多萬次一百多萬次) )運(yùn)算運(yùn)算. .這樣這樣, ,難以做到難以做到實(shí)時(shí)處理實(shí)時(shí)處理. .nkNW1N一個(gè)X(k)的值的工作量,如X(1)1210) 1() 2() 1 () 0() 1 (NNNNNWNxWxWxWxX二二. .改進(jìn)的途徑改進(jìn)的途徑 1. 1. 的對(duì)稱性和周期性的對(duì)稱性和周期性nkNW;,)()()(*NknNkNnNnkNnkNnkNWWWWW.),1( 1),1()2/(2/)(2)()(2kNNkNjNNNnkNnNNkNnkNknNNkNnNWWeWWeW

5、WWWWN得:對(duì)稱性:周期性:利用上述特性利用上述特性, ,可以將有些項(xiàng)合并可以將有些項(xiàng)合并22)()()(NNNkXkXkX把把N N點(diǎn)數(shù)據(jù)分成點(diǎn)數(shù)據(jù)分成兩兩半：半：其運(yùn)算量為：其運(yùn)算量為：2)2(N2)2(N2N再分兩半：再分兩半：44)()(NNkXkX44)()(NNkXkX+=22N2)4(N2)4(N2)4(N2)4(N+=24N這樣一直分下去，剩下兩點(diǎn)的變換。這樣一直分下去，剩下兩點(diǎn)的變換。 把長(zhǎng)度為把長(zhǎng)度為N N點(diǎn)的大點(diǎn)數(shù)的點(diǎn)的大點(diǎn)數(shù)的DFTDFT運(yùn)算依次分解為若干運(yùn)算依次分解為若干個(gè)小點(diǎn)數(shù)的個(gè)小點(diǎn)數(shù)的DFTDFT。因?yàn)?。因?yàn)镈FTDFT的計(jì)算量正比于的計(jì)算量正比于N N2 2

6、，N N小，小，計(jì)算量也就小。計(jì)算量也就小。 FFT FFT算法正是基于這樣的基本思想發(fā)展起來的。算法正是基于這樣的基本思想發(fā)展起來的。19651965年年, ,庫庫利利(cooley)(cooley)和圖基和圖基(Tukey)(Tukey)首先提出首先提出FFTFFT算法算法. .對(duì)于對(duì)于N N點(diǎn)點(diǎn)DFT,DFT,僅需僅需(N/2)log(N/2)log2 2N N 次復(fù)數(shù)乘法運(yùn)算次復(fù)數(shù)乘法運(yùn)算. .例如例如N=1024=2N=1024=21010 時(shí)，需要時(shí)，需要(1024/2)log(1024/2)log2 2 2 21010 =512 =512* *10=512010=5120次。次。

7、5120/1048576=4.88%5120/1048576=4.88% , ,速速度提高度提高2020倍倍. . 應(yīng)用第三代數(shù)字信號(hào)處理器應(yīng)用第三代數(shù)字信號(hào)處理器TMS320C30-40TMS320C30-40，具有，具有50ns50ns的單的單周期執(zhí)行時(shí)間，每秒周期執(zhí)行時(shí)間，每秒2000020000次浮點(diǎn)運(yùn)算，完成乘法、加法及運(yùn)次浮點(diǎn)運(yùn)算，完成乘法、加法及運(yùn)算控制、數(shù)據(jù)存取共需約算控制、數(shù)據(jù)存取共需約1s1s左右，而采用左右，而采用FFTFFT算法，計(jì)算時(shí)間算法，計(jì)算時(shí)間可縮減為可縮減為2.366ms2.366ms。 FFT FFT有多種形式，但基本上可分為兩類：有多種形式，但基本上可分為

8、兩類：時(shí)間抽取法和頻時(shí)間抽取法和頻率抽取法率抽取法。 按按“基數(shù)基數(shù)”分：基分：基-2FFT-2FFT算法；基算法；基-4FFT-4FFT算法；混合基算法；混合基 FFTFFT算法；分裂基算法；分裂基FFTFFT算法算法 其它方法：線性調(diào)頻其它方法：線性調(diào)頻Z Z變換變換(CZT(CZT法法) ) 1. 1. 設(shè)輸入序列長(zhǎng)度為設(shè)輸入序列長(zhǎng)度為N=2N=2L L( (L L為正整數(shù)，將該為正整數(shù)，將該序列按時(shí)間順序的奇偶分解為越來越短的子序序列按時(shí)間順序的奇偶分解為越來越短的子序列，稱為基列，稱為基2 2按時(shí)間抽取的按時(shí)間抽取的FFTFFT算法。也稱為算法。也稱為Coolkey-TukeyCoo

9、lkey-Tukey算法。算法。 2. 2. 其中基數(shù)其中基數(shù)2-N=22-N=2L L，L L為整數(shù)為整數(shù). .若不滿足若不滿足這個(gè)條件，可以人為地加上若干零值（加零補(bǔ)這個(gè)條件，可以人為地加上若干零值（加零補(bǔ)長(zhǎng)）使其達(dá)到長(zhǎng)）使其達(dá)到 N=2 N=2L L6.2 6.2 按時(shí)間抽取按時(shí)間抽取(DIT)(DIT)的的FFTFFT算法算法 庫利庫利- -圖基算法圖基算法算法原理算法原理(1).N/2(1).N/2點(diǎn)點(diǎn)DFTDFT1.1.先將先將 按按n n的奇偶分為兩組作的奇偶分為兩組作DFT,DFT,這樣這樣有有: : n n為偶數(shù)時(shí)為偶數(shù)時(shí): : n n為奇數(shù)時(shí)為奇數(shù)時(shí): :1, 1 , 0

10、),() 12(1, 1 , 0 ),()2(2221NNrrxrxrrxrx10)()()(NnnkNWnxnxDFTkX因此，因此，)(nx由于由于: :所以所以, ,上式可表示為上式可表示為: :1022102110)12(10210102222)()()12()2()()()(NNNNrrkNkNrrkNrkrNrrkNNnNnnkNnkNWrxWWrxWrxWrxWnxWnxkX(n(n為偶數(shù)為偶數(shù)) ) ( (n n為奇數(shù)為奇數(shù)) )222)/(222NNNWeeWjjN)()()()()(211021012222kXWkXWrxWWrxkXkNrrkkNrrkNNNN 其中,2.

11、2.兩點(diǎn)結(jié)論: (1) X (1) X (k),X(k),X (k)(k)均為N/2N/2點(diǎn)的DFTDFT。 (2) X(k)=X (2) X(k)=X (k)+W(k)+W X X (k)(k)只能確定出 X(k) X(k)的k= k= 個(gè)；即前一半的結(jié)果。1 21 2kN10102210101122222222) 12()()()2()()(NNNNNNNNrrkrrkrrkrrkWrxWrxkXWrxWrxkX1, 1 , 02 N 同理同理, , 這就是說這就是說,X,X1 1(k),X(k),X2 2(k)(k)的后一半的后一半, ,分別分別 等于其前一半的值。等于其前一半的值。3.

12、X(k)3.X(k)的后一半的確定的后一半的確定rkkrNNNWW222)()()()()2(1101)(101122222kXWrxWrxkNXNNNNNrrkkrr由于由于 （周期性）（周期性）, ,所以所以: :)()2(22kXkNX 可見可見,X(k),X(k)的后一半，也完全由的后一半，也完全由X X1 1(k), X(k), X2 2(k)(k)的前一半所確定。的前一半所確定。 * *N N點(diǎn)的點(diǎn)的DFTDFT可由兩個(gè)可由兩個(gè)N/2N/2點(diǎn)的點(diǎn)的DFTDFT來計(jì)算。來計(jì)算。kNkNNkNWWWWNN22)()2()2()2(212NkXWNkXNkXNkN1, 1 , 0 ),(

13、)(221NkNkkXWkX又由于又由于 , ,所以所以實(shí)現(xiàn)上式運(yùn)算的流圖稱作蝶形運(yùn)算實(shí)現(xiàn)上式運(yùn)算的流圖稱作蝶形運(yùn)算 前一半4.4.蝶形運(yùn)算蝶形運(yùn)算 后一半（N/2N/2個(gè)蝶形個(gè)蝶形) )( (前一半前一半) )( (后一半后一半) )1 1 11-1-1)()()()()()(2121kXWkXkXkXWkXkXkNkN)1,()1, 1 ,0(22 N Nk kk kN NN N)()()(21kXWkXkXkN)()()2(21kXWkXkNXkN)(1kX)(2kXkNW由由X X1 1(k)(k)、X X 2 2(k)(k)表示表示X(k)X(k)的運(yùn)算是一種特殊的運(yùn)算的運(yùn)算是一種特

14、殊的運(yùn)算- -碟形運(yùn)算碟形運(yùn)算X1(k)X2(k)kNW)()(21kXWkXkN)()(21kXWkXkN作圖要素：作圖要素：(1)(1)左邊兩路為輸入左邊兩路為輸入(2)(2)右邊兩路為輸出右邊兩路為輸出(3)(3)中間以一個(gè)小圓表示加、中間以一個(gè)小圓表示加、減運(yùn)算（右上路為相加輸減運(yùn)算（右上路為相加輸出、右下路為相減輸出出、右下路為相減輸出) )(4)(4)如果在某一支路上信號(hào)需要進(jìn)行如果在某一支路上信號(hào)需要進(jìn)行相乘運(yùn)算，則在該支路上標(biāo)以箭頭，相乘運(yùn)算，則在該支路上標(biāo)以箭頭，將相乘的系數(shù)標(biāo)在箭頭旁。將相乘的系數(shù)標(biāo)在箭頭旁。(5)(5)當(dāng)支路上沒有箭頭及系當(dāng)支路上沒有箭頭及系數(shù)時(shí)，則該支路

15、的傳輸比數(shù)時(shí)，則該支路的傳輸比為為1 1。(1)N/2(1)N/2點(diǎn)的點(diǎn)的DFTDFT運(yùn)算量運(yùn)算量: :復(fù)乘次數(shù)復(fù)乘次數(shù): :復(fù)加次數(shù)復(fù)加次數(shù): :(2)(2)兩個(gè)兩個(gè)N/2N/2點(diǎn)的點(diǎn)的DFTDFT運(yùn)算量運(yùn)算量: :復(fù)乘次數(shù)復(fù)乘次數(shù): :復(fù)加次數(shù)復(fù)加次數(shù): : (3)N/2(3)N/2個(gè)蝶形運(yùn)算的運(yùn)算量個(gè)蝶形運(yùn)算的運(yùn)算量: :復(fù)乘次數(shù)復(fù)乘次數(shù): :復(fù)加次數(shù)復(fù)加次數(shù): : 5. .計(jì)算工作量分析計(jì)算工作量分析復(fù)乘復(fù)乘: :復(fù)加復(fù)加: :4)2(22NN)12(2NN22N)12(NN2NNN222)12(2NNNN22222NNN總共運(yùn)算量總共運(yùn)算量: :按奇、偶分組后的計(jì)算量：按奇、偶分組后

16、的計(jì)算量： 但是但是,N,N點(diǎn)點(diǎn)DFTDFT的復(fù)乘為的復(fù)乘為N N2 2 ; ;復(fù)加復(fù)加N(N-1);N(N-1);與分解與分解后相比可知后相比可知, ,計(jì)算工作點(diǎn)差不多減少計(jì)算工作點(diǎn)差不多減少 一半。一半。 例如 N=8 N=8 時(shí)的DFT,DFT,可以分解為兩個(gè) N/2=4N/2=4點(diǎn)的DFTDFT.具體方法如下: : (1)n(1)n為偶數(shù)時(shí),即 分別記作: :)(42/1kXDFTN，得點(diǎn)的進(jìn)行3 , 2 , 1 , 0)2()()(30430411kWrxWrxkXrrkrrk);6()3(),4()2(),2()1(),0()0(1111xxxxxxxx);6(),4(),2(),

17、0(xxxx (2) n (2) n為奇數(shù)時(shí),分別記作:);7()3(),5()2(),3()1(),1()0(2222xxxxxxxx3 , 2 , 1 , 0) 12()()(30430422kWrxWrxkXrrkrrk)(42/2kXDFTN，得點(diǎn)的進(jìn)行3 , 2 , 1 , 0),()() 4()()()(2121kkXWkXkXkXWkXkXkNkN x1 1(0)=(0)=x(0) (0) x1(1)=(1)=x(2) (2) N/2N/2點(diǎn)點(diǎn) x1(2)=(2)=x(4) DFT (4) DFT x1(3)=(3)=x(6) (6) x2(0)=(0)=x(1) (1) x2(

18、1)=(1)=x(3) (3) N/2N/2點(diǎn)點(diǎn) x2(2)=(2)=x(5) (5) DFT DFT x2(3)=(3)=x(7)(7) X X1(0)(0)X X1(1)(1)X X1(2)(2)X X1(3)(3)X X2(0)(0)X X2(1)(1)X X2(2)(2)X X2(3)(3)WN2WN1WN0WN3-1-1-1-1X(0)X(0)X(1)X(1)X(2)X(2)X(3)X(3)X(4)X(4)X(5)X(5)X(6)X(6)X(7)X(7)(3)(3)對(duì)X 1(k)X 1(k)和X 2(k)X 2(k)進(jìn)行蝶形運(yùn)算,前半部為 X(0) X(3),X(0) X(3),后半

19、部分為X(4) X(7)X(4) X(7) 整個(gè)過程如下圖所示:4點(diǎn)DFTx(0)x(2)x(4)x(6)4點(diǎn)DFTx(1)x(3)x(5)x(7)08W18W28W38WX(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)X1(0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)偶數(shù)序列奇數(shù)序列3821282118210821) 3 () 3 (3) 2() 2(2) 1 () 1 (1) 0() 0(0WXXXWXXXWXXXWXXX）（）（）（）（如：x1(r)x2(r) 由于N=2 N=2 L L , ,所以 N/2N/2仍為偶數(shù),可以進(jìn) 一步把每個(gè)N

20、/2N/2點(diǎn)的序列再按其奇偶部分 分解為兩個(gè)N/4N/4的子序列。例如，n為偶數(shù)時(shí)的 N/2N/2點(diǎn)分解為:(2).N/4(2).N/4點(diǎn)點(diǎn)DFTDFT1, 1 , 0),()2(431Nlxlx1, 1 , 0),() 12(441Nlxlx進(jìn)行N/4N/4點(diǎn)的DFTDFT,得到klNllkNllkNllkNlWlxWlxkXWlxWlxkXNNNN) 12(2/1014/104422/1014/1033) 12()()()2()()(4444( (偶中偶) )( (偶中奇) )()()(4312kXWkXkXkN1, 1 , 04Nk從而可得到前從而可得到前N/4N/4的的X X1 1(k

21、)(k)()()4(4312kXWkXkNXkN后后N/4N/4的的X X1 1(k)(k)為為1, 1 , 04Nk一個(gè)2點(diǎn)的DFT蝶形流圖2點(diǎn)DFT2點(diǎn)DFTx(0)x(4)x(2)x(6)X3(0)X3(1)X4(0)X4(1)X1(0)X1(1)X1(2)X1(3)04W14W) 1 () 1 () 1 () 0() 0() 2() 1 () 1 () 1 () 0() 0() 0(41431404314143140431XWXXXWXXXWXXXWXX其中( (奇中偶奇中偶) )104/64/1026104/5104/254444)()12()()()2()(NNNNllkNlkNl

22、llkNllkNWlxWlxkXWlxWlxkX( (奇中奇奇中奇) )同樣對(duì)同樣對(duì)n n為奇數(shù)時(shí)，為奇數(shù)時(shí)，N/2N/2點(diǎn)分為兩個(gè)點(diǎn)分為兩個(gè)N/4N/4點(diǎn)點(diǎn) 的序列進(jìn)行的序列進(jìn)行DFTDFT，則有，則有: :14, 1 , 0k; (k)XW(k) X(k) X6kN/252N14, 1 , 0k; (k)XW(k) Xk)4N( X6kN/252N進(jìn)行碟形運(yùn)算，得：、由)()(65kXkX另一個(gè)另一個(gè)2 2點(diǎn)的點(diǎn)的DFTDFT蝶形流圖蝶形流圖2點(diǎn)DFT2點(diǎn)DFTx(1)x(5)x(3)x(7)X5(0)X5(1)X6(0)X6(1)X2(0)X2(1)X2(2)X2(3)04W14W) 1

23、 () 1 () 1 () 0() 0() 2() 1 () 1 () 1 () 0() 0() 0(61452604526145260452XWXXXWXXXWXXXWXX其中 (0) (4) (2) (6) (1) (5) (3) (7)WN0WN0WN0W0N-1-1-1-1X (0)X (1)X (0)X (1)X (0)X (1)X (0)X (1)33445566WN0WN2WN0WN2-1-1-1-1X (0)X (1)X (2)X (3)X (0)X (1)X (2)X (3)11121222WWWWN0N1N2N3-1-1-1-1X(0)X(1)X(2)X(3)X(4)X(5

24、)X(6)X(7)xxxxxxxx因此因此,8,8點(diǎn)點(diǎn)DFTDFT的的FFTFFT的運(yùn)算流圖如下的運(yùn)算流圖如下x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)38W28W18W08W08W08W08W08W08W08W28W28WX(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)12/0NNNWW其中旋轉(zhuǎn)因子，共有m=0m=1m=2m m為級(jí)數(shù)為級(jí)數(shù), , N=2N=2M M所以所以N N點(diǎn)點(diǎn)DFTDFT可分成可分成M M級(jí)級(jí)2點(diǎn)DFT2點(diǎn)DFT2點(diǎn)DFT2點(diǎn)DFT2點(diǎn)DFT2點(diǎn)DFT2點(diǎn)DFT2點(diǎn)DFT兩個(gè)2點(diǎn)DFT兩個(gè)2點(diǎn)DFT兩個(gè)2點(diǎn)DFT兩個(gè)2點(diǎn)DFT兩個(gè)

25、4點(diǎn)DFT兩個(gè)4點(diǎn)DFT兩個(gè)N/2點(diǎn)DFTX1(k).X2(k)X(k) 由于每一步分解都是基于在每級(jí)按輸入時(shí)間序列由于每一步分解都是基于在每級(jí)按輸入時(shí)間序列的次序是屬于偶數(shù)還是奇數(shù)來分解為兩個(gè)更短的序列，的次序是屬于偶數(shù)還是奇數(shù)來分解為兩個(gè)更短的序列，所以稱為所以稱為“按時(shí)間抽取法按時(shí)間抽取法”. .x(n)( (二二).).運(yùn)算量運(yùn)算量 由上述分析可知,N=8N=8需三級(jí)蝶形運(yùn)算 N=2 =8,N=2 =8,由此可知,N=2N=2L L 共需L L級(jí)蝶形運(yùn)算, 而且每級(jí)都由N/2N/2個(gè)蝶形運(yùn)算 組成,每個(gè)蝶形運(yùn)算有一次復(fù)乘,兩次復(fù)加。3 3 因此因此,N,N點(diǎn)的點(diǎn)的FFTFFT的運(yùn)算量為

26、的運(yùn)算量為復(fù)乘復(fù)乘: m: mF F = =（N/2N/2）L=L=（N/2N/2） loglog2 2 N N復(fù)加復(fù)加: a: aF F =N L=N log =N L=N log2 2 N N 由于計(jì)算機(jī)的乘法運(yùn)算比加法運(yùn)算所由于計(jì)算機(jī)的乘法運(yùn)算比加法運(yùn)算所需的時(shí)間多得多，故以乘法作為比較基準(zhǔn)需的時(shí)間多得多，故以乘法作為比較基準(zhǔn). . (0)=(0)=X X0 0(0)(0) X X1 1(0)(0) X X2 2(0) X(0) X3 3(0)(0)=X(0) =X(0) (4)=(4)=X X0 0(1)(1) X X1 1(1) X(1) X2 2(1) X(1) X3 3(1)(1

27、)=X(1)=X(1) (2)=(2)=X X0 0(2)(2) X X3 3(2)(2)=X(2)=X(2) (6)=(6)=X X0 0(3)(3) X X3 3(3)(3)=X(3)=X(3) (1)=(1)=X X0 0(4)(4) X X1 1(4) X(4) X2 2(4) X(4) X3 3(4)(4)=X(4)=X(4) (5)=(5)=X X0 0(5)(5) X X3 3(5)(5)=X(5)=X(5) (3)=(3)=X X0 0(6)(6) X X3 3(6)(6)=X(6)=X(6) (7)=(7)=X X0 0(7)(7) X X1 1(7) X(7) X2 2(7

28、) X(7) X3 3(7)(7)=X(7)=X(7)WWWWN0N0N0N0-1-1-1-1WWWWN0N2N0N2-1-1-1-1WWWWNNNN0123.( (三三).DIT).DIT的的FFTFFT算法的特點(diǎn)算法的特點(diǎn) 1.1.原位運(yùn)算原位運(yùn)算輸入數(shù)據(jù)、中間運(yùn)算結(jié)果和最后輸出均用同一存儲(chǔ)器。輸入數(shù)據(jù)、中間運(yùn)算結(jié)果和最后輸出均用同一存儲(chǔ)器。xxxxxxxx2 2 倒位序規(guī)律倒位序規(guī)律 由圖可知由圖可知, ,輸出輸出X(k)X(k)按正常順序排列在存按正常順序排列在存儲(chǔ)單元儲(chǔ)單元, ,即即X(0)X(7),X(0)X(7),輸入?yún)s輸入?yún)s不能按自然順不能按自然順序存入到存儲(chǔ)單元中，而是序存入

29、到存儲(chǔ)單元中，而是x(0),x(4),x(2), x(0),x(4),x(2), x(6).x(6).的順序存入存儲(chǔ)單元的順序存入存儲(chǔ)單元，即為即為亂序輸入，亂序輸入，順序輸出順序輸出。 這種順序稱作這種順序稱作倒位序倒位序, ,即二進(jìn)制數(shù)倒位。即二進(jìn)制數(shù)倒位。 3.3.倒位序?qū)崿F(xiàn)倒位序?qū)崿F(xiàn) 輸入序列先按自然順序存入存儲(chǔ)單元輸入序列先按自然順序存入存儲(chǔ)單元, ,然后經(jīng)變址運(yùn)算來實(shí)現(xiàn)然后經(jīng)變址運(yùn)算來實(shí)現(xiàn)倒位序排列倒位序排列. . 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 4 1 0 0 1 1 0 0 4 2 0 1 0 0 1 0 2 2 0

30、1 0 0 1 0 2 3 0 1 1 1 1 0 6 3 0 1 1 1 1 0 6 4 1 0 0 0 0 1 1 4 1 0 0 0 0 1 1 5 1 0 1 1 0 1 5 5 1 0 1 1 0 1 5 6 1 1 0 0 1 1 3 6 1 1 0 0 1 1 3 7 1 1 1 1 1 1 7 7 1 1 1 1 1 1 7 自然順序自然順序n n 二進(jìn)制二進(jìn)制n n n n n n 倒位序二進(jìn)制倒位序二進(jìn)制n n n n n n 倒位順序倒位順序n n2 1 0 0 1 2看出：倒位序后的順序剛好是數(shù)據(jù)送入計(jì)算機(jī)內(nèi)的順序。看出：倒位序后的順序剛好是數(shù)據(jù)送入計(jì)算機(jī)內(nèi)的順序。4.

31、4.蝶形運(yùn)算所需系數(shù)蝶形運(yùn)算所需系數(shù)mM 2lmW212m0NW12, 1 ,01mlnkNW 蝶形運(yùn)算所需系數(shù)，各級(jí)有所不同。每級(jí)自上蝶形運(yùn)算所需系數(shù)，各級(jí)有所不同。每級(jí)自上而下觀察，均是以而下觀察，均是以 開始，按等比級(jí)數(shù)依次遞開始，按等比級(jí)數(shù)依次遞增，周期重復(fù)。例如，第增，周期重復(fù)。例如，第m m級(jí)運(yùn)算，系數(shù)為級(jí)運(yùn)算，系數(shù)為 , ,共共 個(gè)系數(shù)，指數(shù)個(gè)系數(shù)，指數(shù)l l逐次增逐次增1 1，周期重復(fù)周期重復(fù) 次。計(jì)算時(shí)所需系數(shù)可以事前計(jì)算好次。計(jì)算時(shí)所需系數(shù)可以事前計(jì)算好存在一個(gè)數(shù)表中，這樣運(yùn)算速度快，但需開銷內(nèi)存存在一個(gè)數(shù)表中，這樣運(yùn)算速度快，但需開銷內(nèi)存亦可在需要時(shí)依次遞推計(jì)算，這樣可節(jié)

32、省內(nèi)存，但亦可在需要時(shí)依次遞推計(jì)算，這樣可節(jié)省內(nèi)存，但要增加一定的運(yùn)算工作量。要增加一定的運(yùn)算工作量。6.3 6.3 頻率抽取基頻率抽取基2-2-FFTFFT算法算法( (桑德桑德圖基算法圖基算法) ) 對(duì)于對(duì)于N=2N=2M M情況下的另外一種普遍使用的情況下的另外一種普遍使用的FFTFFT結(jié)結(jié)構(gòu)是頻率抽取法，按輸出構(gòu)是頻率抽取法，按輸出X X（k k）在頻域的順序上）在頻域的順序上屬于偶數(shù)還是奇數(shù)分解為兩組屬于偶數(shù)還是奇數(shù)分解為兩組 對(duì)于頻率抽取法，輸入序列不是按偶數(shù)奇數(shù)，對(duì)于頻率抽取法，輸入序列不是按偶數(shù)奇數(shù)，而是按而是按前后對(duì)半前后對(duì)半分開，這樣便將分開，這樣便將N N點(diǎn)點(diǎn)DFTDFT

33、寫成前后兩寫成前后兩部分：部分：前半子序列前半子序列x(n),x(n), 0 0nN/2-1nN/2-1; ;后半子序列后半子序列x(n+N/2),0 x(n+N/2),0nN/2-1nN/2-1; ;例：例：N=8N=8時(shí)，前半序列為：時(shí)，前半序列為：x(0),x(1),x(2),x(3);x(0),x(1),x(2),x(3); 后半序列為：后半序列為：x(4),x(5),x(6),x(7); x(4),x(5),x(6),x(7); ( (一一).).算法原理算法原理 1.N1.N點(diǎn)點(diǎn)DFTDFT的另一種表達(dá)形式的另一種表達(dá)形式10)()(NnnkNWnxkX10)(1012/10222

34、2)2()()()(NNNNnknNnnkNNNnnkNnnkNWNnxWnxWnxWnxnkNnkNWWNnxnxNN1022)2()(nkNnkWNnxnxkXN102)2() 1()()(1, 1 , 0Nk 2.N2.N點(diǎn)點(diǎn)DFTDFT按按k k的奇偶分組可分為兩個(gè)的奇偶分組可分為兩個(gè)N/2N/2的的DFTDFT 當(dāng)當(dāng)k k為偶數(shù)為偶數(shù), ,即即 k=2rk=2r時(shí)時(shí), (-1), (-1)k k =1 =1； 當(dāng)當(dāng)k k為奇數(shù)為奇數(shù), ,即即 k=2r+1k=2r+1時(shí)時(shí) (-1)(-1)k k =-1 =-1 這時(shí)這時(shí) X(k) X(k) 可分為兩部分：可分為兩部分： nrnnrN

35、nNNNWNnxnxWNnxnx22210210)2()()2()()2( rX1, 1 , 02Nrk k為偶數(shù)時(shí)：為偶數(shù)時(shí)： 可見可見, ,上面兩式均為上面兩式均為N/2N/2的的DFTDFT。nrnnNrnNnNNNWWNnxnxWNnxnxrX22210)12(10)2()()2()() 12(k k為奇數(shù)時(shí)：為奇數(shù)時(shí)：1, 1 , 02Nr-1-1)2()(Nnxnx1, 1 ,02NnnNWNnxnx)2()(3.3.蝶形運(yùn)算蝶形運(yùn)算進(jìn)行如下碟形運(yùn)算：和)2()(NnxnxnNW)2(Nnx)(nx 4. 4.仿照仿照DITDIT的方法的方法 再將再將N/2N/2點(diǎn)點(diǎn)DFTDFT按

36、按k k的奇偶分解為兩個(gè)的奇偶分解為兩個(gè)N/4N/4點(diǎn)點(diǎn)的的DFT,DFT,如此進(jìn)行下去如此進(jìn)行下去, ,直至分解為直至分解為2 2點(diǎn)點(diǎn)DFTDFT。 例子：求例子：求 N=2 N=23 3=8=8點(diǎn)點(diǎn)DIFDIF （1 1）先按）先按N=8-N/2=4N=8-N/2=4，做做4 4點(diǎn)的點(diǎn)的DIFDIF：nNWNnxnxnxNnxnxnx)2()()()2()()(21先將先將N=8DFTN=8DFT分解成分解成2 2個(gè)個(gè)4 4點(diǎn)點(diǎn)DFTDFT：可知：時(shí)域上：可知：時(shí)域上：x(0),x(1),x(2),x(3)x(0),x(1),x(2),x(3)為偶子序列為偶子序列 x(4),x(5),x(

37、6),x(7) x(4),x(5),x(6),x(7)為奇子序列為奇子序列 頻域上：頻域上：X(0),X(2),X(4),X(6)X(0),X(2),X(4),X(6)由由x x1 1(n)(n)給出給出 X(1),X(3),X(5),X(7), X(1),X(3),X(5),X(7),由由x x2 2(n)(n)給出給出將將N=8N=8點(diǎn)分解成點(diǎn)分解成2 2個(gè)個(gè)4 4點(diǎn)的點(diǎn)的DIFDIF的信號(hào)流圖的信號(hào)流圖 4點(diǎn)DFTx(0)x(1)x(2)x(3)4點(diǎn)DFTx(4)x(5)x(6)x(7)X(0)X(2)X(4)X(6)X(1)X(3)X(5)X(7)X1(k)前半部分序列后半部分序列nN

38、nNnNnNWxxxWxxxWxxxWxxxxxxxxxxxxxxx)7()3(3,)6()2(2,)5() 1 (1,)4()0(0)7()3(3),6()2(2),5() 1 (1),4()0(022221111）（）（）（）（）（）（）（）（如：08W18W28W38Wx1(n)x2(n)X2(k)(2)N/2(4(2)N/2(4點(diǎn)點(diǎn))-N/4(2)-N/4(2點(diǎn)點(diǎn)) )FFTFFT(a)(a)先將先將4 4點(diǎn)分解成點(diǎn)分解成2 2點(diǎn)的點(diǎn)的DIFDIF：后半部分序列、前半部分序列、) 3 () 2() 1 () 0(: )(11111xxxxnx10140)2()()()2()(41131

39、1，），在此（）（若設(shè)：LNLLxWNnxnxLxNnxnxnN后半部分序列、前半部分序列、同理：) 3 () 2() 1 () 0(: )(22222xxxxnx10140)2()()()2()(622522，），在此（）（同理：LNLLxWNnxnxLxNnxnxnN（b b) )一個(gè)一個(gè)2 2點(diǎn)的點(diǎn)的DIFDIF蝶形流圖蝶形流圖2點(diǎn)DFT2點(diǎn)DFTx1(0)x1(1)x1(2)x1(3)x3(0)x3(1)x4(0)x4(1)X(0)X(4)X(2)X(6)08W28W) 3 () 1 () 1 (,) 2() 0() 0(113113xxxxxx其中(c)(c)另另一個(gè)一個(gè)2 2點(diǎn)的點(diǎn)

40、的DIFDIF蝶形流圖蝶形流圖2點(diǎn)DFT2點(diǎn)DFTx2(0)x2(1)x2(2)x2(3)x5(0)x5(1)x6(0)x6(1)X(1)X(5)X(3)X(7)08W28W(3)(3)將將N/4N/4（2 2點(diǎn)）點(diǎn)）DFTDFT再分解成再分解成2 2個(gè)個(gè)1 1點(diǎn)的點(diǎn)的DFTDFT(a)(a)求求2 2個(gè)一點(diǎn)的個(gè)一點(diǎn)的DFTDFT021022120202120230202020231021 , 0; 1 , 0)4()0()4()0() 1 ()4()0()4()0()0()()(2WWknWWWWWxWxWxWxXWxWxWxWxXWnxkXnknknkNnkNnnkN，其中，則這里用到對(duì)稱

41、性這是一蝶形結(jié)代入上面流圖可知： 最后剩下兩點(diǎn)最后剩下兩點(diǎn)DFT,DFT,它可分解成兩個(gè)一點(diǎn)它可分解成兩個(gè)一點(diǎn)DFTDFT，但一點(diǎn)，但一點(diǎn)DFTDFT就等于輸入信號(hào)本身，所以兩點(diǎn)就等于輸入信號(hào)本身，所以兩點(diǎn)DFTDFT可用一個(gè)蝶形結(jié)表可用一個(gè)蝶形結(jié)表示。取示。取x3(0)x3(0)、x3(1)x3(1)為例。為例。(b)2(b)2個(gè)個(gè)1 1點(diǎn)的點(diǎn)的DFTDFT蝶形流圖蝶形流圖 1點(diǎn)DFTx3(0)1點(diǎn)DFTx3(1)X(0)X(4)02W進(jìn)一步簡(jiǎn)化為進(jìn)一步簡(jiǎn)化為蝶形流圖：蝶形流圖：02WX(0)X(4)x3(0)x3(1)(4(4) )一個(gè)完整一個(gè)完整N=8N=8的按頻率抽取的按頻率抽取FFT

42、FFT的的運(yùn)算流圖運(yùn)算流圖 x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)38W28W18W08W08W08W08W08W08W08W28W28WX(0)X(4)X(2)X(6)X(1)X(5)X(3)X(7)12/0NNNWW其中旋轉(zhuǎn)因子，共有m=0m=1m=2頻率抽取法頻率抽取法FFTFFT的運(yùn)算特點(diǎn)：的運(yùn)算特點(diǎn)：（1 1）蝶形運(yùn)算）蝶形運(yùn)算 對(duì)于任何一個(gè)對(duì)于任何一個(gè)2 2的整數(shù)冪的整數(shù)冪N=2N=2M M，總是可以通過，總是可以通過M M次次分解最后完全成為分解最后完全成為2 2點(diǎn)的點(diǎn)的DFTDFT運(yùn)算。這樣的運(yùn)算。這樣的M M次分解，次分解，就構(gòu)成從就構(gòu)成從x(n)x

43、(n)到到X(k)X(k)的的M M級(jí)運(yùn)算過程。將頻率抽取法級(jí)運(yùn)算過程。將頻率抽取法的流圖反轉(zhuǎn)，并將輸入變輸出，輸出變輸入，得到的的流圖反轉(zhuǎn)，并將輸入變輸出，輸出變輸入，得到的便是時(shí)間抽取法流圖（反映了時(shí)域，頻域的對(duì)稱法）便是時(shí)間抽取法流圖（反映了時(shí)域，頻域的對(duì)稱法）。頻率抽取法也共有。頻率抽取法也共有M M級(jí)運(yùn)算（級(jí)運(yùn)算（N=2N=2M M），其運(yùn)算量與），其運(yùn)算量與時(shí)間抽取法相同。時(shí)間抽取法相同。（2 2）原位計(jì)算）原位計(jì)算 類似于時(shí)間抽取法，當(dāng)數(shù)據(jù)輸入到存儲(chǔ)器中以后類似于時(shí)間抽取法，當(dāng)數(shù)據(jù)輸入到存儲(chǔ)器中以后，每一級(jí)運(yùn)算的結(jié)果仍然儲(chǔ)存在同一組存儲(chǔ)器中，直，每一級(jí)運(yùn)算的結(jié)果仍然儲(chǔ)存在同一組存

44、儲(chǔ)器中，直到最后輸出，中間無需其它存儲(chǔ)器，所以頻域抽取法到最后輸出，中間無需其它存儲(chǔ)器，所以頻域抽取法也可進(jìn)行原位計(jì)算。也可進(jìn)行原位計(jì)算。（3 3）序數(shù)重排）序數(shù)重排 它的輸入正好是自然順序。但它的輸出卻是碼位倒它的輸入正好是自然順序。但它的輸出卻是碼位倒置的順序。因此運(yùn)算完畢后，要通過變址運(yùn)算將碼位倒置的順序。因此運(yùn)算完畢后，要通過變址運(yùn)算將碼位倒置的順序轉(zhuǎn)換為自然順序，然后輸出，變址方法同時(shí)間置的順序轉(zhuǎn)換為自然順序，然后輸出，變址方法同時(shí)間抽取法。抽取法。（4 4）蝶形類型隨迭代次數(shù)成倍減少）蝶形類型隨迭代次數(shù)成倍減少( (與時(shí)間抽取相反與時(shí)間抽取相反) ) 第一級(jí)迭代中有第一級(jí)迭代中有N

45、/2N/2種蝶形運(yùn)算系數(shù)，參加蝶形運(yùn)種蝶形運(yùn)算系數(shù)，參加蝶形運(yùn)算的兩個(gè)數(shù)據(jù)相隔算的兩個(gè)數(shù)據(jù)相隔N/2N/2，隨后每次迭代，蝶形類形比前，隨后每次迭代，蝶形類形比前一級(jí)減少一倍，間距也減少一倍，最后一級(jí)迭代，蝶形一級(jí)減少一倍，間距也減少一倍，最后一級(jí)迭代，蝶形類形只有一種類形只有一種W W0 0N N，數(shù)據(jù)間隔為，數(shù)據(jù)間隔為1 1。 由這幾點(diǎn)規(guī)律可以看出，頻率抽取法與時(shí)間抽取法由這幾點(diǎn)規(guī)律可以看出，頻率抽取法與時(shí)間抽取法是兩種等價(jià)的是兩種等價(jià)的FFTFFT運(yùn)算。運(yùn)算。1.1.相同點(diǎn)相同點(diǎn) (1)(1)進(jìn)行原位運(yùn)算；進(jìn)行原位運(yùn)算； (2)(2)運(yùn)算量相同運(yùn)算量相同, ,均為（均為（N/2) Log

46、N/2) Log2 2N N次復(fù)次復(fù)乘乘,N Log,N Log2 2N N次復(fù)加。次復(fù)加。 2.2.不同點(diǎn)不同點(diǎn) (1)DIT(1)DIT輸入為倒位序輸入為倒位序, ,輸出為自然順序；輸出為自然順序； DIFDIF正好與此相反。但正好與此相反。但DITDIT也有輸入為自然順也有輸入為自然順序序, ,輸出為倒位序的情況。輸出為倒位序的情況。( (二二).DIF).DIF法與法與DITDIT法的異同法的異同rNmmmWjXkXjX)()()(11rNmmmWjXkXkX)()()(11)(1kXm)(1jXmrNW1(2)(2)蝶形運(yùn)算不同蝶形運(yùn)算不同a.a.(DIT)(DIT)用矩陣表示用矩陣

47、表示)(kXm)(jXmrNWrNW)(1kXm)(1jXm=11rNmmmWjXkXjX)()()(11)()()(11jXkXkXmmm)(1kXm)(1jXmrNW1b.b.(DIF)(DIF)用矩陣表示)(kXm)(jXmrNWrNW)(1kXm)(1jXm=11(3)(3)兩種蝶形運(yùn)算的關(guān)系兩種蝶形運(yùn)算的關(guān)系 互為轉(zhuǎn)置（矩陣）；互為轉(zhuǎn)置（矩陣）；將流圖的將流圖的所有支路所有支路方向都反方向都反向向, ,交換輸交換輸入和輸出，入和輸出，即可得到即可得到另一種蝶另一種蝶形。形。 a.a.(DIT)(DIT)b.b.(DFT)(DFT)rNWrNW1111rNWrNWDIFDIF與與DIT

48、DIT根本區(qū)別：根本區(qū)別：在于蝶形結(jié)不同。在于蝶形結(jié)不同。DITDIT的復(fù)數(shù)相乘出現(xiàn)在減法之前。的復(fù)數(shù)相乘出現(xiàn)在減法之前。DIFDIF的復(fù)數(shù)相乘出現(xiàn)在減法之后。的復(fù)數(shù)相乘出現(xiàn)在減法之后。 6.5 6.5離散傅里葉反變換的計(jì)算方法離散傅里葉反變換的計(jì)算方法一一. .稍微變動(dòng)稍微變動(dòng)FFTFFT程序和參數(shù)可實(shí)現(xiàn)程序和參數(shù)可實(shí)現(xiàn)IFFTIFFT nkNNkNnnkNWkXNkXIDFTnxWnxnxDFTkX1010)(1)()()()()( 比較兩式可知比較兩式可知, ,只要只要DFTDFT的每個(gè)系數(shù)的每個(gè)系數(shù) 換換成成 , ,最后再乘以常數(shù)最后再乘以常數(shù)1/N1/N就可以得到就可以得到IDFTI

49、DFT的快速算法的快速算法-IFFT-IFFT。 另外另外, ,可以將常數(shù)可以將常數(shù)1/N1/N分配到每級(jí)運(yùn)算中分配到每級(jí)運(yùn)算中, , , ,也就是每級(jí)也就是每級(jí)蝶形運(yùn)算均乘蝶形運(yùn)算均乘以以1/1/2 2。 nkNWnkNWLLN)21(211利用利用FFTFFT計(jì)算計(jì)算IFFTIFFT時(shí)在命名上應(yīng)注意：時(shí)在命名上應(yīng)注意： (1)(1)把把FFTFFT的時(shí)間抽取法，用于的時(shí)間抽取法，用于IDFTIDFT運(yùn)算運(yùn)算時(shí)，由于輸入變量由時(shí)間序列時(shí)，由于輸入變量由時(shí)間序列x(n)x(n)改成頻率改成頻率序列序列X(k),X(k),原來按原來按x(n)x(n)的奇、偶次序分組的的奇、偶次序分組的時(shí)間抽取法

50、時(shí)間抽取法FFTFFT，現(xiàn)在就變成了按，現(xiàn)在就變成了按X(k)X(k)的奇的奇偶次序抽取了。偶次序抽取了。 ( (2 2) )同樣，頻率抽取的同樣，頻率抽取的FFTFFT運(yùn)算用于運(yùn)算用于IDFTIDFT運(yùn)算時(shí)，也應(yīng)改變?yōu)闀r(shí)間抽取的運(yùn)算時(shí)，也應(yīng)改變?yōu)闀r(shí)間抽取的IFFTIFFT。二、改變二、改變FFTFFT流圖系數(shù)的方法流圖系數(shù)的方法 1 1、在、在IFFTIFFT的運(yùn)算中，常常把的運(yùn)算中，常常把1/N1/N分解為分解為(1/2)(1/2)m m，并且在并且在M M級(jí)運(yùn)算中每一級(jí)運(yùn)算都分別乘以級(jí)運(yùn)算中每一級(jí)運(yùn)算都分別乘以1/21/2因子，因子，就可得到就可得到IFFTIFFT的兩種基本蝶形運(yùn)算結(jié)構(gòu)

51、的兩種基本蝶形運(yùn)算結(jié)構(gòu)。21nNW21BWAnN21BWAnN21AB21nNW21BA21nNWBA21AB(b)(b)時(shí)間抽時(shí)間抽取取IFFTIFFT的蝶形運(yùn)算的蝶形運(yùn)算(a)(a)頻率抽取頻率抽取IFFTIFFT的蝶形運(yùn)算的蝶形運(yùn)算2 2、IFFTIFFT的基本蝶形運(yùn)算的基本蝶形運(yùn)算三三. .不改不改(FFT)(FFT)的程序直接實(shí)現(xiàn)的程序直接實(shí)現(xiàn)IFFT IFFT nkNNkNknkNWkXNWkXNnx1010*)(1)(1)()(1)(110kXDFTNWkXNnkNNk)(nx因此，BABAWWnkNnkN , 這就是說這就是說, ,先將先將X(k)X(k)取共軛取共軛, ,即將

52、即將X(k)X(k)的的虛部乘虛部乘-1-1，直接利用，直接利用FFTFFT程序計(jì)算程序計(jì)算DFTDFT；然后；然后再取一次共軛；最后再乘再取一次共軛；最后再乘1/N,1/N,即得即得 (n)(n)。所。所以以FFT,IFFTFFT,IFFT可用一個(gè)子程序?？捎靡粋€(gè)子程序。x四、直接利用四、直接利用FFTFFT流圖方法的注意點(diǎn)流圖方法的注意點(diǎn)（1 1）FFTFFT與與IFFTIFFT連接應(yīng)用時(shí)，注意輸入輸出序列的連接應(yīng)用時(shí)，注意輸入輸出序列的 排列順序，是自然順序還是倒序。排列順序，是自然順序還是倒序。（2 2）FFTFFT和和IFFTIFFT共用同一個(gè)程序時(shí)，也應(yīng)注意利用共用同一個(gè)程序時(shí)，也

53、應(yīng)注意利用 FFTFFT算法輸入輸出的排列順序，即應(yīng)注意自然算法輸入輸出的排列順序，即應(yīng)注意自然 順序還是例位序順序還是例位序（3 3）當(dāng)把頻率抽?。┊?dāng)把頻率抽取FFTFFT流圖用于流圖用于IDFTIDFT時(shí)，應(yīng)改稱時(shí)時(shí)，應(yīng)改稱時(shí) 間抽取間抽取IFFTIFFT流圖。流圖。（4 4）當(dāng)把時(shí)間抽?。┊?dāng)把時(shí)間抽取FFTFFT流圖用于流圖用于IDFTIDFT時(shí)，應(yīng)改稱頻時(shí)，應(yīng)改稱頻 率抽取率抽取IFFTIFFT流圖。流圖。6.66.6 任意基數(shù)的任意基數(shù)的FFTFFT算法算法 以上討論的都是以以上討論的都是以2 2為基數(shù)的為基數(shù)的FFTFFT算法，即算法，即N=2N=2M M。優(yōu)點(diǎn)：程序簡(jiǎn)單，效率高，

54、使用方便。優(yōu)點(diǎn)：程序簡(jiǎn)單，效率高，使用方便。 實(shí)際應(yīng)用時(shí)，有限長(zhǎng)序列的長(zhǎng)度實(shí)際應(yīng)用時(shí)，有限長(zhǎng)序列的長(zhǎng)度N N很大程度上由人很大程度上由人為因素確定，因此多數(shù)場(chǎng)合可取為因素確定，因此多數(shù)場(chǎng)合可取 N=2N=2M M，從而直接使用，從而直接使用以以 2 2 為基數(shù)的為基數(shù)的FFTFFT算法。如算法。如N N不能人為確定不能人為確定 , N, N的數(shù)值的數(shù)值也不是以也不是以2 2為基數(shù)的整數(shù)次方為基數(shù)的整數(shù)次方, ,處理方法有兩種處理方法有兩種: : 補(bǔ)零補(bǔ)零: : 將將x(n)x(n)補(bǔ)零補(bǔ)零 , , 使使N=2N=2M.M. 例如例如N=30,N=30,補(bǔ)上補(bǔ)上x(30)=x(31)=0 x(3

55、0)=x(31)=0兩點(diǎn)兩點(diǎn), ,使使N=32=2N=32=25 5, ,這這樣可直接采用以樣可直接采用以2 2為基數(shù)為基數(shù)M=5M=5的的FFTFFT程序。程序。 有限長(zhǎng)度序列補(bǔ)零后并不影響其頻譜有限長(zhǎng)度序列補(bǔ)零后并不影響其頻譜 X(eX(ejwjw) )，只，只是頻譜的采樣點(diǎn)數(shù)增加了是頻譜的采樣點(diǎn)數(shù)增加了, ,上例中由上例中由3030點(diǎn)增加到點(diǎn)增加到3232點(diǎn)，點(diǎn)，所以在許多場(chǎng)合這種處理是可接受的。所以在許多場(chǎng)合這種處理是可接受的。 如要求準(zhǔn)確的如要求準(zhǔn)確的N N點(diǎn)點(diǎn)DFTDFT值值, ,可采用任意數(shù)為基數(shù)的可采用任意數(shù)為基數(shù)的 FFT FFT 算法算法 , , 其其 計(jì)算效率低于以計(jì)算效

56、率低于以2 2為基數(shù)為基數(shù)FFTFFT算法。算法。 如如N N為復(fù)合數(shù)，可分解為兩個(gè)整數(shù)為復(fù)合數(shù)，可分解為兩個(gè)整數(shù)p p與與q q的乘積的乘積, ,像像前面以前面以2 2為基數(shù)時(shí)一樣為基數(shù)時(shí)一樣,FFT,FFT的基本思想是將的基本思想是將DFTDFT的運(yùn)算的運(yùn)算盡量分小盡量分小, ,因此因此, ,在在N=pqN=pq情況下情況下, ,也希望將也希望將N N點(diǎn)的點(diǎn)的DFTDFT分分解為解為p p個(gè)個(gè)q q點(diǎn)點(diǎn)DFTDFT或或q q個(gè)個(gè)p p點(diǎn)點(diǎn)DFT,DFT,以減少計(jì)算量。以減少計(jì)算量。步驟：步驟：0101kPkknQnn10,kn分別為0, 1,，Q-1; 01,kn分別為0, 1,，P-1。

57、 N N點(diǎn)點(diǎn)DFTDFT可以重新寫成為可以重新寫成為 100101)(,)()(NnknNWnxkkXkPkXkX1010)(01010101QnPnnQnkPkNWnQnx10100110100101010001100100011011,QnPnnkNPnkNQnkNQnPnnkNPnkNQnkNPQnkNWWWnnxWWWWnnxkkX考慮到考慮到 再令再令1010nkPQnkNWW令令 1010010100100110,QnnkQnkNPnnkPWWWnnxkkXPnnkPWnnxnkX,01000,0011001nkQnkNQnWWnkXkkX00001001,nkNWnkXnkXQn

58、nkQWnkXkkX,以以P P=3=3，Q Q=4, =4, N N=12=12為例為例 (1) (1) 先將先將 x(n)x(n)通過通過 x(nx(n1 1Q+nQ+n0 0) )改寫成改寫成 x(nx(n1 1,n,n0 0) )。因?yàn)?。因?yàn)?Q=4, nQ=4, n1 1=0,1,2, n=0,1,2, n0 0=0,1,2,3,=0,1,2,3,故輸入是按自然順序故輸入是按自然順序的，即的，即 x(0,0)=x(0) x(0,1)=x(1) x(0,2)=x(2) x(0,0)=x(0) x(0,1)=x(1) x(0,2)=x(2) x(0,3)=x(3)x(0,3)=x(3)

59、x(1,0)=x(4) x(1,1)=x(5) x(1,2)=x(6) x(1,0)=x(4) x(1,1)=x(5) x(1,2)=x(6) x(1,3)=x(7)x(1,3)=x(7) x(2,0)=x(8) x(2,1)=x(9) x(2,2)=x(10) x(2,0)=x(8) x(2,1)=x(9) x(2,2)=x(10) x(2,3)=x(11)x(2,3)=x(11)(2) (2) 求個(gè)點(diǎn)的求個(gè)點(diǎn)的DFT DFT （）（）X X1 1(k(k0 0,n,n0 0) )乘以得到乘以得到X X1 1(k(k0 0,n,n0 0) )。（）求（）求P P個(gè)點(diǎn)的個(gè)點(diǎn)的DFTDFT，參變

60、量是，參變量是k k0 020301001110,nnkWnnxnkX304001102001,nnkWnkXkkX（）將（）將X X2 2(k(k0 0,k,k1 1) )通過通過X(kX(k0 0+k+k1 1P)P)恢復(fù)為恢復(fù)為X(k)X(k)N=12為組合數(shù)時(shí)的FFT（）求個(gè)（）求個(gè)P P點(diǎn)點(diǎn)DFTDFT需要需要P P2 2次復(fù)數(shù)乘法和次復(fù)數(shù)乘法和 P(P-1)P(P-1)次復(fù)數(shù)加法；次復(fù)數(shù)加法；（）乘個(gè)（）乘個(gè)W W因子需要次復(fù)數(shù)乘法；因子需要次復(fù)數(shù)乘法；（）求（）求P P個(gè)點(diǎn)個(gè)點(diǎn)DFTDFT需要需要PQPQ2 2 次復(fù)數(shù)乘法和次復(fù)數(shù)乘法和 PP（-1)-1)次復(fù)數(shù)加法。次復(fù)數(shù)加法。