按時(shí)間抽取的基2FFT算法分析報(bào)告

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

2、用?？焖俑道锶~變換(FFT)是計(jì)算離散傅里葉變換(DFT )的快速算法。DFT 的定義式為N1knX(k) =x(n)WNknRN (k)n0在所有復(fù)指數(shù)值 wNn的值全部已算好的情況下，要計(jì)算一個(gè)X(k)需要N次復(fù)數(shù)乘法和N 1次復(fù)數(shù)加法。算出全部 N點(diǎn)X(k)共需N 2次復(fù)數(shù)乘法 和N(N 1)次復(fù)數(shù)加法。即計(jì)算量是與 N2成正比的。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(k N )n WNkn WN(n N)k( 2)對(duì)稱性：

3、 WN(k N /2)WNk利用這兩個(gè)性質(zhì)，可以使 DFT運(yùn)算中有些項(xiàng)合并，以減少乘法次數(shù)。例子:求當(dāng)N = 4時(shí)，X(2)的值3X(2)x( n)W42n x(O)W：x(1)W42x(2)W44x(3)w44n 0x(0) x(2)W40x(1)x(3)W42(周期性)= x(0) x(2)-x(1) x(3)W40(對(duì)稱性)通過(guò)合并，使乘法次數(shù)由4次減少到1次，運(yùn)算量減少。FFT的算法形式有很多種，但基本上可以分為兩大類：按時(shí)間抽取(DIT )和按頻率抽取(DIF )。4.1按時(shí)間抽取(DIT )的FTT為了將大點(diǎn)數(shù)的 DFT分解為小點(diǎn)數(shù)的 DFT運(yùn)算，要求序列的長(zhǎng)度 N為 復(fù)合數(shù)，最常

4、用的是 N 2M的情況(M為正整數(shù))。該情況下的變換稱為 基2FFT。下面討論基2情況的算法。先將序列x(n)按奇偶項(xiàng)分解為兩組x(2r)Xi(r)x(2r 1) x2 (r)r 0,1, ，- 12將DFT運(yùn)算也相應(yīng)分為兩組N 1 knX(k) DFTx( n)x(n)Wzn 0N 1N 1x( n)WNkn+x( n)W,nn 0n 0n為偶數(shù)n為奇數(shù)N /2 12 rk=x(2)WnN /2 1x(2r 1)WN(2r 1)k2rkXi(JWnr 02rkWnX2 (r )Vnr 0N /2 1 rkXi()Wn/2N /2 1 rkWnX2()Wn/2r 0個(gè)為 W(rkWn"

5、;/2 )kX“(k) WNX2(k)其中X,k)、X2(k)分別是 x,n)、x2(n)的 N/2 點(diǎn)的 DFTN /2 1 rkX1(k) =X1(r)WN/2r 0N /2 1rkX2(k) =X2()Wn/2r 0至此，一個(gè)N點(diǎn)DFT被分解為兩個(gè)N /2 1 rkNx(2r)WN/2,0k1r 02x(2r 1)W,/2,0 k N 1r 02N/2 點(diǎn)的 DFT。上面是否將全部 N點(diǎn)的X(k)求解出來(lái)了？N分析：Xdk)和X2(k)只有N/2個(gè)點(diǎn)(k 0,1,21)，則由kX(k) X1(k) WzX2(k)只能求出X(k)的前N/2個(gè)點(diǎn)的DFT，要求出全部N點(diǎn)的X(k)，需要找出X

6、,k)、X2(k)和X(k N/2)的關(guān)系，其中 k 0,1, ,N 1。由式子 X(k) X,k) W,X2(k)可得2X(k N/2) X1(k N/2) W, N/2X2(k N / 2)化簡(jiǎn)得kNX(k N /2) = Xdk) WzX2(k) , k 0,1,12這樣N點(diǎn)DFT可全部由下式確定出來(lái)：0,1,嚴(yán))X(k) Xdk) W,X2(k)kX(k N/2) X1(k) WNX2(k)上式可用一個(gè)專用的碟形符號(hào)來(lái)表示，這個(gè)符號(hào)對(duì)應(yīng)一次復(fù)乘和兩次復(fù)加運(yùn)算。kW“b圖蝶形運(yùn)算符號(hào)kWzb通過(guò)這樣的分解以后，每一個(gè)2N 2 N 2N/2點(diǎn)的DFT只需要（一）2次復(fù)數(shù)乘24法，兩個(gè) N/

