數(shù)字信號處理：第三章 離散付里葉變換及其快速算法(重點)

1、第三章 離散付里葉變換及其快速算法(重點)3.1 離散付里葉變換(DFT)3.2 利用DFT 進行頻譜分析 3.3 快速付里葉變換 (FFT)3.4 FFT 應用中的幾個問題 前面我們討論用付里葉變換和z變換來描述一般的序列和線性時不變離散系統(tǒng)。但有時序列是有限長序列，如FIR系統(tǒng)的單位脈沖響應就是一個有限長序列。對于這種情況，正如本章要討論的，可以導出另一種付里葉表示式，稱作離散付里葉變換(DFT)。 離散付里葉變換是有限長序列付里葉表示式，它本身也是一個序列，而不是一個連續(xù)函數(shù)，它相當于把信號的付里葉變換進行等頻率間隔取樣。離散付里葉變換除了作為有限長序列的一種付里葉表示式在理論上相當重要

2、外，由于存在計算離散付里葉變換的有效算法(FFT)，因而其在實現(xiàn)各種數(shù)字信號處理算法時起著核心作用。 z變換 分析工具 付里葉變換（DTFT） 離散付里葉變換(DFT) 意義在頻域上實現(xiàn)數(shù)字處理有各種快速實現(xiàn)算法(FFT)一般序列有限長序列3.1 離散付里葉變換(DFT) 為了便于更好地理解DFT的概念，先討論周期序列及其離散付里葉級數(shù)(DFS)表示。3.1.1 離散付里葉級數(shù)(DFS)我們用 來表示一個周期為N的周期序列，即 ， k為任意整數(shù)，N為周期。 周期序列不能進行Z變換，因為其在 n= - 到 + 都周而復始永不衰減，在整個 z 平面上任何地方找不到一個衰減因子z能使序列絕對可和：

3、即 z 平面上沒有收斂域。但是，正象連續(xù)時間周期信號可用付氏級數(shù)表達，周期序列也可用離散的付氏級數(shù)來表示，也即用周期為N的正弦序列(或復指數(shù)序列)來表示。周期為N的正弦序列其基頻成分為： k次諧波序列為： 但離散級數(shù)所有諧波成分中只有N個是獨立的，這是與連續(xù)付氏級數(shù)的不同之處， 即 因此 將周期序列展成離散付里葉級數(shù)時，只需取 k=0 到(N-1) 這N個獨立的諧波分量，所以一個周期序列的離散付里葉級數(shù)只需包含這N個復指數(shù)， (1) 利用正弦序列的周期性可求解系數(shù) 。方法：將(1)式兩邊乘以 ，并對一個周期求和 上式中 部分顯然只有當k=r時才有值為1,其他任意k值時均為零,所以有 或寫為 1

4、) 可求 N 次諧波的系數(shù)。 2) 也是一個由 N 個獨立諧波分量組成的傅立葉級數(shù)。 3) 為周期序列，周期為N。周期序列的離散付里葉級數(shù)在頻域上仍是一個周期序列。 是一個周期序列的離散付里葉級數(shù)(DFS)變換對，這種對稱關系可表為： 習慣上：記 ， DFS變換對公式表明，一個周期序列雖然是無窮長序列，但是只要知道它一個周期的內容(一個周期內信號的變化情況)，就可以表示這個序列，所以這種無窮長序列實際上只有N個序列值是有用的，因此周期序列與有限長序列有著本質的聯(lián)系。則DFS變換對可寫為DFS 離散付里葉級數(shù)變換IDFS離散付里葉級數(shù)反變換。 DFS的幾個主要特性： 假設 都是周期為 N 的兩個

5、周期序列，各自的離散付里葉級數(shù)變換為： 1)線性性 a,b為任意常數(shù) 2)序列移位 證： 因為 及 都是以 N 為周期的函數(shù)，所以有 由于 與 對稱性，同樣可證明3)周期卷積若 則 或 證： 這是一個卷積公式，但與前面討論的線性卷積的差別在于，這里的卷積過程只限于一個周期內(即 m=0N-1)，稱為周期卷積。例： 、 ，周期為 N=7, 寬度分別為 4 和 3 ， 求周期卷積。 結論：卷積結果仍為周期序列，周期為 N 。周 期 卷 積 由于DFS與IDFS的對稱性，對周期序列乘積，存在著頻域的周期卷積公式，若 則 3.1.2 離散付里葉變換(DFT) 從上節(jié)的討論，我們知道周期序列實際上只有有

