3快速付里葉變換FFT2

1、第四節(jié)基-2按頻率抽取的FFT算法Decimation-in-Frequency(DIF)(Sander-Tukey)1一、算法原理設輸入序列長度為N=2M(M為正整數(shù)，將該序列的頻域的輸出序列X(k)(也是M點序列，按其頻域順序的奇偶分解為越來越短的子序列，稱為基2按頻率抽取的FFT算法。也稱為Sander-Tukey算法。2二、算法步驟1.分組DFT變換：已證明頻域上X(k)按k的奇偶分為兩組，在時域上x(n)按n的順序分前后兩部分，現(xiàn)將輸入x(n)按n的順序分前后兩部分:前半子序列x(n),0nN/2-1;后半子序列x(n+N/2),0nN/2-1;例：N=8時，前半序列為：x(0),x

2、(1),x(2),x(3); 后半序列為： x(4),x(5),x(6),x(7); 則由定義輸出（求DFT）32.代入DFT中43. 變量置換-153. 變量置換-263. 變量置換-373. 變量置換-484.結論1一個N點的DFT被分解為兩個N/2點DFT。X1(k),X2(k)這兩個N/2點的DFT按照：可見：如此分解，直至分到2點的DFT為止。94.結論210三、蝶形流圖表示蝶形單元：時域中，前后半部表示式用蝶形結表示。x(n)x(n+N/2)與時間抽取法的推演過程一樣，由于N=2L,N/2仍為偶數(shù)，所以可以將N/2點DFT的輸出X(k)再分為偶數(shù)組和奇數(shù)組，這樣就將一個N/2點的D

3、FT分成兩個N/4點DFT的輸入，也是將N/2點的DFT的輸入上、下對半分后通過蝶形運算而形成，直至最后為2點DFT。11例子：求 N=23=8點DIF （1）先按N=8-N/2=4，做4點的DIF：先將N=8DFT分解成2個4點DFT：可知：時域上：x(0),x(1),x(2),x(3)為偶子序列 x(4),x(5),x(6),x(7)為奇子序列 頻域上：X(0),X(2),X(4),X(6)由x1(n)給出 X(1),X(3),X(5),X(7),由x2(n)給出12將N=8點分解成2個4點的DIF的信號流圖 4點DFTx(0)x(1)x(2)x(3)4點DFTx(4)x(5)x(6)x(

4、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)13(2)N/2(4點)-N/4(2點)FFT(a)先將4點分解成2點的DIF：因為4點DIF還是比較麻煩，所以再繼續(xù)分解。14（b)一個2點的DIF蝶形流圖2點DFT2點DFTx1(0)x1(1)x1(2)x1(3)x3(0)x3(1)x4(0)x4(1)X(0)X(4)X(2)X(6)15(c)另一個2點的DIF蝶形流圖2點DFT2點DFTx2(0)x2(1)x2(2)x2(3)x5(0)x5(1)x6(0)x6(1)X(1)X(5)X(3)X(7)16(3)

5、將N/4（2點）DFT再分解成2個1點的DFT(a)求2個一點的DFT 最后剩下兩點DFT,它可分解成兩個一點DFT，但一點DFT就等于輸入信號本身，所以兩點DFT可用一個蝶形結表示。取x3(0)、x3(1)為例。17(b)2個1點的DFT蝶形流圖 1點DFTx3(0)1點DFTx3(1)X(0)X(4)進一步簡化為蝶形流圖：X(0)X(4)x3(0)x3(1)18(4)一個完整N=8的按頻率抽取FFT的運算流圖 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=219(5)DIF的特點(a)輸入自然

6、順序，輸出亂序且滿足碼位倒置規(guī)則。(b)根據(jù)時域、頻域互換，可知：輸入亂序，輸出自然順序。20（6）DIF與DIT比較1相同之處：（1）DIF與DIT兩種算法均為原位運算。（2）DIF與DIT運算量相同。它們都需要21（6）DIF與DIT比較2不同之處：（1）DIF與DIT兩種算法結構倒過來。DIF為輸入順序，輸出亂序。運算完畢再運行“二進制倒讀”程序。DIT為輸入亂序，輸出順序。先運行“二進制倒讀”程序，再進行求DFT。（2）DIF與DIT根本區(qū)別：在于蝶形結不同。DIT的復數(shù)相乘出現(xiàn)在減法之前。DIF的復數(shù)相乘出現(xiàn)在減法之后。22作業(yè)試畫出N=16點的基-2按頻率抽取的FFT流圖（DIF）

7、。23第五節(jié)IFFT運算方法以上所討論的FFT的運算方法同樣可用于IDFT的運算，簡稱為IFFT。即快速付里葉反變換。從IDFT的定義出發(fā)，可以導出下列二種利用FFT來計算FFT的方法。24一、利用FFT計算IFFT的思路1將下列兩式進行比較25二、利用FFT計算IFFT的思路2利用FFT計算IFFT時在命名上應注意：(1)把FFT的時間抽取法，用于IDFT運算時，由于輸入變量由時間序列x(n)改成頻率序列X(k),原來按x(n)的奇、偶次序分組的時間抽取法FFT，現(xiàn)在就變成了按X(k)的奇偶次序抽取了。（2）同樣，頻率抽取的FFT運算用于IDFT運算時，也應改變?yōu)闀r間抽取的IFFT。26三、

