數(shù)字信號(hào)處理31課件

第四節(jié)

基--2按頻率抽取的FFT算法Decimation-in-Frequency(DIF)

(Sander-Tukey)一、算法原理設(shè)輸入序列長(zhǎng)度為N=2M(M為正整數(shù)，將該序列的頻域的輸出序列X(k)(也是M點(diǎn)序列，按其頻域順序的奇偶分解為越來(lái)越短的子序列，稱為基2按頻率抽取的FFT算法。也稱為Sander-Tukey算法。二、算法步驟

1.分組DFT變換：已證明頻域上X(k)按k的奇偶分為兩組，在時(shí)域上x(n)按n的順序分前后兩部分，現(xiàn)將輸入x(n)按n的順序分前后兩部分:前半子序列x(n),0≤n≤N/2-1;后半子序列x(n+N/2),0≤n≤N/2-1;例：N=8時(shí)，前半序列為：x(0),x(1),x(2),x(3);后半序列為：x(4),x(5),x(6),x(7);則由定義輸出（求DFT）3.變量置換--13.變量置換--23.變量置換--34.結(jié)論1一個(gè)N點(diǎn)的DFT被分解為兩個(gè)N/2點(diǎn)DFT。X1(k),X2(k)這兩個(gè)N/2點(diǎn)的DFT按照：可見：如此分解，直至分到2點(diǎn)的DFT為止。4.結(jié)論2三、蝶形流圖表示蝶形單元：時(shí)域中，前后半部表示式用蝶形結(jié)表示。x(n)x(n+N/2)與時(shí)間抽取法的推演過程一樣，由于N=2L,N/2仍為偶數(shù)，所以可以將N/2點(diǎn)DFT的輸出X(k)再分為偶數(shù)組和奇數(shù)組，這樣就將一個(gè)N/2點(diǎn)的DFT分成兩個(gè)N/4點(diǎn)DFT的輸入，也是將N/2點(diǎn)的DFT的輸入上、下對(duì)半分后通過蝶形運(yùn)算而形成，直至最后為2點(diǎn)DFT。將N=8點(diǎn)分解成2個(gè)4點(diǎn)的DIF的信號(hào)流圖4點(diǎn)DFTx(0)x(1)x(2)x(3)4點(diǎn)DFTx(4)x(5)x(6)x(7)X(0)X(2)X(4)X(6)X(1)X(3)X(5)X(7)X1(k)前半部分序列后半部分序列x1(n)x2(n)X2(k)(2)N/2(4點(diǎn))-->N/4(2點(diǎn))FFT

(a)先將4點(diǎn)分解成2點(diǎn)的DIF：因?yàn)?點(diǎn)DIF還是比較麻煩，所以再繼續(xù)分解。（b)一個(gè)2點(diǎn)的DIF蝶形流圖2點(diǎn)DFT2點(diǎn)DFTx1(0)x1(1)x1(2)x1(3)x3(0)x3(1)x4(0)x4(1)X(0)X(4)X(2)X(6)(3)將N/4（2點(diǎn)）DFT再分解成2個(gè)1點(diǎn)的DFT

(a)求2個(gè)一點(diǎn)的DFT最后剩下兩點(diǎn)DFT,它可分解成兩個(gè)一點(diǎn)DFT，但一點(diǎn)DFT就等于輸入信號(hào)本身，所以兩點(diǎn)DFT可用一個(gè)蝶形結(jié)表示。取x3(0)、x3(1)為例。(b)2個(gè)1點(diǎn)的DFT蝶形流圖1點(diǎn)DFTx3(0)1點(diǎn)DFTx3(1)X(0)X(4)進(jìn)一步簡(jiǎn)化為蝶形流圖：X(0)X(4)x3(0)x3(1)(4)一個(gè)完整N=8的按頻率抽取FFT的運(yùn)算流圖x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)X(0)X(4)X(2)X(6)X(1)X(5)X(3)X(7)m=0m=1m=2（6）DIF與DIT比較1相同之處：（1）DIF與DIT兩種算法均為原位運(yùn)算。（2）DIF與DIT運(yùn)算量相同。它們都需要（6）DIF與DIT比較2不同之處：（1）DIF與DIT兩種算法結(jié)構(gòu)倒過來(lái)。DIF為輸入順序，輸出亂序。運(yùn)算完畢再運(yùn)行“二進(jìn)制倒讀”程序。DIT為輸入亂序，輸出順序。先運(yùn)行“二進(jìn)制倒讀”程序，再進(jìn)行求DFT。（2）DIF與DIT根本區(qū)別：在于蝶形結(jié)不同。DIT的復(fù)數(shù)相乘出現(xiàn)在減法之前。DIF的復(fù)數(shù)相乘出現(xiàn)在減法之后。作業(yè)試畫出N=16點(diǎn)的基-2按頻率抽取的FFT流圖（DIF）。一、利用FFT計(jì)算IFFT的思路1將下列兩式進(jìn)行比較二、利用FFT計(jì)算IFFT的思路2利用FFT計(jì)算IFFT時(shí)在命名上應(yīng)注意：(1)把FFT的時(shí)間抽取法，用于IDFT運(yùn)算時(shí)，由于輸入變量由時(shí)間序列x(n)改成頻率序列X(k),原來(lái)按x(n)的奇、偶次序分組的時(shí)間抽取法FFT，現(xiàn)在就變成了按X(k)的奇偶次序抽取了。（2）同樣，頻率抽取的FFT運(yùn)算用于IDFT運(yùn)算時(shí)，也應(yīng)改變?yōu)闀r(shí)間抽取的IFFT。四.直接利用FFT流圖的方法