6、限個序列值有意義，因此它的許多特性可推廣到有限長序列上。 一個有限長序列 x(n)，長為N， 為了引用周期序列的概念，假定一個周期序列 ，它由長度為 N 的有限長序列 x(n) 延拓而成，它們的關系為： 周期序列與有限長序列 的關系：周期序列的主值區(qū)間與主值序列： 對于周期序列 ，定義其第一個周期 n=0N-1，為 的“主值區(qū)間”，主值區(qū)間上的序列為主值序列 。x(n)與 的關系可描述為： 數(shù)學表示： RN(n) 為矩形序列。符號 (n)N 是余數(shù)運算表達式，表示 n 對 N 求余數(shù)。例： 是周期為 N=7 的序列，求 n=11 和 n=-2 對 N的余數(shù)。因此 頻域上的主值區(qū)間與主值序列：

7、周期序列 的離散付氏級數(shù) 也是一個周期序列，也可給它定義一個主值區(qū)間 ，以及主值序列 X(k)。數(shù)學表示： 再看周期序列的離散付里葉級數(shù)變換(DFS)公式： 這兩個公式的求和都只限于主值區(qū)間(0N-1)，它們完全適用于主值序列 x(n) 與 X(k) ，因而我們可得到一個新的定義有限長序列離散付里葉變換定義。 長度為N的有限長序列 x(n) ，其離散付里葉變換 X(k) 仍是一個長度為N 的有限長序列，它們的關系為： x(n) 與 X(k) 是一個有限長序列離散付里葉變換對，已知 x(n) 就能唯一地確定 X(k) ，同樣已知 X(k) 也就唯一地確定 x(n) ，實際上 x(n) 與 X(k

8、) 都是長度為 N 的序列(復序列)，都有N個獨立值，因而具有等量的信息。有限長序列隱含著周期性。例： 是一個 N=12 的有限長序列，由DFT得：DFT特性： 以下討論DFT的一些主要特性，這些特性都與周期序列的DFS有關。 假定x(n)與y(n)是長度為N的有限長序列，其各自的離散付里葉變換分別為： X(k)=DFTx(n) Y(k)=DFTy(n) (1) 線性 DFTax(n)+by(n)=aX(k)+bY(k) ,a,b為任意常數(shù)(2) 圓周移位 有限長序列x(n)的圓周移位定義為： f(n)=x(n+m)NRN(n)含義：1) x(n+m)N 表示 x(n) 的周期延拓序列 的移位

9、： 2) x(n+m)NRN(n) 表示對移位的周期序列 x(n+m)N 取主值序列, 所以 f(n) 仍然是一個長度為N的有限長序列。 f(n)實際上可看作序列 x(n)排列在一個N等分圓周上，并順時針旋轉 m 位。 圓周移位周期延拓，左移2位取主值圓周移位移位前左移兩位后證：利用周期序列的移位特性： 實際上，利用 的周期性，將 f(n)=x(n+m)NRN(n) 代入DFT定義式，同樣很容易證明。 序列圓周移位后的DFT為 F(k) =DFT f(n) = 同樣，對于頻域有限長序列X(k)的圓周移位，有如下反變換特性： IDFTX(k+l)NRN(k)= x(n)頻域的圓周移位等效于時域序

10、列的調制。(3)圓周卷積若 F(k)=X(k)Y(k)則 或 證：這個卷積可看作是周期序列 卷積后再取其主值序列。將 F(k) 周期延拓，得： 則根據(jù)DFS的周期卷積公式：因0mN-1時，x(m)N=x(m)，因此經(jīng)過簡單的換元可證明：這一卷積過程與周期卷積比較，過程是一樣的，只是這里只取結果的主值序列，由于卷積過程只在主值區(qū)間0mN-1內進行，所以 實際上就是 y(m)的圓周移位，稱為“圓周卷積”，習慣上常用符號“ ”表示圓周卷積，以區(qū)別于線性卷積。圓周卷積也稱為循環(huán)卷積?？梢宰C明： 1）由有限長序列 x(n)、y(n) 構造周期序列循環(huán)卷積過程:2）計算周期卷積 3）卷積 結果取主值圓周卷

