按時間抽取的基2FFT算法分析

.第四章快速傅里葉變換有限長序列可以通過離散傅里葉變換(DFT)將其頻域也離散化成有限長感謝閱讀序列.但其計算量太大,很難實時地處理問題,因此引出了快速傅里葉變換謝謝閱讀(FFT).1965年，Cooley和Tukey提出了計算離散傅里葉變換（DFT）的謝謝閱讀快速算法，將DFT的運算量減少了幾個數(shù)量級。從此，對快速傅里葉變換感謝閱讀（FFT）算法的研究便不斷深入，數(shù)字信號處理這門新興學(xué)科也隨FFT的出謝謝閱讀現(xiàn)和發(fā)展而迅速發(fā)展。根據(jù)對序列分解與選取方法的不同而產(chǎn)生了FFT的感謝閱讀多種算法，基本算法是基２DIT和基２DIF。FFT在離散傅里葉反變換、線感謝閱讀性卷積和線性相關(guān)等方面也有重要應(yīng)用?？焖俑道锶~變換（FFT）是計算離散傅里葉變換（DFT）的快速算法。精品文檔放心下載DFT的定義式為N1x(n)WknR(k)X(k)=NNn0在所有復(fù)指數(shù)值Wkn的值全部已算好的情況下，要計算一個X(k)需要N精品文檔放心下載N次復(fù)數(shù)乘法和N－1次復(fù)數(shù)加法。算出全部N點X(k)共需N2次復(fù)數(shù)乘法和N(N1)次復(fù)數(shù)加法。即計算量是與N2成正比的。精品文檔放心下載FFT的基本思想：將大點數(shù)的DFT分解為若干個小點數(shù)DFT的組合，謝謝閱讀從而減少運算量。.N因子具有以下兩個特性，可使DFT運算量盡量分解為小點數(shù)的DFT感謝閱讀運算：（1）周期性：W(kN)nWknW(nN)kNNN（2）對稱性：W(kN/2)WkNN利用這兩個性質(zhì)，可以使DFT運算中有些項合并，以減少乘法次數(shù)。例子：謝謝閱讀求當(dāng)N＝4時，X(2)的值X(2)

3

x(n)W

2n4

x(0)W04

x(1)W

24

x(2)W

44

x(3)W64n0[x(0)＝[x(0)

x(2)]W0[x(1)x(3)]W謝謝閱讀4x(2)]－[x(1)x(3)]W04