7、2點(diǎn)的DFT需要2N 2 N22（）2次復(fù)乘，再加上將兩個(gè)N/2點(diǎn)2 2DFT合并成為 N點(diǎn)DFT時(shí)有N / 2次與 W因子相乘，一共需要N2N 次復(fù)乘?？梢?jiàn)，通過(guò)這樣的分解，運(yùn)算量節(jié)省了近一半。2 2因?yàn)镹2M，N/2仍然是偶數(shù)，因此可以對(duì)兩個(gè) N/2點(diǎn)的DFT再分別作進(jìn)一步的分解，將兩個(gè) N/2點(diǎn)的DFT分解成兩個(gè)N/4點(diǎn)的DFT。例如對(duì)xdr），可以在按其偶數(shù)部分及奇數(shù)部分進(jìn)行分解:xi（2l）X3（l）Xi（2l1）X4（l）0,1,沖 1N /4 12lkX1（k） =X1（2I）Wn/2l 0N /4 1xi（2l1）wN2l21）kl 0則的運(yùn)算可相應(yīng)分為兩組:N /4 1 lk

8、=X3（I）Wn/4l 0N /4 1kikWn/2X4（I）Wn/4l 0kNX3（k） WN/2X4（k） k 01，1將系數(shù)統(tǒng)一為以N為周期，即W,/2WN，可得2 kXi（k）X3（k） Wn X4（k）N2kk 0,1, 1Xi（k N /4） X3（k） Wn X4（k）4同樣，對(duì)X2(k)也可進(jìn)行類似的分解。一直分解下去，最后是2點(diǎn)的3DFT, 2點(diǎn)DFT的運(yùn)算也可用碟形符號(hào)來(lái)表示。這樣，對(duì)于一個(gè)N 28的DFT運(yùn)算，其按時(shí)間抽取的分解過(guò)程及完整流圖如下圖所示。xxxx xxxx(n)同罔問(wèn)11 5)3)p)2占DFT& 00 OQ-4e e 0 b OIOII-&

9、;0800 & Q &xlsrxMXxxx2)_31町可切n這種方法，由于每一步分解都是按輸入序列在時(shí)域上的次序是屬于偶數(shù)還是奇數(shù)來(lái)抽取的，故稱為“時(shí)間抽取法”。分析上面的流圖，N 2M，一共要進(jìn)行 M次分解，構(gòu)成了從 x(n)到X(k)的M級(jí)運(yùn)算過(guò)程。每一級(jí)運(yùn)算都是由N/2個(gè)蝶形運(yùn)算構(gòu)成，因此每一級(jí)運(yùn)算都需要 N/2次復(fù)乘和N次復(fù)加，則按時(shí)間抽取的M級(jí)運(yùn)算后總共需復(fù)數(shù)乘法次數(shù)： mF M N log2 NF 2 2 U2復(fù)數(shù)加法次數(shù)：aF N M N |og2 N根據(jù)上面的流圖，分析FFT算法的兩個(gè)特點(diǎn)，它們對(duì)FFT的軟硬件構(gòu)成產(chǎn)生很大的影響。(1) 原位運(yùn)算也稱為同址運(yùn)算，

10、當(dāng)數(shù)據(jù)輸入到存儲(chǔ)器中以后，每一級(jí)運(yùn)算的結(jié)果仍然存儲(chǔ) 在原來(lái)的存儲(chǔ)器中， 直到最后輸出，中間無(wú)需其它的存儲(chǔ)器。 根據(jù)運(yùn)算流圖 分析原位運(yùn)算是如何進(jìn)行的。原位運(yùn)算的結(jié)構(gòu)可以節(jié)省存儲(chǔ)單元，降低設(shè)備成本。(2) 變址分析運(yùn)算流圖中的輸入輸出序列的順序，輸出按順序，輸入是“碼位倒置” 的順序。見(jiàn)圖。自然順序進(jìn)制表示碼位倒置碼位倒置順序0000000010011004223011110641000011510110156110011371111117碼位倒置順序X(0)X(7)碼位倒置的變址處理在實(shí)際運(yùn)算中，直接將輸入數(shù)據(jù) x(n)按碼位倒置的順序排好輸入很不 方便，一般總是先按自然順序輸入存儲(chǔ)單元，然后

11、通過(guò)變址運(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按頻率抽取(DIF )的FTT除時(shí)間抽取法外，另外一種普遍使用的FFT結(jié)構(gòu)是頻率抽取法。頻率抽取法將輸入序列不是按奇、偶分組，而是將N點(diǎn)DFT寫成前后兩部分：N 1 knX(k) DFTx(

12、 n)x(n)WNn 0(N/2) 1N 1knknx(n)Wz +x(n)Wzn 0n N/2N /2 1=x( n)W0n 0N /2 1x(n N /2)WN(n N/2)kn 0N /2 1=x( n) wNN/2沐 x( n N/2)W0因?yàn)閣NN/2i,wNN/2)k( i)k, k為偶數(shù)時(shí)(i)k i, k為奇數(shù)時(shí)(1)k 1，由此可將X(k)分解為偶數(shù)組和奇數(shù)組:N /2 1X(k)=x( n) ( 1)kx( n N/2)Wkn 0N/2 12nrX(2r)=x(n) x(n N /2)Wnn 0N /2 1x( n) x(n N/2)WN：2n 0N /2 1X(2r 1)