1.思路前面的兩種IFFT算法，排程序很方便，但要改變FFT的程序和參數(shù)才能實(shí)現(xiàn)。現(xiàn)介紹第三種IFFT算法，則可以完全不必改動(dòng)FFT程序。2.直接利用FFT流圖方法的推導(dǎo)可知：只須將頻域成份一個(gè)求共軛變換，即（1）將X(k)的虛部乘以-1，即先取X(k)的共軛，得X*(k)。(2)將X*(k)直接送入FFT程序即可得出Nx*(n)。(3)最后再對(duì)運(yùn)算結(jié)果取一次共軛變換，并乘以常數(shù)1/N，即可以求出IFFT變換的x(n)的值。此為DFT可用FFT程序3.直接利用FFT流圖方法的注意點(diǎn)（1）FFT與IFFT連接應(yīng)用時(shí)，注意輸入輸出序列的排列順序，即應(yīng)注意是自然順序還是倒序。（2）FFT和IFFT共用同一個(gè)程序時(shí)，也應(yīng)注意利用FFT算法輸入輸出的排列順序，即應(yīng)注意自然順序還是例位序（3）當(dāng)把頻率抽取FFT流圖用于IDFT時(shí)，應(yīng)改稱時(shí)間抽取IFFT流圖。（4）當(dāng)把時(shí)間抽取FFT流圖用于IDFT時(shí)，應(yīng)改稱頻率抽取IFFT流圖。作業(yè)用C語(yǔ)言完成N=128點(diǎn)的DIT，DIF及IDIT，IDIF。第六節(jié)

線性調(diào)頻Z變換一、引入以上提出FFT算法，可以很快地求出全部DFT值。即求出有限長(zhǎng)序列x(n)的z變換X(z)在單位園上N個(gè)等間隔抽樣點(diǎn)zk處的抽樣值。它要求N為高度復(fù)合數(shù)。即N可以分解成一些因子的乘積。例N=2L實(shí)際上：（1）也許對(duì)其它圍線上z變換取樣發(fā)生興趣。如語(yǔ)音處理中，常常需要知道某一圍線z變換的極點(diǎn)所處的復(fù)頻率。（2）只需要計(jì)算單位圓上某一段的頻譜。如窄帶信號(hào)，希望在窄帶頻率內(nèi)頻率抽樣能夠非常密集，提高分辨率，帶外則不考慮。（3）若N是大素?cái)?shù)時(shí)，不能加以分解，又如何有效計(jì)算這種序列DFT。例N=311，若用基2則須補(bǔ)N=28=512點(diǎn)，要補(bǔ)211個(gè)零點(diǎn)。二、問題提出由上面三個(gè)問題提出：為了提高DFT的靈活性，須用新的方法。線性調(diào)頻z變換(CZT)就是適用這種更為一般情況下，由x(n)求X(zk)的快速變換CZT：來(lái)自于雷達(dá)專業(yè)的專用詞匯。三、算法原理