8、改變FFT流圖系數(shù)的方法1.思路在IFFT的運算中，常常把1/N分解為(1/2)m，并且在M級運算中每一級運算都分別乘以1/2因子，就可得到IFFT的兩種基本蝶形運算結構。（并不常用此方法）272.IFFT的基本蝶形運算ABAB(a)頻率抽取IFFT的蝶形運算(b)時間抽取IFFT的蝶形運算28四.直接利用FFT流圖的方法1.思路前面的兩種IFFT算法，排程序很方便，但要改變FFT的程序和參數(shù)才能實現(xiàn)?，F(xiàn)介紹第三種IFFT算法，則可以完全不必改動FFT程序。292.直接利用FFT流圖方法的推導可知：只須將頻域成份一個求共軛變換，即（1）將X(k)的虛部乘以-1，即先取X(k)的共軛，得X*(k

9、)。(2)將X*(k)直接送入FFT程序即可得出Nx*(n)。(3)最后再對運算結果取一次共軛變換，并乘以常數(shù)1/N，即可以求出IFFT變換的x(n)的值。此為DFT可用FFT程序303.直接利用FFT流圖方法的注意點（1）FFT與IFFT連接應用時，注意輸入輸出序列的排列順序，即應注意是自然順序還是倒序。（2）FFT和IFFT共用同一個程序時，也應注意利用FFT算法輸入輸出的排列順序，即應注意自然順序還是例位序（3）當把頻率抽取FFT流圖用于IDFT時，應改稱時間抽取IFFT流圖。（4）當把時間抽取FFT流圖用于IDFT時，應改稱頻率抽取IFFT流圖。31作業(yè)用C語言完成N=128點的DIT

10、，DIF及IDIT，IDIF。32第六節(jié)線性調(diào)頻Z變換33一、引入以上提出FFT算法，可以很快地求出全部DFT值。即求出有限長序列x(n)的z變換X(z)在單位園上N個等間隔抽樣點zk處的抽樣值。它要求N為高度復合數(shù)。即N可以分解成一些因子的乘積。例N=2L實際上：（1）也許對其它圍線上z變換取樣發(fā)生興趣。如語音處理中，常常需要知道某一圍線z變換的極點所處的復頻率。（2）只需要計算單位圓上某一段的頻譜。如窄帶信號，希望在窄帶頻率內(nèi)頻率抽樣能夠非常密集，提高分辨率，帶外則不考慮。（3）若N是大素數(shù)時，不能加以分解，又如何有效計算這種序列DFT。例N=311，若用基2則須補N=28=512點，要補

11、211個零點。34二、問題提出由上面三個問題提出：為了提高DFT的靈活性，須用新的方法。線性調(diào)頻z變換(CZT)就是適用這種更為一般情況下，由x(n)求X(zk)的快速變換CZT：來自于雷達專業(yè)的專用詞匯。35三、算法原理1.定義Z 變 換 采 用 螺 線 抽 樣, 可 適 用 于 更 一 般 情 況 下 由 x(n) 求X(zk) 的 快 速 算 法, 這 種 變 換 稱 為 線 性 調(diào) 頻 Z 變 換 ( 簡 稱 CZT ).362.CZT公式推導1 已 知 x(n) ，0nN-1,則它的z變換是： 為適應z可以沿平面內(nèi)更一般的路徑取值，故：沿z平面上的一段螺線作等分角的抽樣，則z的取樣點