13、=x(n) x(n N/2)wN"小n 0N /2 1x( n) x(n N/2)WN>N；r/2n 0n 0,1,N/21令 x1(n) x(n) x(n N/2)x2(n) x(n) x(n N/2)W這兩個(gè)序列都是 N/2點(diǎn)的序列，對(duì)應(yīng)的是兩個(gè)N/2點(diǎn)的DFT運(yùn)算:N/2 1nrX(2r)=X1(n) Wn/2n 0N /2 1rnX(2r 1)=X2(n)W/2n 0這樣，同樣是將一個(gè) N點(diǎn)的DFT分解為兩個(gè)N/2點(diǎn)的DFT 了。頻率抽選法 對(duì)應(yīng)的碟形運(yùn)算關(guān)系圖如下：對(duì)于N=8時(shí)頻率抽取法的 FFT流圖如下:OQOOC占 Q 口 *1- *1* 1- o 1 2 3 J

14、- 5 6 7 I-I uilJP xxxx XXX點(diǎn)FT2 D點(diǎn)FT2D點(diǎn)FT z D點(diǎn)FT2D卩4醫(yī)伍.卩宙07) XIXI旳x(x(xxx(IOJ1 )21可叫5J6J7) fl> n H_ n xxxxxxxxo 4o_IJ 0 4 2 6 15 3 7 卅應(yīng)旳斤XI用x(x(oo0'c殆o o -1* *-14 4-14 *-1這種分組的辦法由于每次都是按輸出X(k)在頻域的順序上是屬于偶數(shù)還是奇數(shù)來(lái)分組的，稱為頻率抽取法。與前面按時(shí)間抽取的方法相比，相同點(diǎn) 問(wèn)題：如何利用快速算法計(jì)算IDFT ？分析IDFT的公式：1 N 1x(n) IDFT X(k) 丄X(k)WN

15、nk,n 0,1, N 1N k o比較DFT的公式：N 1X(k) DFT x(n)x(n)Wk,k 0,1, , N 1n 0得知可用兩種方法來(lái)實(shí)現(xiàn)IDFT的快速算法：(1)只要把DFT運(yùn)算中的每1一個(gè)系數(shù) W該為wNnk，并且最后再乘以常數(shù)，就可以用時(shí)間抽取法N或頻率抽取的FFT算法來(lái)直接計(jì)算IDFT o這種方法需要對(duì) FFT的程序和參數(shù)稍加改動(dòng)才能實(shí)現(xiàn)。 (2) 因?yàn)? N 1 * nk * 1 *x(n) X (k)WN DFTX (k), n 0,1, ,N 1，也就 N k oN是說(shuō)，可先將 X(k)取共軛變換，即將 X(k)的虛部乘以1,就可直接調(diào)用 FFT的程序，最后再對(duì)運(yùn)算

16、結(jié)果取一次共軛變換并乘以常數(shù)1/N即可得到x(n)的值。這種方法中，F(xiàn)FT運(yùn)算和IFFT運(yùn)算都可以共用一個(gè)子程序塊， 在使用通用計(jì)算機(jī)或用硬件實(shí)現(xiàn)時(shí)比較方便。混合基FFT算法以上討論的是基2的FFT算法，即N 2M的情況，這種情況實(shí)際 上使用得最多，這種 FFT運(yùn)算，程序簡(jiǎn)單，效率很高，用起來(lái)很方便。另 外，在實(shí)際應(yīng)用時(shí)，有限長(zhǎng)序列的長(zhǎng)度N到底是多少在很大程度時(shí)是由人為因素確定的，因此，大多數(shù)場(chǎng)合人們可以將N選定為N 2M，從而可以直接調(diào)用以2為基數(shù)的FFT運(yùn)算程序。如果長(zhǎng)度N不能認(rèn)為確定，而 N的數(shù)值又不是以2為基數(shù)的整數(shù)次 方，一般可有以下兩種處理方法：(1) 將x(n)用補(bǔ)零的方法延長(zhǎng)，

17、使N增長(zhǎng)到最鄰近的一個(gè)N 2M數(shù)值。例如，N=30,可以在序列x(n)中補(bǔ)進(jìn)x(30) = x(31)=0兩個(gè)零值點(diǎn)， 使N=32。如果計(jì)算FFT的目的是為了了解整 個(gè)頻譜，而不是特定頻率點(diǎn)，則此法可行。因?yàn)橛邢揲L(zhǎng)序列補(bǔ) 零以后并不影響其頻譜X (ejw )，只是頻譜的采樣點(diǎn)數(shù)增加而已。(2) 如果要求特定頻率點(diǎn)的頻譜，則N不能改變。如果 N為復(fù)合數(shù)，則可以用以任意數(shù)為基數(shù)的 FFT 算法來(lái)計(jì)算。 快速傅里葉變換的基本思想就是要將 DFT 的運(yùn)算盡量分小。例如， N=6 時(shí)，可以按照N=3 X2分解，將6點(diǎn) DFT分解為3組2點(diǎn) DFT。舉例： N=9 時(shí)的快速算法。4.2 快速傅里葉變換的應(yīng)

18、用凡是可以利用傅里葉變換來(lái)進(jìn)行分析、 綜合、 變換的地方， 都可以利 用 FFT 算法及運(yùn)用數(shù)字計(jì)算技術(shù)加以實(shí)現(xiàn)。 FFT 在數(shù)字通信、語(yǔ)音信號(hào)處 理、圖像處理、匹配濾波以及功率譜估計(jì)、仿真、系統(tǒng)分析等各個(gè)領(lǐng)域都得 到了廣泛的應(yīng)用。但不管 FFT 在哪里應(yīng)用，一般都以卷積積分或相關(guān)積分 的具體處理為依據(jù)，或者以用 FFT 作為連續(xù)傅里葉變換的近似為基礎(chǔ)。利用 FFT 求線性卷積快速卷積在實(shí)際中常常遇到要求兩個(gè)序列的線性卷積。 如一個(gè)信號(hào)序列 x(n) 通過(guò)FIR濾波器時(shí)，其輸出 y(n)應(yīng)是x(n)與h(n)的卷積：y(n) x(n) h(n) x(m)h(n m)m有限長(zhǎng)序列x(n)與h(n

19、)的卷積的結(jié)果y(n)也是一個(gè)有限長(zhǎng)序列。假設(shè) x(n)與 h(n)的長(zhǎng)度分別為 N1和N2，貝U y(n)的長(zhǎng)度為N=N1+N2-1。若通過(guò)補(bǔ)零使 x(n)與h(n)都加長(zhǎng)到N點(diǎn)，就可以用圓周卷積來(lái)計(jì)算線性卷積。這樣得到用 FFT運(yùn)算來(lái)求y(n)值(快速卷積)的步驟如下：(1) 對(duì)序列x(n)與 h( n)補(bǔ)零至長(zhǎng)為 N ,使 N > N1+N2-1 ,并且N 2M (M為整數(shù))，即x(n), n 0,1, ,N1 1x(n)0, n N1,N1 1, ,N 1h(n), n 0,1, ,N2 1h(n)0, n N2,N2 1, ,N 1(2) 用FFT計(jì)算x(n)與h(n)的離散傅

20、里葉變換x(n) (FFT)X(k)(N 點(diǎn))h(n) (FFT)H(k)(N 點(diǎn))(3) 計(jì)算 Y(k)=X(k)H(k)(4) 用IFFT計(jì)算Y(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ǔ)零的方法來(lái)繞過(guò)這個(gè)障礙。設(shè)兩個(gè)離散時(shí)間信號(hào) x(n)與y(n)為已知，離散互相關(guān)

21、函數(shù)記作 Rxy (n),定義為Rxy(n)x(m)y(n m)m如果x(n)與y(n)的序列長(zhǎng)度分別為 N1和N2，則用FFT求相關(guān)的計(jì)算步驟 如下：(1 )對(duì)序列x(n)與y( n)補(bǔ)零至長(zhǎng)為N ,使N > N1+N2-1 ,并且N 2m (M為整數(shù))，即x(n)x(n), n0,1, ,N110, nN1,N1 1,N1y(n)y(n), n0,1, ,N210, nN2,N2 1,N1(2)用FFT計(jì)算x(n)與y(n)的離散傅里葉變換x(n)(FFT) X(k)( N 點(diǎn))y(n)(FFT) Y(k)N 點(diǎn))(3) 將X(k)的虛部lmX(k)改變符號(hào)，求得其共軛 X*(k)(4) 計(jì)算 Rxy(k)=x*(k)Y(k)(5) 用IFFT求得相關(guān)序列Rxy(n)Rxy(n) = IFFT Rxy(k)(n 點(diǎn))如