2 (周期性)4(對稱性)通過合并，使乘法次數(shù)由4次減少到1次，運算量減少。謝謝閱讀FFT的算法形式有很多種，但基本上可以分為兩大類：按時間抽取謝謝閱讀（DIT）和按頻率抽?。―IF）。4.1按時間抽?。―IT）的FTT為了將大點數(shù)的DFT分解為小點數(shù)的DFT運算，要求序列的長度N為精品文檔放心下載復(fù)合數(shù)，最常用的是N2M的情況（M為正整數(shù)）。該情況下的變換稱為感謝閱讀基2FFT。下面討論基2情況的算法。先將序列x(n)按奇偶項分解為兩組x(2r)x(r)r0,1,,N11x(2r1)x(r)22.將DFT運算也相應(yīng)分為兩組N1X(k)DFT[x(n)]x(n)Wkn謝謝閱讀N0N1x(n)Wkn＋N1x(n)Wkn謝謝閱讀NNn0n0n為偶數(shù)n為奇數(shù)N/21N/21＝x(2r)W2rkx(2r1)W(2r1)kNNr0r0N/21N/21＝x(r)W2rkWkx(r)W2rk1NN2Nr0r0N/21WkN/21（因為W2rkWrk）＝x(r)Wrkx(r)Wrk1N/2N2N/2NN/2r0r0X(k)WkX(k)1N2其中X(k)、X(k)分別是x(n)、x(n)的N/2點的DFT1212X(k)＝x(r)Wrkx(2r)Wrk,0kN1N/21N/2111N/2N/22r0r0N/21N/21,0kN1X(k)＝x(r)Wrkx(2r1)Wrk22N/2N/22r0r0至此，一個N點DFT被分解為兩個N/2點的DFT。謝謝閱讀上面是否將全部N點的X(k)求解出來了？分析：X(k)和X(k)只有N/2個點（k0,1,,N1），則由122X(k)X(k)WkX(k)只能求出X(k)的前N/2個點的DFT，要求出感謝閱讀1 N 2全部N點的X(k)，需要找出X(k)、X(k)和X(kN/2)的關(guān)系，其感謝閱讀1 2.k0,1,,N21。由式子X(k)X(k)WkX(k)可得N21謝謝閱讀X(kN/2)X(kN/2)WkN/2X(kN/2)化簡得感謝閱讀1 N 2X(kN/2)＝X(k)WkX(k謝謝閱讀1 N 2這樣N點DFT可全部由下式確定出來：X(k)X(k)WkX(k)1N2X(kN/2)X(k)WkX(k)1N2

)，k0,1, ,N21k0,1,,N1（＊）2上式可用一個專用的碟形符號來表示，這個符號對應(yīng)一次復(fù)乘和兩次復(fù)加運感謝閱讀算。aaWkbNbaWkbWk-1NN圖 蝶形運算符號通過這樣的分解以后，每一個N／2點的DFT只需要(N)2N2次復(fù)數(shù)感謝閱讀2 4乘法，兩個N/2點的DFT需要2(N)2N2次復(fù)乘，再加上將兩個N／2謝謝閱讀2 2點DFT合并成為N點DFT時有N／2次與W因子相乘，一共需要謝謝閱讀N2NN2222次復(fù)乘?？梢?，通過這樣的分解，運算量節(jié)省了近一半。因為N2M，N/2仍然是偶數(shù)，因此可以對兩個N/2點的DFT再感謝閱讀分別作進一步的分解，將兩個N/2點的DFT分解成兩個N/4點的DFT。感謝閱讀.例如對x(r)，可以在按其偶數(shù)部分及奇數(shù)部分進行分解：精品文檔放心下載1x(2l)x(l)l0,1,,N131x(2l1)x(l)414則的運算可相應(yīng)分為兩組：N/41N/41X(k)＝x(2l)W2lkx(2l1)W(2l1)k11N/21N/2l0l0N/41WkN/41＝x(l)Wlkx(l)Wlk3N/4N/24N/4l0l0X(k)WkX(k)k0,1,,N13N/244將系數(shù)統(tǒng)一為以Ｎ為周期，即WkW2k，可得N/2NX(k)X(k)W2kX(k)Nk0,1,,13N41X(kN/4)X(k)W2kX(k)413N4同樣，對X(k)也可進行類似的分解。一直分解下去，最后是２點的精品文檔放心下載2DFT，２點DFT的運算也可用碟形符號來表示。這樣，對于一個N238精品文檔放心下載的DFT運算，其按時間抽取的分解過程及完整流圖如下圖所示。謝謝閱讀.這種方法，由于每一步分解都是按輸入序列在時域上的次序是屬于偶數(shù)精品文檔放心下載還是奇數(shù)來抽取的，故稱為“時間抽取法”。分析上面的流圖，N 2M，一共要進行M次分解，構(gòu)成了從x(n)到感謝閱讀X(k)的M級運算過程。每一級運算都是由N/2個蝶形運算構(gòu)成，因此每一謝謝閱讀級運算都需要N/2次復(fù)乘和N次復(fù)加，則按時間抽取的M級運算后總共精品文檔放心下載.需要復(fù)數(shù)乘法次數(shù)：mFNMNlog2N復(fù)數(shù)加法次數(shù)：aNMNlogNF2根據(jù)上面的流圖，分析ＦＦＴ算法的兩個特點，它們對ＦＦＴ的軟硬件感謝閱讀構(gòu)成產(chǎn)生很大的影響。（１）原位運算也稱為同址運算，當(dāng)數(shù)據(jù)輸入到存儲器中以后，每一級運算的結(jié)果仍然存儲謝謝閱讀在原來的存儲器中，直到最后輸出，中間無需其它的存儲器。根據(jù)運算流圖謝謝閱讀分析原位運算是如何進行的。原位運算的結(jié)構(gòu)可以節(jié)省存儲單元，降低設(shè)備謝謝閱讀成本。（２）變址分析運算流圖中的輸入輸出序列的順序，輸出按順序，輸入是“碼位倒置”精品文檔放心下載的順序。見圖。自然順序二進制表示碼位倒置碼位倒置順序00000000100110042010010230111106.41000011510110156110011371111117碼位倒置順序01234567X(0)X(4)X(2)X(6)X(1)X(5)X(3)X(7)碼位倒置的變址處理在實際運算中，直接將輸入數(shù)據(jù)x(n)按碼位倒置的順序排好輸入很不感謝閱讀方便，一般總是先按自然順序輸入存儲單元，然后通過變址運算將自然順序感謝閱讀的存儲換成碼位倒置順序的存儲，這樣就可以進行FFT的原位運算。變質(zhì)謝謝閱讀的功能如圖所示。用軟件實現(xiàn)是通用采用雷德（Rader）算法，算出I的倒感謝閱讀序Ｊ以后立即將輸入數(shù)據(jù)X(I)和X(J)對換。盡管變址運算所占運算量的比例精品文檔放心下載很小，但對某些高要求的應(yīng)用（尤其在實時信號處理中），也可設(shè)法用適當(dāng)感謝閱讀的電路結(jié)構(gòu)直接實現(xiàn)變址。例如單片數(shù)字信號處理器TMS320C25就有專謝謝閱讀用于FFT的二進制碼變址模式。4.２按頻率抽?。―IF）的FTT除時間抽取法外，另外一種普遍使用的FFT結(jié)構(gòu)是頻率抽取法。頻率謝謝閱讀.抽取法將輸入序列不是按奇、偶分組，而是將Ｎ點DFT寫成前后兩部分：謝謝閱讀N1X(k)DFT[x(n)]x(n)Wkn謝謝閱讀N0(N/2)x1(n)Wkn＋N1x(n)Wkn感謝閱讀NNn0nN/2N/21N/21＝x(n)Wnkx(nN/2)W(nN/2)kNNn0n0N/21＝[x(n)W(N/2)kx(nN/2)]WnkNNn0因為WN/21,W(N/2)k(1)k，k為偶數(shù)時(1)k1，k為奇數(shù)時NN(1)k1，由此可將X(k)分解為偶數(shù)組和奇數(shù)組：N/21X(k)＝ [x(n)(1)kx(nN/2)]Wnk感謝閱讀N0N/21X(2r)＝ [x(n)x(nN/2)]W2nr感謝閱讀N0N/2[1x(n)x(nN/2)]Wnr謝謝閱讀N/20N/21X(2r1)＝ [x(n)x(nN/2)]W(2r1)n感謝閱讀N0N/2[1x(n)x(nN/2)]WnWnr感謝閱讀NN/2n0x(n)x(n)x(nN/2)n0,1,,N/21令1x(n)[x(n)x(nN/2)]Wn2N這兩個序列都是N/2點的序列，對應(yīng)的是兩個N/2點的DFT運算：感謝閱讀.X(2r

N/21)＝ x(n)]W1

