【正文】 ( ) ( ) ( ) ( ) ( )my n x n h n x m h n m??? ? ? ?? X(k)=FFT[x(n)] b. 求 H(k)=FFT[h(n)] c. 求 Y(k)=H(k)X(k) k=0～ L1 d. 求 y(n)=IFFT[Y(k)] n=0～ L1 可見，只要進行二次 FFT,一次 IFFT就可完成 線性卷積計算。計算表明 , L32時 , 上述計算線 性卷積的方法比直接計算線卷積有明顯的優(yōu)越性。 因此 ,也稱圓周卷積的方法為 快速卷積法 。 上述方法適用于 x(n)、 h(n)兩序列長度比較接近或相等的情況。如果 x(n)、 h(n)長度相差較多 ,例如： h(n)為某濾波器的單位脈沖響應(yīng) ,長度有限 ,用來處理一個很長很長的輸入信號 x(n),按上述方法 ,h(n)要補許多零值后再進行計算 ,這降低了運算速度，發(fā)揮不出圓周卷積的優(yōu)點。 為了保持快速卷積法的優(yōu)越性 ,可將 x(n)分為許多段 ,每段的長度與 h(n)接近 , 處理方法有兩種： (1)重疊相加法 (2)重疊保留法 (1)重疊相加法 —— 由分段卷積的各段相加構(gòu) 成總的卷積輸出 h(n) x(n) 序列長度為 1N序列長度為 2N 假定 表示 x(n)序列的第 i段 ： 則輸入序列可表為： 于是輸出可分解為： 其中 ??? ?????01)1()()( 22 NiniNnxnxi??????ii nxnx )()(? ????????????i iii nynhnxnhnxny )()(*)()(*)()()(*)()( nhnxny ii ?()ixn 。 ??????ii nyny )()(重疊相加法計算步驟： a. 先對 h(n)及 補零，補到具有 N點長度， N=N1+N21， 并且滿足 N=2M 。 b. 用 N點 FFT計算 c. 用 N點 FFT計算 ()ixn( ) [ ( ) ]iiDFTX k nx?( ) ( ) ( )iiy n x n h n?? 由于 的長度為 N， 而 的長度為 N2， 因此相鄰兩段序列 必然有 NN2=N11 點發(fā)生重疊 ，最后的輸出應(yīng)該是這些重疊部分相加起來 ， 再和不重疊部分共同組成輸出序列 。 重疊相加法對處理一個無限長的語音信號或地震信號都是十分有效的 。 ()iyn()ixn()iyn()yn有 N11個點發(fā)生重疊 (2)重疊保留法 這種方法和第一種方法稍有不同 ， 即將上面分段序列中補零的部分不是補零 ， 而是保留原來的輸入序列值 ， 如果利用 FFT實現(xiàn) h(n)和 xi(n)的圓周卷積 ， 則每段卷積結(jié)果中有 N11個點不等于線性卷積值需舍去 。 重疊保留法與重疊相加法的計算量差不多 ，但省去了重疊相加法最后的相加運算 。 h(n) x(n) 序列長度為 1N序列長度為 2N(1)重疊相加法 (2)重疊保留法 保留 點的輸入序列值 211N N N? ? ??FFT應(yīng)用中的幾個問題 實數(shù)序列的 FFT 以上討論的 FFT算法都是復(fù)數(shù)運算 ,包括序列 x(n)也認為是復(fù)數(shù) ,但大多數(shù)場合 ,信號是實數(shù)序列 ,任何實數(shù)都可看成虛部為零的復(fù)數(shù) 。 例如 ,求某實信號 x(n)的復(fù)譜 ,可認為是實信號加上數(shù)值為零的虛部組成復(fù)信號 (x(n)+j0),再用 FFT求其離散傅里葉變換 。 這種作法很不經(jīng)濟 ,因為把實序列變成復(fù)序列 ,存儲器要增加一倍 ,且計算機運行時 ,即使虛部為零 ,也要進行涉及虛部的運算 ,造成運算速度下降 。 合理的解決方法是利用復(fù)數(shù)據(jù) FFT對實數(shù)據(jù)進行有效計算 ,下面介紹兩種方法 。 （ 1） 用一個 N點 FFT同時計算兩個 N點實序列的 DFT 設(shè) x(n)、 y(n)是彼此獨立的兩個 N點實序列 ,且 X(k)=DFT[x(n)]， Y(k)=DFT[y(n)] 則 X(k)、 Y(k)可通過一次 FFT運算同時獲得 。 首先將 x(n)、 y(n)分別當作一復(fù)序列的實部及 虛部 ,令： g(n)=x(n)+jy(n) 通過 FFT運算可獲得 g(n)的 DFT值 ? ? ? ? ? ?? ? ? ? ? ? ? ?r i r iG k X k j Y kX k j X k j Y k Y k??? ? ? ????? 利用離散傅里葉變換的共軛對稱性 通過 g(n)的 FFT運算結(jié)果 G(k),由上式可得到 X(k)的值 。 Y(k)的值也可以通過 g(n)的 FFT運算結(jié)果 G(k)得到 。 ? ? ? ? ? ? ? ? ? ?? ? ? ?r i i rriG k X k Y k j X k j Y kG k j G k? ? ? ???????? ?? ?? ? ? ?? ? ? ?? ?? ? ? ?? ? ? ? ? ?? ?kNGkGjkNGkGkNGkGkXngiirr ??????????212121ReD F T*? ?? ? ? ?? ? ? ?? ? ? ? ? ? ? ?*D F T I m121122r r i ij g n j Y kG k G N kG k G N k j G k G N k?? ?????? ? ???? ? ? ? ? ?? ? ? ?? ? ? ?? ? ? ? ? ?? ? ? ? ? ?? ?kNGkGjkNGkGkY rrii ?????? 2121 作一次 Ｎ 點復(fù)序列的 FFT，再通過加、減法運算就可以將 X(k)與 Y(k)分離出來。顯然，這將使運算效率提高一倍。 （ 2） 用一個 N點的 FFT獲得一個 2N點實序列的 DFT 設(shè) x(n)是 2N點的實序列 ,現(xiàn)人為地將 x(n)分為偶數(shù)組 x1(n)和奇數(shù)組 x2(n) x1(n)=x(2n) n=0,1,… ,N1 x2(n)=x(2n+1) n=0,1,… ,N1 然后將 x1(n)及 x2(n)組成一個復(fù)序列： y(n)=x1(n)+jx2(n) 通過 N點 FFT運算可得到： Y(k)=X1(k)+jX2(k) ??????????????)]()([2)()]()([21)(*2*1kNYkYjkXkNYkYkX 為求 2N點 x(n)所對應(yīng) X(k)， 需求出 X(k)與 X1(k)、 X2(k)的關(guān)系 ： ??? ???????????10)12(21022120)12()2()()(NnknNNnnkNNnnk WnxWnxWnxkX?????????10210)12()2(NnnkNkNNnnkN WnxWWnx ??????????????)]()([2)()]()([21)(*2*1kNYkYjkXkNYkYkX所以 1）由 x1(n)及 x2(n)組成復(fù)序列，經(jīng) FFT運算求得 Y(k)。 2）利用共軛對稱性求出 X1(k)、 X2(k)。 3）最后利用上式求出 X(k), 達到用一個 N點的 FFT 計算一個 2N點的實序列的 DFT的目的。 X(k)=X1(k)+W2Nk X2(k) ??????????????? ?????????1011022101011)12()()()2()()(NnnkNNnnkNNnNnnkNnkNWnxWnxkXWnxWnxkX