11、積計算：在一個周期內對應點相乘相加同樣，若 f(n)=x(n)y(n)，則(4)有限長序列的線性卷積與圓周卷積(圓周卷積的應用) 實際問題的大多數(shù)是求解線性卷積，如信號 x(n) 通過系統(tǒng) h(n) ，其輸出就是線性卷積 y(n)=x(n)*h(n) 。而圓周卷積比起線性卷積，在運算速度上有很大的優(yōu)越性，它可以采用快速付里葉變換(FFT)技術，若能利用圓周卷積求線性卷積，會帶來很大的方便。 現(xiàn)在我們來討論上述 x(n) 與 h(n) 的線性卷積，如果 x(n)、h(n) 為有限長序列，則在什么條件下能用圓周卷積代替線性卷積而不產(chǎn)生失真? 有限長序列的線性卷積：假定 x(n) 為有限長序列，長度

12、為N， y(n) 為有限長序列，長度為M，它們的線性卷積 f(n) =x(n)*y(n) 也應是有限長序列。因 x(m) 的非零區(qū)間： 0mN-1， y(n-m) 的非零區(qū)間： 0n-mM-1， 這兩個不等式相加，得： 0nN+M-2， 在這區(qū)間以外或 x(m)=0，或 y(n-m)=0，因而f(n)=0。因此，f(n) 是一個長度為N+M-1的有限長序列。圓周卷積： 重新構造兩個有限長序列 x(n)、y(n)，長度均為 L maxN,M ，序列 x(n) 只有前 N 個是非零值，后 L-N 個為補充的零值；序列 y(n) 只有前 M 個是非零值，后L-M個為補充的零值。為了分析 x(n) 與

13、 y(n) 的圓周卷積，先討論其周期卷積。 將 x(n)，y(n) 周期延拓： 其中 f(n) 就是線性卷積，也就是說， 的周期卷積，是 x(n)、y(n) 線性卷積的周期延拓，周期為L。它們的周期卷積序列為： 根據(jù)前面的分析，f(n)具有 N+M-1 個非零序列值，因此，如果周期卷積的周期 Lp+q，所以組合數(shù)的FFT計算效率要高于直接計算法。 上述分解原則可推廣至任意基數(shù)的更加復雜的情況。例如, 如果N可分解為m個質數(shù)因子p1,p2,，pm，即 N=p1p2p3pm則第一步：可把N先分解為兩個因子N=p1q1，其中q1=p2p3pm ，并用上述討論的方法將DFT分解為p1個q1點DFT；第

14、二步：將q1分解為q1=p2q2，q2=p3p4pm，然后將每個q1 點DFT再分解為p2個q2點DFT；： 依此類推，：通過m次分解，一直分到最少點數(shù)的DFT運算，從而獲得最高的運算效率。其運算量近似為N(p1+p2+pm)次復數(shù)乘法和復數(shù)加法。但計算效率的提高是要以編程的復雜性為代價的，一般較少應用。 p1=p2 = =pm =2，為基2 FFT 算法。6、Chirp-z變換 采用FFT算法可以很快算出全部N點DFT值，即z變換X(z)在z平面單位圓上的全部等間隔取樣值，但要求 N 為復合數(shù)。問題的提出： 不需要計算整個單位圓上z變換的取樣，如對于窄帶信號，只需要對信號所在的一段頻帶進行分

15、析，這時,希望頻譜的采樣集中在這一頻帶內，以獲得較高的分辨率，而頻帶以外的部分可不考慮。 對其它圍線上的z變換取樣感興趣，例如語音信號處理中，需要知道z變換的極點所在頻率，如極點位置離單位圓較遠，則其單位圓上的頻譜就很平滑，這時很難從中識別出極點所在的頻率，如果采樣不是沿單位圓而是沿一條接近這些極點的弧線進行，則在極點所在頻率上的將出現(xiàn)明顯的尖峰，由此可較準確地測定極點頻率。 要求能有效地計算當N是素數(shù)時序列的DFT，因此提高DFT計算的靈活性非常有意義。 螺旋線采樣是一種適合于這種需要的變換，且可以采用FFT來快速計算，這種變換也稱作Chirp-z變換。算法原理：已知x(n)，0nN-1令z