1.定義Z變換采用螺線抽樣,可適用于更一般情況下由x(n)求X(zk)的快速算法,這種變換稱為線性調(diào)頻Z變換(簡(jiǎn)稱CZT).2.CZT公式推導(dǎo)1已知x(n)，0≤n≤N-1,則它的z變換是：為適應(yīng)z可以沿平面內(nèi)更一般的路徑取值，故：沿z平面上的一段螺線作等分角的抽樣，則z的取樣點(diǎn)Zk可表示為：其中M：表示欲分析的復(fù)頻譜的點(diǎn)數(shù)。M不一定等于N。A，都為任意復(fù)數(shù)。2.CZT公式推導(dǎo)22.CZT公式推導(dǎo)33.用CZT求解DFT的流圖4.CZT變換各點(diǎn)的值5、圖形6、說明1（1）A為起始樣點(diǎn)位置6、說明2（2）zk是z平面一段螺線上的等分角上某一采樣點(diǎn)。6、說明36、說明46、說明57、CZT的實(shí)現(xiàn)步驟17、CZT的實(shí)現(xiàn)步驟27、CZT的實(shí)現(xiàn)步驟37、CZT的實(shí)現(xiàn)步驟47、CZT的實(shí)現(xiàn)步驟57、CZT的實(shí)現(xiàn)步驟67、CZT的實(shí)現(xiàn)步驟78、CZT變換運(yùn)算流程圖9、CZT運(yùn)算量的估算19、CZT運(yùn)算量的估算210、CZT運(yùn)算量與直接運(yùn)算量比較當(dāng)M、N足夠小時(shí)，直接算法運(yùn)算量少。但M、N值比較大時(shí)（大于50），CZT算法比直接算法的運(yùn)算量少得多。例M=50，N=50，N*M=2500次而CZT<1600次。11、CZT算法的特點(diǎn)與標(biāo)準(zhǔn)FFT算法相比，CZT算法有以下特點(diǎn)：（1）輸入序列長(zhǎng)N及輸出序列長(zhǎng)M不需要相等。（2）N及M不必是高度合成數(shù)，二者均可為素?cái)?shù)。（3）Zk的角間隔是任意的，其頻率分辨率也是任意的。（4）周線不必是z平面上的圓，在語(yǔ)音分析中螺旋周線具有某些優(yōu)點(diǎn)。（5）起始點(diǎn)z0可任意選定，因此可以從任意頻率上開始對(duì)輸入數(shù)據(jù)進(jìn)行窄帶高分辨率的分析。（6）若A=1,M=N,可用CZT來(lái)計(jì)算DFT，即使N為素?cái)?shù)時(shí)，也可以。總之，CZT算法具有很大的靈活性，在某種意義上說，它是一個(gè)一般化的DFT。12、CZT變換的應(yīng)用1（1）利用CZT變換計(jì)算DFT。12、CZT變換的應(yīng)用2（2）對(duì)信號(hào)的頻譜進(jìn)行細(xì)化分析。其中對(duì)窄帶信號(hào)頻譜或?qū)Σ糠指信d趣的頻譜進(jìn)行細(xì)化分析。這樣CZT只對(duì)感興趣的頻率區(qū)段進(jìn)行采樣。計(jì)算量小很多，有利于實(shí)時(shí)處理。或在保證實(shí)時(shí)處理的情況下，可大提高頻率分辨率。12、CZT變換的應(yīng)用3（3）求解z變換X(z)的零、極點(diǎn)。用于語(yǔ)音信號(hào)處理過程中。具體方法：利用不同半徑同心圓，進(jìn)行等間隔的采樣。作業(yè)第七節(jié)FFT的應(yīng)用凡是利用付里葉變換來(lái)進(jìn)行分析、綜合、變換…的地方，都可以利用FFT算法來(lái)減少其計(jì)算量。FFT主要應(yīng)用在（1）快速卷積（2）快速相關(guān)（3）頻譜分析一、快速卷積設(shè)x(n)的長(zhǎng)度為N點(diǎn)，h(n)的長(zhǎng)度為M點(diǎn)，則：y(n)的長(zhǎng)度為N+M-1點(diǎn)。所以直接計(jì)算y(n)線性卷積運(yùn)算量為NM。1.利用圓周卷積代替線卷積用圓周卷積（FFT）代替線卷積的必要條件：x(n)、h(n)補(bǔ)零加長(zhǎng)至L=N+M-1.然后計(jì)算圓卷積。求出y(n)代表線卷積。2、用FFT計(jì)算y(n)的步驟(1)求H(k)=DFT[h(n)](L點(diǎn)）(2)求X(k)=DFT[x(n)](L點(diǎn)）(3)計(jì)算Y(k)=X(k)H(k)(L點(diǎn)）(4)求y(n)=IDFT[Y(k)](L點(diǎn)）2、用FFT計(jì)算y(n)與直接計(jì)算y(n)的運(yùn)算量比較3、分段卷積的方法（1）重疊相加法（2）重疊保留法設(shè)x(n)的長(zhǎng)度為長(zhǎng)序列N，h(n)為短序列列M。（1）重疊相加法1（1）x(n)為分段，每段長(zhǎng)為p點(diǎn)，p選擇與M數(shù)量組相同。用xi(n)表示x(n)的第i段.（1）重疊相加法2（1）重疊相加法例子（2）重疊保留法1（2）重疊保留法2（2）重疊保留法例子二、快速相關(guān)

1.方法2.步驟三、頻譜分析這里我們僅介紹FFT的儀器設(shè)備：快速付里葉分析儀。其功能為：（1）能分析確定性信號(hào)的頻譜。（2）估計(jì)隨機(jī)信號(hào)的功率譜（3）并對(duì)信號(hào)進(jìn)行快速卷積濾波（4）計(jì)算相關(guān)函數(shù)1.頻譜分析儀