《快速傅里葉變換(FFT).ppt》由會員分享，可在線閱讀，更多相關《快速傅里葉變換(FFT).ppt（89頁珍藏版）》請在裝配圖網(wǎng)上搜索。

第4章快速傅里葉變換,4.1引言4.2直接計算DFT的問題及改進的途徑4.3按時間抽?。―IT）的基2-FFT算法4.4按頻率抽?。―IF）的基2-FFT算法4.5IDFT的高效算法4.6FFT的其他應用—快速卷積,學習目標,理解按時間抽取的基-2FFT算法的原理、運算流圖、所需計算量和算法特點；理解按頻率抽取的基-2FFT算法的原理、運算流圖、所需計算量和算法特點；理解IFFT算法；理解線性卷積的FFT算法及分段卷積（即塊卷積）方法。,4.1引言,快速傅里葉變換（FFT）并不是一種新的變換，而是離散傅里葉變換（DFT）的一種快速算法。在信號的頻譜分析、系統(tǒng)的分析、設計和實現(xiàn)中都會用到DFT的計算。DFT的計算量太大，很難對問題進行實時處理，難以實用。1965年首次發(fā)現(xiàn)了DFT運算的一種快速算法以后，人們開始認識到DFT運算的一些內(nèi)在規(guī)律，從而很快地發(fā)展和完善了一套高速有效的運算方法，這就是快速傅里葉變換（FFT）的算法。FFT出現(xiàn)后使DFT的運算大大簡化，運算時間一般可縮短一二個數(shù)量級之多，使DFT的運算在實際中真正得到了廣泛的應用。,4.2直接計算DFT的問題及改進的途徑,一、直接計算DFT的運算量問題設x(n)為N點有限長序列，其DFT為,k=0,1,…,N-1,反變換（IDFT）為,n=0,1,…,N-1,運算量,一個X(k),復數(shù)乘法,復數(shù)加法,N,N-1,N2,N(N-1),N個X(k),一次復數(shù)乘法需用四次實數(shù)乘法和二次實數(shù)加法；一次復數(shù)加法需二次實數(shù)加法。,二、改進的途徑,x(n)長序列————短序列WNkn,4.3按時間抽?。―IT）的基-2FFT算法,一、算法原理1.一次分解N→N/2設序列x(n)長度為N，且滿足N=2M，M為正整數(shù)。按n的奇偶把x(n)分解為兩個N/2點的子序列：,,k=0,1,…..,N/2-1,,利用周期性求X(k)的后半部分,,,,,,,,,x(0),x(1),x(2),x(3),x(4),x(5),x(6),x(7),,,,,,-1,-1,-1,-1,WN0,WN1,WN2,WN3,,,,N/2點DFT,N/2點DFT,,,2.二次分解N/2→N/4,X2(k)也可進行同樣的分解：,,,,,-1,-1,-1,-1,WN0,WN1,WN2,WN3,,N/2點DFT分解為兩個N/4點DFT,,一個N=8點DFT分解為四個N/4點DFT,,,N=8，四個N/4點DFT即四個2點DFT，其輸出分別為：X3(k)，X4(k)，X5(k)，X6(k)，k=0,1,,,,,N=8按時間抽取的FFT運算流圖,X3(0),X3(1),X4(0),X4(1),X5(0),X5(1),X6(0),X6(1),N=8時共有三級蝶形運算，每一級有N/2=4個蝶形,X1(0),X1(1),X1(2),X1(3),X2(0),X2(1),X2(2),X2(3),x3(0),x3(1),x4(0),x4(1),x5(0),x5(1),x6(0),x6(1),二、按時間抽取的FFT算法與直接計算DFT運算量的比較N=2M時，共有M級蝶形，每級都由N/2個蝶形運算組成；每個蝶形需要一次復乘、二次復加；每級運算都需N/2次復乘和N次復加；M級運算總共需要：,以乘法為例，直接DFT復數(shù)乘法次數(shù)是N2，F(xiàn)FT復數(shù)乘法次數(shù)是(N/2)lbN；直接計算DFT與FFT算法的復數(shù)乘法計算量之比為：,當N=2048時，這一比值為372.4，即直接計算DFT的運算量是FFT運算量的372.4倍；當點數(shù)N越大時，F(xiàn)FT的優(yōu)點更為明顯。,對一個連續(xù)時間信號xa(t)采樣1秒得到一個4096個采樣點的序列，若計算采樣信號的4096點DFT。假定僅對200≤f≤300Hz頻率范圍所對應的DFT采樣點感興趣。（1）若直接用DFT，要計算這些值需要多少次復乘？MN=1014096=413696（2）若用基2的DIT-FFT計算，則需要多少次復乘？N/2log2N=4096/2log24096=24576,思考題,N點x(n)序列，構造新序列y(n)=x(n/2),n為偶數(shù)時，y(n)=0，n為奇數(shù)時，n=0,1,2,…2N-1，求：Y(K)與X(K)的關系，K=0,1,2,….2N-1,例題：,解：由DIT-FFT可得y(2n)=y1(n)=x(n),Y1(K)=X(K)y(2n+1)=y2(n)=0,Y2(K)=0n=0,1,….,N-1,已知x(n)長度為N（N為偶數(shù)）。定義兩個長度為N/2的序列如下:其中，G(k)=DFT[g(n)],H(k)=DFT[h(n)],分別為N/2長。試利用G(k)和H(k)表示出X(k)=DFT[x(n)]，k=0,1,……N-1。,補充題,提示,三、按時間抽取的FFT算法的特點,1.原位運算（同址運算）,第一級蝶形運算,第二級蝶形運算,第三級蝶形運算,,m表示第m級迭代，k,j為數(shù)據(jù)所在行數(shù)；,某一級的兩個節(jié)點k和j的節(jié)點變量進行蝶形運算后，得到結果為下一級k,j兩節(jié)點的節(jié)點變量，即每個蝶形的輸入、輸出數(shù)據(jù)節(jié)點同在一條水平線上；與其他節(jié)點變量無關，即蝶形的兩個輸出值仍放回蝶形的兩個輸入所在的存儲器中；每級的N/2個蝶形運算全部完成后，再開始下一級的蝶形運算；這樣經(jīng)過M級運算后，原存放輸入數(shù)據(jù)的N個存儲單元中依次存放輸出的N個值；這種利用同一存儲單元存放蝶形計算輸入、輸出數(shù)據(jù)的方法稱為原位運算?？梢怨?jié)省存儲單元,降低設備成本。,2.倒位序規(guī)律基2的DIT-FFT的輸出X(k)按正常順序排列在存儲單元中，即按X(0)，X(1)，…，X(7)的順序排列；輸入x(n)卻不是按自然順序存儲的，而是按x(0)，x(4)，…，x(7)的順序存入存儲單元，看起來好像是“混亂無序”的；實際上是有規(guī)律的，我們稱之為倒位序。,n用二進制數(shù)表示為(n2n1n0)2（當N=8=23時，二進制為三位）第一次分組，n為偶數(shù)（相當于n的二進制數(shù)的最低位n0=0）在上半部分，n為奇數(shù)（相當于n的二進制數(shù)的最低位n0=1）在下半部分。下一次則根據(jù)次最低位n1為“0”或是“1”來分偶奇（而不管原來的子序列是偶序列還是奇序列），如此繼續(xù)分下去，直到最后N個長度為1的子序列。,倒位序,N=8時的自然順序二進制數(shù)和相應的倒位序二進制數(shù),先按自然順序?qū)⑤斎胄蛄写嫒氪鎯卧?，為了得到倒位序的排列，我們通過變址運算來完成；如果輸入序列的自然順序號I用二進制數(shù)（例如n2n1n0）表示，則其倒位序J對應的二進制數(shù)就是（n0n1n2），這樣，在原來自然順序時應該放x(I)的單元，現(xiàn)在倒位序后應放x(J)。,000,100,010,110,001,101,011,111,順序數(shù)I的起始、終止值分別為1和N-2；倒序數(shù)J的起始值為N/2；為避免重復調(diào)換，只對I>NL=M+N-1≈M,短序列補很多零，長序列需全部輸入后才能計算存儲容量大運算時間長，處理延時很大，難于實時處理怎么解決？——塊卷積（重疊相加和重疊保留法）,2．重疊相加法設h(n)的點數(shù)為N，將x(n)分解為很多段，每段為m點，各段互不重疊，m和N的數(shù)量級相同，用xi(n)表示x(n)的第i段：,xi(n)為m點，yi(n)為（m+N-1）點；相鄰兩段輸出序列必然有（N-1）個點發(fā)生重疊，即前一段的后（N-1）個點和后一段的前（N-1）個點相重疊；將重疊部分相加再和不重疊的部分共同組成輸出。,,,特點：x(n)分段各數(shù)據(jù)子段互不重疊；h(n)與xi(n)各子段所作為線性卷積得yi(n)；yi(n)數(shù)據(jù)間有N-1點重疊；最后的卷積結果y(n)為各子段線性卷積yi(n)之和。,3．重疊保留法將x(n)分段，每段L個點，序列中補零處不補零，而在每一段的前邊補上前一段保留下來的（M-1）個輸入序列值，組成N=L+M-1點序列xi(n)；如果L+M-1<2m，則可在每段序列末端補零值點，補到長度為2m；用DFT實現(xiàn)h(n)和xi(n)的N點圓周卷積，則其每段圓周卷積結果的前（M-1）個點的值不等于線性卷積值，必須舍去。,重疊保留法示意圖,,,重疊保留法示意圖,用保留信號代替補零后的局部混疊現(xiàn)象,用保留信號代替補零后的局部混疊現(xiàn)象,為了說明以上說法的正確性，我們來看一看圖3-29。任一段xi(n)（為N點）與h(n)（原為M點，補零值后也為N點）的N點圓周卷積,由于h(m)為M點，補零后作N點圓周移位時，在n=0,1,…,M-2的每一種情況下，h((n-m))NRN(m)在0≤m≤N-1范圍的末端出現(xiàn)非零值，而此處xi(m)是有數(shù)值存在的，圖4-27（c），（d）為n=0,n=M-2的情況，所以在,0≤n≤M-2,這一部分的yi(n)值中將混入xi(m)尾部與h((n-m))NRN(m)尾部的乘積值，從而使這些點的yi(n)不同于線性卷積結果。但是從n=M-1開始到n=N-1，h((n-m))NRN(m)=h(n-m)（如圖4-26（e），（f）所示），圓周卷積值完全與線性卷積值一樣，yi(n)就是正確的線性卷積值。因而必須把每一段圓周卷積結果的前(M-1)個值去掉，如圖4-26（g）所示。因此，為了不造成輸出信號的遺漏，對輸入分段時，就需要使相鄰兩段有M-1個點重疊（對于第一段，即x0(n)，由于沒有前一段保留信號，則需要在序列前填充M-1個零值點），這樣，若原輸入序列為x′(n)（n≥0時有值），則應重新定義輸入序列,而,0≤n≤N-1,其他n,i=0,1,…,在這一公式中，已經(jīng)把每一段的時間原點放在該段的起始點，而不是x(n)的原點。這種分段方法示于圖4-25中，每段xi(n)和h(n)的圓周卷積結果以yi(n)表示，如圖4-25（b）所示，圖中已標出每一段輸出段開始的(M-1)個點，0≤n≤M-2部分舍掉不用。把相鄰各輸出段留下的序列銜接起來，就構成了最后的正確輸出，即,式中:,M-1≤n≤N-1,其他n,這時，每段輸出的時間原點放在yi′(n)的起始點，而不是y(n)的原點。,