16、的取樣點為 ，k=0，M-1 ，M ：采樣點數(shù)，A、W：任意復數(shù)，其中：A0表示起始取樣點的半徑長度，通常A01；0表示起始取樣點z0的相角；0表兩相鄰點之間的等分角；W0螺旋線的伸展率，W01則螺線內縮(反時針)；W0=1 表示半徑為A0的一段圓??；A0=1 這段圓弧是單位圓的一部分。圖 螺旋線采樣計算z變換在采樣點 zk 的值 k=0,1, ,M-1顯然，同直接計算DFT情況相仿，按照以上公式計算出全部M點采樣值需要 NM 次復乘和(N-1)M次復加，當N及M較大時，計算量迅速增加，但通過一定的變換，以上運算可轉換為卷積形式，從而可采用FFT進行，這樣可大大提高計算速度。利用zk的表示式代

17、入 nk可以用以下表示式來替換則定義：則 上式說明，如對信號x(n)先進行一次加權處理，加權系數(shù)為 ，然后通過一個單位脈沖響應為h(n)的線性系統(tǒng)，最后，對該系統(tǒng)的前M點輸出再作一次 的加權，就可得到全部M點螺旋線采樣值。 系統(tǒng)的單位脈沖響應 與頻率隨時間成線性增加的線性調頻信號相似，因此這種算法稱為Chirp-z變換。 xxx(n)g(n)X(zk)算法實現(xiàn)： 由于輸入信號 g(n)是有限長的，長為N，但序列 是無限長的，而計算 0M-1 點卷積 g(n)*h(n) 所需要的 h(n)是取值在n=-(N-1)M-1那一部分的值，因此，可認為h(n)是一個有限長序列，長為L=N+M-1。 所以

18、，Chirp-z變換為兩個有限長序列的線性卷積 g(n)*h(n)，可用圓圈卷積通過FFT來實現(xiàn)。 h(n)的主值序列 可由h(n)作周期延拓后取0nL-1部分值獲得，將 與 g(n)作圓周卷積后，其輸出的前M個值就是Chirp -z變換的M個值。這個圓周卷積的過程可在頻域上通過FFT實現(xiàn)。 Chirp-z變換的計算步驟： (1) 求h(n)的主值序列 (2)用FFT求 的付里葉變換: H(k)=FFT , L點 (3)對x(n)加權并補零(4) G(k)=FFT g(n) , L點(5) Y(k)=G(k)H(k) , L點(6) y(n)=IFFTY(k) , L點(7) , 0kM-1

19、計算量估算： 乘法數(shù)估計 (1)(2)兩步可以事先計算，不必實時計算。 (3)(7)兩步兩次加權共計N+M次復乘，形成Y(k)需L次復乘，一個FFT與一個IFFT需Llog2L次乘，所以 總乘法數(shù)：L+N+M+Llog2L。 直接計算乘法數(shù)：NM 可見，N及M較大時，用FFT實現(xiàn)Chirp-Z變換，速度上有很大的改進。Chirp-z變換的特點：1) 輸入序列的長度N 與 輸出序列的長度 M 不需要相等；2) N 及 M 不必是高度復合數(shù)，二者均可為素數(shù)；3) 相鄰采樣點 zk 之間的角間隔 0 是任意的，即頻率分辨率是任意的；4) 圍線是任意的，不必是 Z 平面的單位圓；5) 起始點 z0 可

20、任意選定，即可從任意頻率上開始對輸入數(shù)據(jù)進行窄帶高分辨率分析；6) 若 A=1 , M=N , , 可用 Chirp-z變換計算DFT(即使 N 為素數(shù))。$3.3 FFT應用中的幾個問題1)實數(shù)序列的FFT 以上討論的FFT算法都是復數(shù)運算，包括序列x(n)也認為是復數(shù)，但大多數(shù)場合，信號是實數(shù)序列，任何實數(shù)都可看成虛部為零的復數(shù)，例如，求某實信號y(n)的復譜，可認為是將實信號加上數(shù)值為零的虛部變成復信號(x(n)+j0)，再用FFT求其離散付里葉變換。這種做法很不經(jīng)濟，因為把實序列變成復序列，存儲器要增加一倍，且計算機運算時，即使虛部為零，也要進行涉及虛部的運算，浪費了運算量。合理的解決

