快速傅里葉變換(FFT).ppt

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

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