按時(shí)間抽取的基2FFT算法分析

1、第四章快速傅里葉變換有限長(zhǎng)序列可以通過離散傅里葉變換(DFT)將其頻域也離散化成有限長(zhǎng) 序列.但其計(jì)算量太大，很難實(shí)時(shí)地處理問題，因此引出了快速傅里葉變換 (FFT). 1965年，CooIey和TUkey提出了計(jì)算離散傅里葉變換(DFT)的快 速算法，將DFT的運(yùn)算量城少了幾個(gè)數(shù)量級(jí)。從此，對(duì)快速傅里葉變換(FFT) 算法的研究便不斷深入，數(shù)字信號(hào)處理這門新興學(xué)科也隨FFT的出現(xiàn)和發(fā)展 而迅速發(fā)展。根損對(duì)序列分解與選取方法的不同而產(chǎn)生了 FFT的多種算法， 基本算法是基2DIT和基2DIFo FFT在離散傅里葉反變換、線性卷積和線性 相關(guān)等方面也有重要應(yīng)用?？焖俑道锶~變換(FFT)是計(jì)算離散

2、傅里葉變換(DFT)的快速算法。DFT的定狡式為N-IX伙)=工心)呼心在所有復(fù)指數(shù)值Wf的值全部已算好的情況下，要計(jì)算一個(gè)X伙)需要N次 復(fù)數(shù)乘法和N-1次復(fù)數(shù)加法。算出全部N點(diǎn)X伙)共需N?次復(fù)數(shù)乘法和 N(N-I)次復(fù)數(shù)加法。即計(jì)算量是與N?成正比的。FFT的基本思想：將大點(diǎn)數(shù)的DFT分解為若干個(gè)小點(diǎn)數(shù)DFT的組合，從 而城少運(yùn)算量。WN因子具有以下兩個(gè)特性，可使DFT運(yùn)算量盡量分解為小點(diǎn)數(shù)的DFT 運(yùn)算：(1) 周期性：Wn = WN)k(2) 對(duì)稱性：WN,2 =利用這兩個(gè)性質(zhì)，可以使DFT運(yùn)算中有些項(xiàng)合并，以減少乘法次數(shù)。例子:求當(dāng)N=4時(shí)，X(2)的值3X(2)=工 Xs)WJ

3、= x(O)VV4o + (1)W42 + (2)VV44 + x(3)46H-O=-r(0) + (2)VV40 +Wl) + x(3)VV42 (周期性)=(0) + x(2)-x(l) + X 網(wǎng) (對(duì)稱性)通過合并，使乘法次數(shù)由4次減少到1次，運(yùn)算量減少。FFT的算法形式有很多種，但基本上可以分為兩大類：按時(shí)間抽取(DlT)和按頻率抽取(DlF)O按時(shí)間抽取(DlT)的FTT為了將大點(diǎn)數(shù)的DFT分解為小點(diǎn)數(shù)的DFT運(yùn)算，要求序列的長(zhǎng)度N為復(fù) 合數(shù)，最常用的是N = 2“的情況(M為正整數(shù))。該情況下的變換稱為基 2FFTo下面討論基2情況的算法。先將序列X (n)按奇偶項(xiàng)分解為兩組x(

4、2r) = XI (r)N 、x(2r + ) = x2(r)廠_，''勺"_將DFT運(yùn)算也相應(yīng)分為兩組JV-IX(k) = DFTx(n)=x(n)W0NTNT=2>S)W(+;?=0H=OH為偶數(shù)n為奇數(shù)JV/2-1Af/2-1=Yjx(2r)Vrk ÷ £心 + 1)W嚴(yán)r-()r-()JV2-1W/2-1(r)W +; x2(r)r rOr-0/2-12-lX"叱2+叫2(M農(nóng)(因?yàn)檫硣?yán)=叱2)r-()r-0= X") + WjX2 伙)其中XI伙）、X2（Ar）分別是x1（n）s勺5）的"2點(diǎn)的DFTN