21、方法是利用復數(shù) FFT 對實數(shù)據(jù)進行有效計算，下面介紹兩種方法。 (1) 用 一個N點FFT同時計算兩個N點實序列的DFT 設 x1(n) 、 x2(n) 是彼此獨立的兩個N點實序列，且 X1(k)=DFTx1(n) ， X2(k)=DFTx2(n) 則 X1(k)、X2(k) 可通過一次FFT運算同時獲得。算法如下： 首先將x1(n)、x2(n)分別當作一復序列的實部及虛部,令 x(n)=x1(n)+jx2(n)通過FFT運算可獲得 x(n) 的DFT值 X(k)=DFTx1(n)+jDFTx2(n) =X1(k)+jX2(k)利用離散付里葉變換的共軛對稱性，有:有了x(n)的FFT運算結果

22、X(k)，由上式可得到X1(k)、X2(k)的值。(2) 用一個N點的FFT運算獲得一個2N點實序列的DFT 設x(n)是2N點的實序列，現(xiàn)人為地將x(n)分為偶數(shù)組x1(n)和奇數(shù)組x2(n) x1(n) =x(2n) n=0,1,N-1 x2(n) =x(2n+1) n=0,1,N-1然后將x1(n)及x2(n)組成一個復序列： y(n)=x1(n)+jx2(n)通過N點FFT運算可得到： Y(k)=X1(k)+jX2(k) ，N點根據(jù)前面的討論，得到 為求 2N 點 x(n)所對應 X(k)，需求出 X(k)與 X1(k)、X2(k)的關系 ： 0kN-1 而 所以 , 0kN-1 計算

23、步驟：1) 由x1(n)及x2(n)組成復序列，經(jīng)FFT運算求得 Y(k)( N點FFT)；2) 利用共軛對稱性求出 X1(k)、X2(k)；3) 最后利用上式求出 X(k)；4) X(k)， k=N2N-1，由實序列頻譜的對稱性 X(k)= X*(2N-k) 得到。 相關的概念很重要，互相關運算廣泛應用于信號分析與統(tǒng)計分析，如通過相關函數(shù)峰值的檢測測量兩個信號的時延差；由自相關計算信號的能量，實現(xiàn)匹配濾波和信號能量檢測等。 2)用FFT計算相關函數(shù)相關用途分析功率譜作為二階矩，描述平穩(wěn)信號的統(tǒng)計特性構成相關檢測器線性相關兩個實有限長序列 x(n)與y(n)的互相關函數(shù)定義為：-20-1001

24、020-50050100150200250300m-20-1001020-50050100150200250300m幅度幅度 (a) (b) 圖2.23 (a)延遲序列的互相關函數(shù)和(b)自相關函數(shù)圓周相關定理 兩個長為N的實離散時間序列 x(n)與y(n)的互相關函數(shù)為 則可以證明，rxy(m)的離散付里葉變換為 其中 X(k)=DFTx(n), Y(k)=DFTy(n), Rxy(k)=DFTrxy(m) ， 0kN-1證：將x(n)、y(n)的逆離散付里葉變換代入互相關函數(shù)定義式 因x(n)是實序列，x(n)=x*(n)，得 因 得 證畢。 互相關函數(shù)與信號功率譜互為傅立葉變換對。 當x

25、(n)=y(n)時，得到x(n)的自相關函數(shù)為： 維納辛欽定理： 自相關函數(shù)與信號功率譜互為傅立葉變換對。 上面的推導表明，互相關和自相關函數(shù)的計算可利用 FFT實現(xiàn)。 由于離散付里葉變換隱含著周期性，所以用FFT計算離散相關函數(shù)也是對周期序列而言的。 利用圓周相關定理計算兩個有限長序列的線性相關時，為避免混淆，需采用與由圓周卷積求線性卷積相類似的方法。利用FFT求兩個有限長序列的線性相關： 設x(n)長為N1，y(n)長為N2，求線性相關: (1)將x(n)，y(n)補零至長為N，NN1+N2-1，且N=2m，以使兩個有限長序列的線性相關可用其圓周相關代替而不產(chǎn)生混淆。 即 (2) 用FFT