12、Zk可表示為：其中M：表示欲分析的復頻譜的點數(shù)。M不一定等于N。A， 都為任意復數(shù)。 372.CZT公式推導2382.CZT公式推導3393.用CZT求解DFT的流圖404.CZT變換各點的值415、圖形426、說明1（1）A為起始樣點位置436、說明2（2）zk是z平面一段螺線上的等分角上某一采樣點。446、說明3456、說明4466、說明5477、CZT的實現(xiàn)步驟1487、CZT的實現(xiàn)步驟2497、CZT的實現(xiàn)步驟3507、CZT的實現(xiàn)步驟4517、CZT的實現(xiàn)步驟5527、CZT的實現(xiàn)步驟6537、CZT的實現(xiàn)步驟7548、CZT變換運算流程圖559、CZT運算量的估算1569、CZT運

13、算量的估算25710、CZT運算量與直接運算量比較當M、N足夠小時，直接算法運算量少。但M、N值比較大時（大于50），CZT算法比直接算法的運算量少得多。例M=50，N=50，N*M=2500次而CZT1600次。5811、CZT算法的特點與標準FFT算法相比，CZT算法有以下特點：（1）輸入序列長N及輸出序列長M不需要相等。（2）N及M不必是高度合成數(shù)，二者均可為素數(shù)。（3）Zk的角間隔 是任意的，其頻率分辨率也是任意的。（4）周線不必是z平面上的圓，在語音分析中螺旋周線具有某些優(yōu)點。（5）起始點z0可任意選定，因此可以從任意頻率上開始對輸入數(shù)據(jù)進行窄帶高分辨率的分析。（6）若A=1,M=N

14、,可用CZT來計算DFT，即使N為素數(shù)時，也可以?？傊?，CZT算法具有很大的靈活性，在某種意義上說，它是一個一般化的DFT。5912、CZT變換的應用1（1）利用CZT變換計算DFT。6012、CZT變換的應用2（2）對信號的頻譜進行細化分析。其中對窄帶信號頻譜或?qū)Σ糠指信d趣的頻譜進行細化分析。這樣CZT只對感興趣的頻率區(qū)段進行采樣。計算量小很多，有利于實時處理。或在保證實時處理的情況下，可大提高頻率分辨率。6112、CZT變換的應用3（3）求解z變換X(z)的零、極點。用于語音信號處理過程中。具體方法：利用不同半徑同心圓，進行等間隔的采樣。62作業(yè)63第七節(jié)FFT的應用凡是利用付里葉變換來進

15、行分析、綜合、變換的地方，都可以利用FFT算法來減少其計算量。FFT主要應用在（1）快速卷積（2）快速相關（3）頻譜分析64一、快速卷積設x(n)的長度為N點，h(n)的長度為M點，則：y(n)的長度為N+M-1點。所以直接計算y(n)線性卷積運算量為NM。651.利用圓周卷積代替線卷積用圓周卷積（FFT）代替線卷積的必要條件：x(n)、h(n)補零加長至L=N+M-1.然后計算圓卷積。求出y(n)代表線卷積。662、用FFT計算y(n)的步驟(1)求H(k)=DFTh(n) (L點） (2)求X(k)=DFTx(n) (L點）(3)計算Y(k)=X(k)H(k) (L點）(4)求y(n)=IDFTY(k) (L點）672、用FFT計算y(n)與直接計算y(n)的運算量比較683、分段卷積的方法（1）重疊相加法（2）重疊保留法設x(n)的長度為長序列N，h(n)為短序列列M。69（1）重疊相加法1（1）x(n)為分段，每段長為p點，p選擇與M數(shù)量組相同。用xi(n)表示x(n)的第i段.70（1）重疊相加法271（1）重疊相加法例子72（2）重疊保留法173（2）重疊保留法274（2）重疊保留法例子75二、快速相關1.方法762.步驟77三、頻譜分析這里我們僅介紹FFT的儀器設備：快速付里葉分析儀。其功能為：（1）能分析確定性信號的頻譜。（2）估計