5、/2-172-lNX1W = X1 (r)VZ2 =工v(2r)VV2,0k-r-()r-0LN/2-1NJ 27NX2(k)=jx2(r)WZ2 = (2r + l)2,0Arl-l r-0r-0L至此，一個(gè)N點(diǎn)DFT被分解為兩個(gè)N/2點(diǎn)的DFT。上面是否將全部N點(diǎn)的X伙）求解出來了N分析：X伙）和X?伙）只有N/2個(gè)點(diǎn)（&=0丄,一一1）,則由 2X伙）=Xl伙）+ WX2伙）只能求出X伙）的前N/2個(gè)點(diǎn)的DFT,要求出全部N點(diǎn)的X伙），需要找出Xl W > X2（k）和X伙+ N2）的關(guān)系，其中 =0,l, -,-Io 由式子 X伙)=Xl(k) + WX2(k)可得2X伙

6、 + N/2) = X1 (k + N2) + Wf2X2伙+ N2)化簡(jiǎn)得NX(k + N2) = = Xl(R)-W(X2(Q, R = (M,一_12這樣N點(diǎn)DFT可全部由下式確定出來:X(k + N2) = Xk)-W.X2(k)2上式可用一個(gè)專用的碟形符號(hào)來表示，這個(gè)符號(hào)對(duì)應(yīng)一次復(fù)乘和兩次復(fù)加運(yùn)算。a + Wba-W通過這樣的分解以后，每一個(gè)N/2點(diǎn)、的DFT只需要()2 =次復(fù)數(shù)乘2NN法，兩個(gè)N/2點(diǎn)的DFT需要2()2 =次復(fù)乘，再加上將兩個(gè)N/2點(diǎn) 22NN NDFT合并成為N點(diǎn)DFT時(shí)有N/2次與W因子相乘，一共需要 + 222次復(fù)乘。可見，通過這樣的分解，運(yùn)算量節(jié)省了近一

7、半。因?yàn)镹 = 2'". N/2仍然是偶數(shù)，因此可以對(duì)兩個(gè)N/2點(diǎn)的DFT再分別作進(jìn)一步的分解，將兩個(gè)N/2點(diǎn)的DFT分解成兩個(gè)N/4點(diǎn)的DFTo例如對(duì)x1(r),可以在按其偶數(shù)部分及奇數(shù)部分進(jìn)行分解：Fg心0,1,上1g + l) = x4()4則的運(yùn)算可相應(yīng)分為兩組：yv4-lf4-1X")=工 m(2)Vc2 + > + 1)叱於“/-0/-()jV/4-1N/4-1=>3(W為+叱爲(wèi)工兀叱為/-0Z-OX3(k) + W,2X4 伙)jt=0,l,-l一48 點(diǎn) DFT×(0 (I) ×(2) 必(3) <×(

8、4) 啦5 嘆6ZXXXXXXX(XXXXXXXX (0)M)(21問 £ x(×(×(×(x(×(×(X2dftXXXXXXXXOOOOoOoOO-OOOQO OoX1W = X3伙) + w,i伙),Al N I<k = O _ 1X、(k + N4) = X3(k)-WtkX4 伙) 4同樣，對(duì)X2(Zr)也可進(jìn)行類似的分解。一直分解下去，最后是2點(diǎn)的DFT, 2點(diǎn)DFT的運(yùn)算也可用碟形符號(hào)來表示。這樣，對(duì)于一個(gè)N = 23 =S 的DFT運(yùn)算，其按時(shí)間抽取的分解過程及完整流圖如下圖所示。x(0- XrIb ×(

9、2kX (3Io- × M)O- x(5J0.X (6卩 ×Rk(O)同(2)問(1)(5)Pl ×(x(x(×(×(x(x(X這種方法，由于每一步分解都是按輸入序列在時(shí)域上的次序是屬于偶數(shù) 還是奇數(shù)來抽取的，故稱為"時(shí)間抽取法S分析上面的流圖，N = 2“，一共要進(jìn)行M次分解，構(gòu)成了從x(n)到 X(k)的M級(jí)運(yùn)算過程。毎一級(jí)運(yùn)算都是由N/2個(gè)蝶形運(yùn)算構(gòu)成，因此每一級(jí) 運(yùn)算都需要N/2次復(fù)乘和N次復(fù)加，則按時(shí)間抽取的M級(jí)運(yùn)算后總共需要NN復(fù)數(shù)乘法次數(shù)：HIF =M=-IosNf 22 復(fù)數(shù)加法次數(shù)：UIt =N-M= /Vlog2

10、N根據(jù)上面的流圖，分析FFT算法的兩個(gè)特點(diǎn)，它們對(duì)FFT的軟硬件 構(gòu)成產(chǎn)生很大的影響。(1 )原位運(yùn)算也稱為同址運(yùn)算，當(dāng)數(shù)據(jù)輸入到存儲(chǔ)器中以后，毎一級(jí)運(yùn)算的結(jié)果仍然存儲(chǔ) 在原來的存儲(chǔ)器中，直到我后輸出，中間無需其它的存儲(chǔ)器。根據(jù)運(yùn)算流圖 分析原位運(yùn)算是如何進(jìn)行的。原位運(yùn)算的結(jié)構(gòu)可以節(jié)省存儲(chǔ)單元，降低設(shè)備 成本。(2) 變址分析運(yùn)算流圖中的輸入輸出序列的順序，輸出按順序，輸入是“碼位倒置” 的順序。見圖。自然順序二進(jìn)制表示碼位倒置碼位倒置順序OOOO000010011004201001023011110641000011510110156110011371111117在實(shí)際運(yùn)算中，直接舟輸入數(shù)據(jù)

11、X (n)按碼位倒置的順序排好輸入很 不方便，一般總是先按自然順序輸入存儲(chǔ)單元，然后通過變址運(yùn)算將自然順 序的存儲(chǔ)換成碼位倒置順序的存儲(chǔ)，這樣就可以進(jìn)行FFT的原位運(yùn)算。變質(zhì) 的功能如圖所示。用軼件實(shí)現(xiàn)是通用釆用雷徳(Rader)算法，算出I的倒 序J以后立即將輸入數(shù)據(jù)X(I)和X(J)對(duì)換。盡管變址運(yùn)算所占運(yùn)算董的比 例很小，但對(duì)某些高要求的應(yīng)用(尤其在實(shí)時(shí)信號(hào)處理中)，也可設(shè)法用適 當(dāng)?shù)碾娐方Y(jié)構(gòu)直接實(shí)現(xiàn)變址。例如單片數(shù)字信號(hào)處理器TMS320C25就有專用 于FFT的二進(jìn)制碼變址模式。4. 2按頻率抽取(DlF)的FTT除吋間抽取法外，另外一種普遍使用的FFT結(jié)構(gòu)是頻率抽取法。頻率抽取法將

12、輸入序列不是按奇、偶分組，而是將N點(diǎn)DFT寫成前后兩部分:N-IX(k) = DFnx(n)= x(n)WnH-O(T2)-1N-I= DS)W+ 2>(")wj0/r-4V2JV/2-1N/2-1=+ 2>(n + N2)Wyz2M-0r0N/2-1=yjx(n) +JV/2)V(H + / 2)W-O因?yàn)閃f" =_1,Wf 2)* =(_i)x , k為偶數(shù)時(shí)(_1)女=1, k為奇數(shù)時(shí)(一1)*=一1,由此可將X(k)分解為偶數(shù)紐和奇數(shù)紐：72-lXg= 2>() + (-1)飯+ N/2)卩曾n-0jV/2-1X(2r)=工x()+心+ N2)W

13、"H-Of/2-1=x(n) + x(n + N 2)V2rU)JV/2-1X (2r +1)=工x() - x(n + N / 2) Wi"-0N/2-1 =2>U)7G + N2)W.W篇 2片-0Xl (；0 = X(II) + x(zz + yv2)令 <H = O 丄，N/2 12() = x() 一 x(n + N2) ;這兩個(gè)序列都是N/2點(diǎn)的序列，對(duì)應(yīng)的是兩個(gè)N/2點(diǎn)的DFT運(yùn)算：2-lX(2J= x,(nM'2H-O2-lX（2 廠+ 1）=J>2陀;2-4）這樣，同樣是將一個(gè)N點(diǎn)的DFT分解為兩個(gè)N/2點(diǎn)的DFT 了。頻率抽選法

14、對(duì)應(yīng)的碟形運(yùn)算關(guān)系圖如下：對(duì)于N=8吋頻率抽取法的FFT流圖如下:* IJ -IJ IJ J -IJ -IJ IJ 卩 1 234 567 fl¾ fl¾ fl¾ ( ( H ( ××××××××OOOAVO : : 廠 ； 二O歹，矽OAVOo-Or*cb77-.2占C-八“DFT送2占DFT-1廠F>o2占C-八"DFTo-12占厶八、DFTr U 一 一/ “ 卩g尼他 P R XXXX XXXX 06OOO600 kkk-IJ -IJ U -IJ -IJ IJ

15、-IJ 0426 1537«11 ll «11 «11 H »11 <l Xxxx Xxxx這種分組的辦法由于每次都是按輸出X(k)在頻域的順序上是屬于偶數(shù)還是 奇數(shù)來分組的，稱為頻率抽取法。與前面按時(shí)間抽取的方法相比，相同點(diǎn) 問題：如何利用快速算法計(jì)算IDFT分析IDFT的公式：1 AMX(H) = IDFT X 伙)=若 X 伙)叱卩","=0,1,N 1比較DFT的公式：,-lXa) = DFTx(n) = YXS)W化 & =0,屮一1n0得知可用兩種方法來實(shí)現(xiàn)IDFT的快速算法：(1 )只要把DFT運(yùn)算中的每一

16、 個(gè)系數(shù)Wy該為Wy 并且最后再乘以常數(shù)丄，就可以用時(shí)間抽取法或N頻率抽取的FFT算法來直接計(jì)算IDFTo這種方法需要對(duì)FFT的程序和參數(shù)稍 加 改 動(dòng) 才 能 實(shí) 現(xiàn)。 (2) 因 為1 N-1W0 = 77工(QW嚴(yán)=77MT(燈M = O,1,N-1,也就 N A：-oN是說，可先將X(k)取共純變換，即將X(k)的虛部乘以一 1 ,就可直接調(diào)用 FFT的程序，罠后再對(duì)運(yùn)算結(jié)果取一次共純變換并乘以常數(shù)1/N即可得到X (n) 的值。這種方法中，F(xiàn)FT運(yùn)算和IFFT運(yùn)算都可以共用一個(gè)子程序塊，在使 用通用計(jì)算機(jī)或用硬件實(shí)現(xiàn)吋比較方便。4.1.3混合基FFT算法以上討論的是基2的FFT算法，

17、即N = 2M的情況，這種情況實(shí)際上 使用得最多，這種FFT運(yùn)算，程序簡(jiǎn)單，效率很鬲，用起來很方便。另外， 在實(shí)際應(yīng)用時(shí)，有限長(zhǎng)序列的長(zhǎng)度N到底是多少在很大程度時(shí)是由人為因素 確定的，因此，大多數(shù)場(chǎng)合人們可以將N選定為N = 2M 9從而可以直接調(diào) 用以2為基數(shù)的FFT運(yùn)算程序。如果長(zhǎng)度N不能認(rèn)為確定，而N的數(shù)值又不是以2為基數(shù)的整數(shù)次方， 一般可有以下兩種處理方法：(1 ) 將x(n)用補(bǔ)零的方法延長(zhǎng)，使N增長(zhǎng)到最鄰近的一個(gè) N = 2M數(shù)值。例如,N=30,可以在序列x(n)中補(bǔ)進(jìn)x(30)=x(31) =O兩個(gè)零值點(diǎn)，使N=32。如果計(jì)算FFT的目的是為了 了解整 個(gè)頻譜，而不是特定頻率

18、點(diǎn)，則此法可行。因?yàn)橛邢揲L(zhǎng)序列補(bǔ) 零以后并不影響其頻譜X(ejw),只是頻譜的采樣點(diǎn)數(shù)增加而 已。(2)如果要求特定頻率點(diǎn)的頻譜，則N不能改變。如果N為復(fù)合數(shù)， 則可以用以任意數(shù)為基數(shù)的FFT #法來計(jì)算?？焖俑道锶~變換的基本思想就是要將DFT的運(yùn)算盡量分小。例如，N=6吋，可以按照N=3X2分解，將6點(diǎn)DFT分解為3組2點(diǎn)DFTo舉例：N=9時(shí)的快速算法。4.2快速傅里葉變換的應(yīng)用凡是可以利用傅里葉變換來進(jìn)行分析、綜合、變換的地方，都可以利 用FFT算法及運(yùn)用數(shù)字計(jì)算技術(shù)加以實(shí)現(xiàn)。FFT在數(shù)字通信、語音信號(hào)處理、 圖像處理、匹配濾波以及功率譜仕計(jì).仿真.系統(tǒng)分析等各個(gè)領(lǐng)域都得到了 廣泛的應(yīng)用

19、。但不管FFT在哪里應(yīng)用，一般都以卷積積分或相關(guān)積分的具體 處理為依據(jù)，或者以用FFT作為連續(xù)傅里葉變換的近似為基礎(chǔ)。利用FFT求線性卷積一快速卷積在實(shí)際中常常遇到要求兩個(gè)序列的線性卷積。如一個(gè)信號(hào)序列x(n)通 過FlR濾波器時(shí)，其輸出y(n)應(yīng)是x(n)與h(n)的卷積：Xy(n) = x(n) * h(n)= 工 x(ni)h(n 一 In)“10C有限長(zhǎng)序列x(n)與h(n)的卷積的結(jié)果y(n)也是一個(gè)有限長(zhǎng)序列。假設(shè)x (n) 與h(n)0長(zhǎng)度分別為Nl和N2,則y(n)的長(zhǎng)度為N=N1+N2T°若通過補(bǔ)零使 x(n)與h(n)都加長(zhǎng)到N點(diǎn)，就可以用圓周卷積來計(jì)算線性卷枳。

20、這樣得到 用FFT運(yùn)算來求y(n)值(快速卷積)的步驟如下：(1 )對(duì)序列x(n)與h(n)補(bǔ)零至長(zhǎng)為N,使NN1+N2-1 ,并且N = 2M (M為整數(shù)),即Lr(n), H = 0,1,9 /Vl -1X02)=O, H = NhNz ，N-If/?(/?), n = O,1,7V2-1 Il(H)= <O, n = V2,N2 + l,N-1(2) 用FFT計(jì)算x(n)與h(n)的離散傅里葉變換X(U) <=> (FFT) o X伙)(N 點(diǎn))h(n) <=> (FFT) o H伙)(N 點(diǎn))(3) 計(jì)算 Y(k)=X(k)H(k)(4) 用IFFT計(jì)算Y

21、(k)的離散傅里葉反變換得：y(n) = IFFTY(k) (N 點(diǎn))4. 2. 2利用FFT求相關(guān)一快速相關(guān)互相關(guān)及自相關(guān)的運(yùn)算已廣泛的應(yīng)用于信號(hào)分析與統(tǒng)計(jì)分析，應(yīng)用于連 續(xù)時(shí)間系統(tǒng)也用于離散事件系統(tǒng)。用FFT計(jì)算相關(guān)函數(shù)稱為快速相關(guān)，它與快速卷積完全類似，不同的是 一個(gè)應(yīng)用離散相關(guān)定理，另一個(gè)應(yīng)用離散卷積定理。同樣都要注意到離散傅 里葉變換固有的周期性，也同樣用補(bǔ)零的方法來繞過這個(gè)障礙。設(shè)兩個(gè)離散時(shí)間信號(hào)x(n)與y(n)為已知，離散互相關(guān)函數(shù)記作&、.(”)，定義為OCRan= YJX(If j)y(n + m)J?!-X如果x(n)與y(n)的序列長(zhǎng)慶分別為NI和N2,則用FFT求相關(guān)的計(jì)算步驟 如下：(1 )對(duì)序列x(n)與y(n)補(bǔ)零至長(zhǎng)為N,使NMNI+N2T,并且N = 2"(M為整數(shù)),即x(n),2 = 0丄，Nl-IXW =O, n = Nl,M + l,，N-1b(n), =0,，N2-1y(n)=, n = N2N2 + X 、N-(2) 用FFT計(jì)算x(n)與y(n)的離散傅里葉變換X(H) O (FFT) o X伙)(N 點(diǎn))y(n) 0 (FFT) 0 Yg(N 點(diǎn))(3) 將X(k)的虛部lmX