26、計算X(k)，Y(k)(k=0，1，N-1) (3) R(k)=X*(k)Y(k); (4) r(n)=Real IFFT( R(k) ) ; (n=0，1，N-1) x=1 3 -1 1 2 3 3 1;y=2 1 -1 1 2 0 -1 3;k=length(x);xk=fft(x,2*k);yk=fft(y,2*k);rm=real(ifft(conj(xk).*yk);rm=rm(k+2:2*k) rm(1:k);m=(-k+1):(k-1);stem(m,rm)xlabel(m); ylabel(幅度);-8-6-4-202468-6-4-2024681012m幅度兩個序列的相關函數(shù)

27、 3) 線性卷積的FFT算法 線性卷積是求離散系統(tǒng)響應的主要方法之一，許多重要應用都建立在這一理論基礎上，如卷積濾波等。 以前曾討論了用圓周卷積計算線性卷積的方法歸納如下: 將長為N2的序列x(n)延長到L，補L-N2個零， 將長為N1的序列h(n)延長到L，補L-N1個零， 如果LN1+N2-1，則圓周卷積與線性卷積相等，此時，可用FFT計算線性卷積，步驟如下:a. 計算X(k)=FFTx(n)b. 求H(k)=FFTh(n)c. 求Y(k)=H(k)X(k) k=0L-1d. 求y(n)=IFFTY(k) n=0L-1 可見，只要進行二次FFT，一次IFFT就可完成線性卷積計算。 計算表明

28、，L32時，上述計算線性卷積的方法比直接計算線卷積有明顯的優(yōu)越性，因此，也稱上述圓周卷積方法為快速卷積法。上述結論適用于 x(n)、h(n) 兩序列長度比較接近或相等的情況,如果x(n)、h(n) 長度相差較多,例如, h(n) 為某濾波器的單位脈沖響應,長度有限,用來處理一個很長的輸入信號 x(n)，或者處理一個連續(xù)不斷的信號，按上述方法,有三個問題： （1） h(n) 要補許多零再進行計算,計算量有很大的浪費，或者根本不能實現(xiàn)。 （2）系統(tǒng)的存儲量要求極高。 （3）帶來了很大的系統(tǒng)延遲。 為了克服上述三個問題，保持快速卷積法的優(yōu)越性,可將 x(n) 分為許多段,每段的長度與 h(n) 接近

29、 , 處理方法有兩種： 重疊相加法 重疊保存法(1) 重疊相加法由分段卷積的各段相加構成總的卷積輸出h(n) 假定 xi(n) 表示 x(n)序列的第i段 ： 則輸入序列可表為： 于是輸出可分解為： 其中 上兩式表明，只要將x(n)的每一段分別與h(n)卷積，然后再將這些卷積結果相加起來就可得到輸出序列。這樣，每一段的卷積都可用上面討論的快速卷積來計算： 1) 先對 h(n)及 xi(n)補零，補到具有N點長度，N=N1+N2-1， 一般選 N=2M，通常取N=256，512 或 1024。 2) 用基2 FFT計算 yi(n)=xi(n)*h(n)。 3) 重疊部分相加構成最后的輸出序列。

30、由于 yi(n)的長度為N，而xi(n)的長度為N2，因此相鄰兩段 yi(n)序列必然有N-N2=N1-1點發(fā)生重疊。 計算步驟：a. 準備好濾波器參數(shù) H(k)=DFTh(n)，N點;b. 用N點FFT計算 Xi(k)=DFTxi(n);c. Yi(k)=Xi(k)H(k);d. 用N點IFFT求 yi(n)= IDFTYi(k) ;e. 將重疊部分相加(2)重疊保存 這種方法和第一種方法稍有不同，即上面分段序列中補零的部分不是補零，而是保留原來的輸入序列值，且保留在各段的前端，這時，如果利用DFT實現(xiàn)h(n)和xi(n)的圓周卷積，則每段卷積結果的前N1-1個點不等于線性卷積值應舍去。實現(xiàn)

31、步驟： 1） 定義xi(n) 為 第一段x(n)由于沒有前一段保留信號，在最前面填補N1-1點個零點。 2）用FFT計算每段 與 h(n)的圓周卷積，以 yi(n) 表示，計算過程如圖。 3）對計算得到的yi(n)，去掉其前N1-1點，再把相鄰各段輸出yi(n)順次連接起來構成最終的輸出序列 y(n)。 每段 xi(n)（長為N）與 h(n)(長為N1)的圓周卷積情況： 圓周卷積2 圖 用保留信號代替補零后的局部混淆現(xiàn)象h(-n)n=0n=N1-1h(n)xi(n)N1=4N=14 由于h(n)的長度為N1，當0nN1-2時，h(n-m)N將在xi(m)的尾部出現(xiàn)有非零值，如圖n=1的情況就是