nrN/20X(2r

N/211)＝ x(n)W2

rnN/20這樣，同樣是將一個N點的DFT分解為兩個N/2點的DFT了。頻率抽選精品文檔放心下載法對應(yīng)的碟形運算關(guān)系圖如下：aabb(ab)WnN-1WnN對于N=8時頻率抽取法的FFT流圖如下：.這種分組的辦法由于每次都是按輸出X(k)在頻域的順序上是屬于偶數(shù)還是謝謝閱讀奇數(shù)來分組的，稱為頻率抽取法。與前面按時間抽取的方法相比，相同點感謝閱讀問題：如何利用快速算法計算IDFT？分析IDFT的公式：x(n)IDFT[X(k)]1N1X(k)Wnk,n0,1, ,N1謝謝閱讀N Nk0比較DFT的公式：(k)DFT[x(n)]N1x(n)Wnk,k0,1,,N1謝謝閱讀N0得知可用兩種方法來實現(xiàn)IDFT的快速算法：（１）只要把DFT運算中的每精品文檔放心下載一個系數(shù)Wnk該為Wnk，并且最后再乘以常數(shù)1，就可以用時間抽取法精品文檔放心下載N N N.或頻率抽取的FFT算法來直接計算IDFT。這種方法需要對FFT的程序和參精品文檔放心下載數(shù) 稍 加 改 動 才 能 實 現(xiàn) 。（ ２ ） 因 為謝謝閱讀x(n)1N1X*(k)Wnk]*1{DFT[X*(k)]},n0,1,,N1，也就[NNN0是說，可先將X(k)取共軛變換，即將X(k)的虛部乘以－１，就可直接調(diào)用精品文檔放心下載FFT的程序，最后再對運算結(jié)果取一次共軛變換并乘以常數(shù)1/N即可得到精品文檔放心下載x(n)的值。這種方法中，F(xiàn)FT運算和IFFT運算都可以共用一個子程序塊，精品文檔放心下載在使用通用計算機或用硬件實現(xiàn)時比較方便。4.1.3混合基FFT算法以上討論的是基2的FFT算法，即N2M的情況，這種情況實際上使用得最多，這種FFT運算，程序簡單，效率很高，用起來很方便。另精品文檔放心下載外，在實際應(yīng)用時，有限長序列的長度N到底是多少在很大程度時是由人謝謝閱讀為因素確定的，因此，大多數(shù)場合人們可以將N選定為N2M，從而可精品文檔放心下載以直接調(diào)用以２為基數(shù)的FFT運算程序。如果長度N不能認(rèn)為確定，而N的數(shù)值又不是以2為基數(shù)的整數(shù)次精品文檔放心下載方，一般可有以下兩種處理方法：（１） 將x(n)用補零的方法延長，使N增長到最鄰近的一個精品文檔放心下載2M數(shù)值。例如，N=30，可以在序列x(n)中補進x(30)＝精品文檔放心下載.x(31)＝０兩個零值點，使N=32。如果計算FFT的目的是為了謝謝閱讀了解整個頻譜，而不是特定頻率點，則此法可行。因為有限長謝謝閱讀序列補零以后并不影響其頻譜X(ejw)，只是頻譜的采樣點數(shù)增謝謝閱讀加而已。（２）如果要求特定頻率點的頻譜，則N不能改變。如果N為復(fù)合謝謝閱讀數(shù)，則可以用以任意數(shù)為基數(shù)的FFT算法來計算?？焖俑道锶~變換的謝謝閱讀基本思想就是要將DFT的運算盡量分小。例如，N=6時，可以按照精品文檔放心下載N=3×２分解，將６點DFT分解為３組２點DFT。感謝閱讀舉例：N=9時的快速算法。4.2 快速傅里葉變換的應(yīng)用凡是可以利用傅里葉變換來進行分析、綜合、變換的地方，都可以利精品文檔放心下載FFT算法及運用數(shù)字計算技術(shù)加以實現(xiàn)。FFT在數(shù)字通信、語音信號處理、圖像處理、匹配濾波以及功率譜估計、仿真、系統(tǒng)分析等各個領(lǐng)域都得到了廣泛的應(yīng)用。但不管FFT在哪里應(yīng)用，一般都以卷積積分或相關(guān)積分的具體處理為依據(jù)，或者以用FFT作為連續(xù)傅里葉變換的近似為基礎(chǔ)。感謝閱讀4.2.1利用FFT求線性卷積—快速卷積在實際中常常遇到要求兩個序列的線性卷積。如一個信號序列x(n)通過謝謝閱讀.FIR濾波器時，其輸出y(n)應(yīng)是x(n)與h(n)的卷積：精品文檔放心下載y(n)x(n)h(n)

x(m)h(nm)m有限長序列x(n)與h(n)的卷積的結(jié)果y(n)也是一個有限長序列。假設(shè)x(n)感謝閱讀與h(n)的長度分別為N1和N2，則y(n)的長度為N=N1+N2-1。若通過精品文檔放心下載補零使x(n)與h(n)都加長到N點，就可以用圓周卷積來計算線性卷積。這謝謝閱讀樣得到用FFT運算來求y(n)值（快速卷積）的步驟如下：精品文檔放心下載（１）對序列x(n)與h(n)補零至長為N，使N≥N1+N2-1，并且謝謝閱讀N2M(M為整數(shù))，即x(n),n0,1,,N11x(n)0,nN1,N11,,N1h(n),n0,1,,N21h(n)0,nN2,N21,,N1（２）用FFT計算x(n)與h(n)的離散傅里葉變換x(n)(FFT)X(k)（N點）h(n)(FFT)H(k)（N點）（３）計算Y(k)=X(k)H(k)（４）用IFFT計算Y(k)的離散傅里葉反變換得：y(n)=IFFT[Y(k)]（N點）.4.2.2利用FFT求相關(guān)—快速相關(guān)互相關(guān)及自相關(guān)的運算已廣泛的應(yīng)用于信號分析與統(tǒng)計分析，應(yīng)用于連謝謝閱讀續(xù)時間系統(tǒng)也用于離散事件系統(tǒng)。用FFT計算相關(guān)函數(shù)稱為快速相關(guān)，它與快速卷積完全類似，不同的精品文檔放心下載是一個應(yīng)用離散相關(guān)定理，另一個應(yīng)用離散卷積定理。同樣都要注意到離散謝謝閱讀傅里葉變換固有的周期性，也同樣用補零的方法來繞過這個障礙。精品文檔放心下載設(shè)兩個離散時間信號x(n)與y(n)為已知，離散互相關(guān)函數(shù)記作R(n)，謝謝閱讀xy定義為R(n)x(m)y(nm)xy如果x(n)與y(n)的序列長度分別為N1和N2，則用FFT求相關(guān)的計算步驟感謝閱讀如下：（１）對序列x(n)與y(n)補零至長為N，使N≥N1+N2-1，并且精品文檔放心下載2M(M為整數(shù))，即x(n),n0,1, ,N11x(n)0, nN1,N11, ,N1y(n),n0,1, ,N21y(n)0, nN2,N21, ,N1感謝閱讀（２）用FFT計算x(n)與y(n)的離散傅里葉變換精品文檔放心下載x(n)(FFT)X(k) （N點）謝謝閱讀.y(n)(FFT)Y(k) （N點）精品文檔放心下載（３）將X(k)的虛部Im[X(k)]改變符號，求得其共軛