32、如此，所以0nN1-2這部分yi(n)值中將混入xi(m)尾部與h(n-m)N的卷積值，從而使yi(n)不同于線性卷積結果，但當n=N1-1N-1時，則有h(n-m)N =h(n-m)，因此從n=N1-1點開始圓周圈卷積值完全與線性卷積值一樣，yi(n)才是正確的卷積值，而每一段卷積運算結果的前N1-1點的值需去掉。 為了不造成輸出信號遺漏，對 x(n)分段時，需使相鄰兩段有N1-1個點的重疊，即每一輸入段均由N-N1+1個新點和前一段保留下來的N1-1個點所組成。 重疊保留法與重疊相加法的計算量差不多，但省去了重疊相加法最后的相加運算。一般來說，用FFT作信號濾波，只用于FIR濾波器階數(shù) N

33、1大于32( N1為h(n)的長)的情況下，且取N2=(510)N1，這樣可接近于最高效的運算。4) 用FFT計算二維離散的付里葉變換 二維信號也是信號處理的研究對象。二維信號有圖象信號、時空信號、時頻信號等。二維離散付里葉變換可用于處理二維離散信號。 二維離散付里葉變換的定義為： k=0,1,N-1, l=0,1，M-1 式中 二維離散付里葉變換可通過兩次一維離散付里葉變換來實現(xiàn): 1) 作一維N點DFT (對每列 m 做一次，共M次) k=0,1,N-1 ， m=0,1, ,M-1 2) 作M點的DFT (對每行 k 做一次，共N次) k=0,1, ,N-1 ， l=0,1,M-1 這兩次

34、離散付里葉變換都可以用快速算法求得，若M和N都是2的冪，則可使用基二FFT算法，所需要乘法次數(shù)為 而直接計算二維離散付里葉變換所需的乘法次數(shù)為(M+N)MN，當M和N比較大時用用FFT運算，可節(jié)約很多運算量。5) DFT應用中的一些問題利用DFT進行連續(xù)信號頻譜分析的過程：這是一個近似過程，各環(huán)節(jié)都有可能引入誤差。(1)混疊 對連續(xù)信號x(t)進行數(shù)字處理前，要進行采樣 采樣序列的頻譜是連續(xù)信號頻譜的周期延拓，周期為fs，如采樣率過低，不滿足采樣定理，fs2fh，則導致頻譜混迭，使一個周期內的譜對原信號譜產(chǎn)生失真，無法恢復原信號，進一步的數(shù)字處理失去依據(jù)。解決：采樣前進行抗混疊濾波;對截短信號

35、，提高采樣頻率。連續(xù)指數(shù)信號在不同采樣率下的幅度譜連續(xù)指數(shù)信號的幅度譜 (b) 不同采樣率下的幅度譜 (2) 泄漏 處理實際信號序列 x(n)時，一般總要將它截斷為一有限長序列，長為N點，相當于乘以一個矩形窗 w(n)=RN(n)。 矩形窗函數(shù)，其頻譜是一個抽樣函數(shù)，有主瓣，也有許多副瓣，窗口越大，主瓣越窄，當窗口趨于無窮大時，就是一個沖擊函數(shù)。 我們知道，時域的乘積對應頻域的卷積，所以，加窗后的頻譜實際是原信號頻譜與矩形窗函數(shù)頻譜(抽樣函數(shù))的卷積，卷積的結果使頻譜延伸到了主瓣以外，且一直延伸到無窮。當窗口無窮大時，與沖擊函數(shù)的卷積才是其本身，這時無畸變，否則就有畸變。 例如，信號為 ，是一單線譜，但當加窗后，線譜與抽樣函數(shù)進行卷積，原來在0處的一根譜線變成了以0為中心的，形狀為抽樣函數(shù)的譜線序列，原來在一個周期(s)內只有一個頻率上有非零值，而現(xiàn)在一個周期內幾乎所有頻率上都有非零值，即 的頻率成份從0處“泄漏”到其它頻率處去了。 考慮各采樣頻率周期間頻譜“泄漏”后的互相串漏，卷積后還有頻譜混迭現(xiàn)象產(chǎn)生。解決：選擇合適的窗函數(shù)，并截取