數(shù)字信號處理dsp教程-ch2課件

1、第 2 章 離散變換及其快速算法本章內(nèi)容：離散傅里葉級數(shù)（DFS）離散傅立葉變換（DFT）基2快速傅立葉變換（FFT）利用DFT做連續(xù)信號的頻譜分析 FFT在分段卷積等中的應(yīng)用2.1 DFT對于有限長序列，可以用離散傅里葉變換（Discrete Fourier Transform，DFT）來分析，DFT能反映信號的頻域特征且更便于用計算機(jī)處理。傅里葉變換的幾種可能形式四種傅里葉變換形式的歸納時間函數(shù) 頻率函數(shù) 連續(xù)和非周期 非周期和連續(xù) 連續(xù)和周期 非周期和離散 離散和非周期 周期和連續(xù) 離散和周期 周期和離散 一個域的離散對應(yīng)另一個域的周期延拓， 一個域的連續(xù)必定對應(yīng)另一個域的非周期。2.1

2、.1 周期序列的離散傅里葉級數(shù)(DFS)設(shè) 是一個周期為N的周期序列， 即 k次諧波周期序列 基頻（2/N）離散傅里葉級數(shù)取k=0 到N-1的N個獨立諧波分量諧波系數(shù)是以N為周期的周期序列即呈周期性，其周期為N， 推導(dǎo) 離散傅里葉級數(shù)（DFS）只要知道周期序列一個周期的內(nèi)容，其他的內(nèi)容也都知道了。所以，這種無限長序列實際上只有一個周期中的N個序列值有信息。 因而周期序列和有限長序列有著本質(zhì)的聯(lián)系。 例求所示周期序列的離散傅里葉級數(shù)表示式。解：離散傅里葉級數(shù)（DFS）的性質(zhì)1 線性2 序列的移位證：由于都是以N為周期的，即因此 離散傅里葉級數(shù)（DFS）的性質(zhì)3 共軛對稱性復(fù)序列 共軛偶對稱分量

3、共軛奇對稱分量 離散傅里葉級數(shù)（DFS）的性質(zhì)4 周期卷積證 例N=7，計算解：兩個周期序列的周期N=7，周期卷積過程用圖示。周期卷積過程用圖解表示m012345622220000022100000122020000122020000124220000181220000100122000100012200600012202周期卷積過程列表表示周期卷積結(jié)果2.1.2 有限長序列離散傅里葉變換(DFT)周期序列實際上只有有限個序列值有意義設(shè)x(n)為有限長序列，長度為N，x(n)在n=0到N-1點上有值。把 的第一個周期n=0 到n=N-1 定義為“主值區(qū)間”， 故x(n)是 的“主值序列”，即主

4、值區(qū)間上的序列。主值序列把 的第一個周期n=0 到n=N-1 定義為“主值區(qū)間”， 故x(n)是 的“主值序列”，即主值區(qū)間上的序列。0n1N-1，n2為整數(shù) 例例離散傅里葉變換(DFT)0kN-1 0nN-1 離散傅里葉變換隱含著周期性x(n)和X(k)是一個有限長序列的離散傅里葉變換對。已知其中的一個序列，就能惟一地確定另一個序列。這是因為x(n)與X(k)都是點數(shù)為N的序列，都有N個獨立值（可以是復(fù)數(shù)），所以信息等量。 此外，值得強調(diào)得是，在使用離散傅里葉變換時，必須注意所處理的有限長序列都是作為周期序列的一個周期來表示的。 離散傅里葉變換隱含著周期性。簡記為簡記為矩陣方程來表示 例x(

5、n)=(n)，求它的N點DFT不論對它進(jìn)行多少點的DFT，結(jié)果都是一個離散矩形序列解例矩形序列x(n)=RN(n)，求它的N點DFT結(jié)果只有一個非零值N解例求復(fù)數(shù)序列x(n)=1+j， 1-j，j，1的DFT。求得 解 例x(n)=cos(n/6) ，N=12， 求它的N點DFT解離散傅里葉變換的性質(zhì)（1） 線性（2） 循環(huán)移位，圓周移位一個長度為N的有限長序列x(n)的圓周移位定義為f(n)=x(n+m)NRN(n) 圓周移位過程示意圖x(n)向左循環(huán)移位（圓周移位）時，此圓是順時針旋轉(zhuǎn); x(n)向右循環(huán)移位（圓周移位）時，此圓是逆時針旋轉(zhuǎn)。如果圍繞圓周觀察幾圈， 那么看到的就是周期序列循

6、環(huán)移位時域循環(huán)移位定理表明，有限長序列的圓周移位在離散頻域中引入一個和頻率成正比的線性相移 ，而對頻譜的幅度沒有影響。 頻域循環(huán)移位定理調(diào)制特性：說明時域序列的調(diào)制等效于頻域的圓周移位（3） 循環(huán)卷積 (圓周卷積)它和周期卷積過程是一樣的，只不過這里要取主值序列。時域循環(huán)卷積定理推導(dǎo) 頻域循環(huán)卷積定理例計算解（1） 循環(huán)卷積圖示法 N=7N=7解（2） m0123456f(n)x(m)2222000y(m)0022100y(0-m)NRN(n)00012202y(1-m)NRN(n)00001220y(2-m)NRN(n)20000124y(3-m)NRN(n)22000018y(4-m)NR

7、N(n)122000010y(5-m)NRN(n)012200010y(6-m)NRN(n)00122006y(7-m)NRN(n)00012202循環(huán)卷積列表法 例：循環(huán)卷積（圓周卷積）過程示意圖求這兩個矩形序列的循環(huán)卷積。 例 設(shè)兩個有限長序列相等，各為N點，同為矩形序列解：矩形序列的DFT等于N點的循環(huán)卷積5點的循環(huán)卷積9點的循環(huán)卷積兩個序列各增加5個零點，為10點的序列進(jìn)行循環(huán)卷積9點的循環(huán)卷積與線性卷積比較9點的循環(huán)卷積=線性卷積一定條件下，循環(huán)卷積可以等于線性卷積研究循環(huán)卷積與線性卷積的關(guān)系 設(shè)x1(n)是N1點的有限長序列（0nN1-1）， x2(n)是N2點的有限長序列（0nN

8、2-1）。 線性卷積y (n)是N1+N2-1 點有限長序列周期卷積循環(huán)卷積兩序列補充零值至L點 循環(huán)卷積等于線性卷積而不產(chǎn)生混疊的必要條件循環(huán)卷積等于線性卷積而不產(chǎn)生混疊的必要條件y (n)是N1+N2-1 點有限長序列例：線性卷積與圓周卷積線性卷積圓周卷積（4） 共軛對稱性x*(n)為x(n)的共軛復(fù)序列DFTx*(n)=X*(-k)NRN(k)=X*(N-k)NRN(k) =X*(N-k) 0kN-1 X(N)=X(0) X*(N)=X*(0) 證X(k)的隱含周期性，故有X(N)=X(0)共軛對稱性同樣的方法可以證明對稱性是指關(guān)于坐標(biāo)原點的縱坐標(biāo)的對稱性。DTFT一些對稱性質(zhì)，定義了共

9、軛對稱序列與共軛反對稱序列的概念。 DFT有類似的對稱性，但在DFT中，涉及的序列x(n)及其離散傅里葉變換X(k)均為有限長序列，且定義區(qū)間為 0 到N-1，DFT的對稱性是指關(guān)于N/2 點的對稱性。 x(n) 的實部與虛部的DFT共軛（偶）對稱分量共軛奇（反）對稱分量x(n) 的實部與虛部的DFTx(n) 的 共軛對稱和共軛反對稱的DFT共軛（偶）對稱分量共軛奇（反）對稱分量x(n) 的 共軛對稱和共軛反對稱的DFTx(n) 為實序列的偶對稱和奇對稱偶對稱分量奇對稱分量（5） 選頻性例（6） DFT與zT、DTFTx(n)是一個有限長序列，長度為NDFT與序列傅里葉變換、Z變換的關(guān)系X(k

10、) 是X(z)在Z平面單位圓上N點等間隔采樣值， X(k)也可以看作x(n)的X(ej)在區(qū)間0， 2上的N點等間隔采樣，其采樣間隔為N=2/N， 這就是DFT的物理意義。顯而易見，DFT的變換區(qū)間長度N不同， 表示對X(ej)在區(qū)間0， 2上的采樣間隔和采樣點數(shù)不同， 所以DFT的變換結(jié)果也不同。例0n4 求其N=5 點離散傅里葉變換X(k)k=0, N, 2N, 其他 DFS k=0, 1, 2, 3, 4 k=0 k=0, 1, 2, 3, 4 DFTDFT舉例說明x(n)的5點DFT（a） 有限長序列x(n)（b） 由x(n)形成的周期N=5的周期序列（c） 對應(yīng)于 的傅里葉級數(shù)和x(

11、n)的|X(ej)|（d） x(n)的5點DFTDFT舉例說明x(n)的10點DFT（a） 有限長序列x(n) （b） 由x(n)（補零）形成的周期N=10的周期序列（c） x(n)的10點DFT（7） DFT形式下的Parseval定理證進(jìn)一步例2.2 利用DFT做連續(xù)信號的頻譜分析由于DFT具有選頻特性，所以常用它對連續(xù)信號進(jìn)行頻譜分析。這一分析過程是一次次的近似過程。其步驟：（1）采樣連續(xù)信號用離散采樣信號的DTFT來近似連續(xù)信號的傅里葉變換 （2）將x(n)截短 用有限長度序列的DTFT來近似無限長度序列的DTFT（3）對截短的信號做DFT對有限長度序列的DTFT采樣前置低通濾波器LP

12、F，是為了消除或減少時域連續(xù)信號轉(zhuǎn)換成序列時可能出現(xiàn)的頻譜混疊的影響。 在實際工作中，時域離散信號x(n)的時寬是很長的， 甚至是無限長的（例如語音或音樂信號）。由于DFT的需要(實際應(yīng)用FFT計算)，必須把x(n)限制在一定的時間區(qū)間之內(nèi)，即進(jìn)行數(shù)據(jù)截斷。 數(shù)據(jù)的截斷相當(dāng)于加窗處理。 因此， 在計算FFT之前，用一個時域有限的窗函數(shù)w(n)加到x(n)上是非常必要的。可能出現(xiàn)的問題及其解決方法 （1）混疊采樣序列的頻譜是被采樣模擬信號頻譜的周期延拓，當(dāng)采樣頻率不滿足奈奎斯特采樣定理時，就會發(fā)生頻譜的混疊，不能真實地反映原信號的頻譜。解決混疊問題的惟一方法是保證采樣頻率足夠高，以防止頻譜混疊，

13、這意味著通常需要知道原信號的頻譜范圍，以確定采樣頻率。但很多情況下可能無法預(yù)計信號頻率，為確保無混疊現(xiàn)象，可在采樣前利用一模擬低通濾波器（抗混疊濾波器） 。（2）泄漏一個時間有限的信號其頻帶寬度為無限，一個時間無限的信號其頻帶寬度則為有限。在實際DFT運算中，時間長度總是取有限值，在將信號截短的過程中，出現(xiàn)了分散的擴(kuò)展譜線的現(xiàn)象，稱為頻譜泄漏或功率泄漏。由于泄漏使信號的頻譜展寬，泄漏也會引起混疊。 （3）柵欄效應(yīng)DFT是對單位圓上z變換的均勻采樣，頻譜是一組離散譜線。有限長序列的頻譜是連續(xù)狀的。用DFT來觀察頻譜就如同通過一個柵欄來觀看景象一樣，只能在離散點上看到真實的頻譜，這樣一些頻譜的峰點

14、或谷點就有可能被“尖樁的柵欄”擋住，也就是正好落在兩個離散采樣點之間，不能被觀察到。減小柵欄效應(yīng)的一個方法是在原序列的末端填補一些零值，增加了DFT的點數(shù)，從而離散譜線（柵）目加大，相當(dāng)于搬動了“尖樁柵欄”的位置，從而使得頻譜的峰點或谷點暴露出來。柵欄效應(yīng)舉例（4）DFT的分辨率DFT的頻率分辨率通常規(guī)定為fs/N，這里的N是指信號x (n)的有效長度，而不是補零的長度。填補零值可以改變對DTFT的采樣密度，不能提高DFT的頻率分辨率。不同長度的x(n)，其DTFT的結(jié)果是不同的；而相同長度的x(n)只是反映了對相同的DTFT采用了不同的采樣密度。要提高DFT分辨率只有增加信號x/(n)的截取

15、長度N。 例 設(shè)模擬信號xa(t)的最高頻率fmax=5Hz，試求最低采樣頻率fs，在這一采樣頻率下采得256點數(shù)據(jù)，對其做DFT，給出所能得到的最大頻率分辨率f 。解：由采樣定理得 fs=2fmax=10Hzf=10/256= 0.039Hz用FFT進(jìn)行頻譜分析時參數(shù)選擇的一般原則：（一）若已知信號的最高頻率fmax，選定采樣頻率（二）據(jù)實際需要，選定頻率分辨率f，再確定所需DFT長度f越小越好，但f越小，N越大，使計算量、存儲量也隨之增大。（三）根據(jù)fs和N確定模擬信號的時間長度（）周期信號的譜分析圖 (c)和圖 (d)分別是N=16時的截取信號和DFT結(jié)果，由于截取了兩個整周期，得到單一

16、譜線的頻譜。上述頻譜的誤差主要是由于時域中對信號的非整周期截斷產(chǎn)生的頻譜泄漏。圖（a）和圖（b）分別是N=20時的截取信號和 DFT結(jié)果，由于截取了兩個半周期，頻譜出現(xiàn)泄漏；2.3 FFT DFT的運算量每計算一個X(k)值，需要N次復(fù)數(shù)乘法和N-1次復(fù)數(shù)加法。X(k)一共有N個點（k從0取到N-1），所以完成整個DFT運算總共需要N2次復(fù)數(shù)乘法及N(N-1)次復(fù)數(shù)加法。一次復(fù)數(shù)乘法需用四次實數(shù)乘法和二次實數(shù)加法；一次復(fù)數(shù)加法需二次實數(shù)加法。 每運算一個X(k)需4N次實數(shù)乘法和2N+2(N-1)=2(2N-1)次實數(shù)加法。 整個DFT運算總共需要4N2次實數(shù)乘法和2N(2N-1)次實數(shù)加法。

17、 IDFT與DFT的差別只在于WN的指數(shù)符號不同，以及差一個常數(shù)1/N，所以IDFT與DFT具有相同的運算工作量。 FFT的運算量復(fù)數(shù)乘法復(fù)數(shù)加法例 對一幅NN點的二維圖像進(jìn)行DFT變換，如用每秒可做10萬次復(fù)數(shù)乘法的計算機(jī)，當(dāng)N=1024時，問需要多少時間（不考慮加法運算時間）？解 直接計算DFT所需復(fù)乘次數(shù)為（N2)21012次，因此用每秒可做10萬次復(fù)數(shù)乘法的計算機(jī)，則需要近3000小時。 這對實時性很強的信號處理來說，要么提高計算速度，而這樣，對計算速度的要求太高了。另外，只能通過改進(jìn)對DFT的計算方法，以大大減少運算次數(shù)。2.3.1 按時間抽?。―IT）的基 -2 FFT算法（1）

18、WNnk的對稱性Wnk的以下固有特性（2） WNnk的周期性（3） WNnk的可約性按時間抽取 (DIT）法序列x(n)長度為N，且滿足N=2M，M為正整數(shù)。按n的奇偶把x(n)分解為兩個N/2點的子序列：蝶形運算結(jié)構(gòu) 利用G（k）、H（k）的周期特性，有 一個8點DFT由兩個4點DFT組成 由四個2點DFT組成8點DFT 按時間抽取的8點FFT 基2-DIT-FFT N點DFT的一次時域抽取分解圖(N=8)N點DFT的第二次時域抽取分解圖(N=8)一個N=8點DFT分解為四個N/4點DFT按時間抽取的FFT算法與直接計算DFT運算量的比較N=2M，共有M級蝶形， 每級都由N/2個蝶形運算組成

19、，每個蝶形需要一次復(fù)乘、 二次復(fù)加，因而每級運算都需N/2次復(fù)乘和N次復(fù)加，這樣M級運算總共需要 復(fù)乘復(fù)加直接計算DFT與FFT算法的計算量之比N=2048時，這一比值為372.4，即直接計算DFT的運算量是FFT運算量的372.4倍例 用FFT算法處理一幅NN點的二維圖像，如用每秒可做10萬次復(fù)數(shù)乘法的計算機(jī)，當(dāng)N=1024時，問需要多少時間（不考慮加法運算時間）？解 當(dāng)N=1024點時，F(xiàn)FT算法處理一幅二維圖像所需復(fù)數(shù)乘法約為107次，僅為直接計算DFT所需時間的10萬分之一。 即原需要3000小時，現(xiàn)在只需要2 分鐘。FFT算法DFT按時間抽取的FFT算法的特點（1） 蝶形運算N=2M

20、，共有M級蝶形， 每級都由N/2個蝶形運算組成，每個蝶形需要一次復(fù)乘、 二次復(fù)加，因而每級運算都需N/2次復(fù)乘和N次復(fù)加。（2） 原位運算（同址運算）原位運算， 即某一列的N個數(shù)據(jù)送到存儲器后，經(jīng)蝶形運算，其結(jié)果為下一列數(shù)據(jù)，它們以蝶形為單位仍存儲在這同一組存儲器中，直到最后輸出，中間無需其他存儲器。也就是蝶形的兩個輸出值仍放回蝶形的兩個輸入所在的存儲器中。 每列的N/2 個蝶形運算全部完成后， 再開始下一列的蝶形運算。 這樣存儲器數(shù)據(jù)只需N個存儲單元。下一級運算仍采用這種原位方式，只是進(jìn)入蝶形結(jié)的組合關(guān)系有所不同。 這種原位運算結(jié)構(gòu)可以節(jié)省存儲單元， 降低設(shè)備成本。N點DITFFT運算流圖(

21、N=8) 輸入倒序輸出順序（3） 蝶形類型隨迭代次數(shù)成倍增加（4） 序數(shù)重排（倒位序規(guī)律）X(k)按正常順序，即按X(0)，X(1)，X(7)的順序排列，x(n)不是按自然順序存儲的，而是按x(0)，x(4)， ， x(7)的順序存入存儲單元，稱之為倒位序。倒位序的形成如輸入序列的自然順序號為n2n1n0，則其倒位序就是n0n1n2N=8序數(shù)重排過程 十進(jìn)制二進(jìn)制第一次分偶、奇第二次分偶、奇第三次分偶、奇十進(jìn)制0000n0=0000n1=0000n2=000001001010100n2=110042010100n1=1010n2=001023011110110n2=111064100n0=10

22、01n1=0001n2=000115101101101n2=110136110011n1=1011n2=001157111111111n2=11117N=8時的自然順序二進(jìn)制數(shù)和相應(yīng)的倒位序二進(jìn)制數(shù)自然順序（I） 二進(jìn)制數(shù) 倒位序二進(jìn)制數(shù) 倒位序（J） 0123456700000101001110010111011100010001011000110101111104261537N=8 倒位序的變址處理DIT-FFT程序框圖倒序程序框圖DIT-FFT運算程序框圖按時間抽取的FFT算法的其他形式流圖時間抽取、 輸入自然順序、 輸出倒位序的FFT流圖 基2-DIT-FFT 輸入順序輸出倒序基2-D

23、IT-FFT 輸入順序輸出順序2.3.2 按頻率抽?。―IF）的基 -2 FFT算法設(shè)序列點數(shù)為N=2M，M為正整數(shù)。把輸入序列按前一半、后一半分開（不是按偶數(shù)、 奇數(shù)分開）， 把N點DFT寫成兩部分。輸出X(k)按k的奇偶分組。 按頻率抽?。―IF）法按頻率抽取的第一次分解按頻率抽取的第二次分解按頻率抽取的FFT（N=8）信號流圖按頻率抽取法的運算特點（）蝶形運算（）原位計算（）蝶形類型隨迭代次數(shù)成減少盡管蝶形結(jié)構(gòu)不同于按時間抽取FFT，但總的計算量與按時間抽取算法相同。 （）序數(shù)重排 與時間抽取法不同，按頻率抽取法的輸入是自然順序，而輸出是以按位反轉(zhuǎn)的規(guī)律重排。將頻率抽取法的流圖反轉(zhuǎn)，并且

24、將輸入變輸出，輸出變輸入，正好得到時間抽取法的流圖。按頻率抽取法與按時間抽取法是兩種等價的FFT運算 2.3.3 N為組（復(fù)）合數(shù)的FFT算法 問題: N為任意因子的組合數(shù)，N=P1P2 Pm，(Pi是正整數(shù))，如何提高計算效率?最簡單的情況: N=PQ為兩個數(shù)的乘積。(1)將DFT的時間順序n和頻率順序k分別表示成二維的形式 n=n1Q+n0 k=k1P+k0 式中n0, k1分別為0,1,，Q-1;n1, k0分別為0,1,，P-12.3.4 線性調(diào)頻Z變換（Chirp-Z變換）算法螺線采樣Chirp-Z變換的線性系統(tǒng)表示Chirp-Z變換的圓周卷積圖2.4 關(guān)于FFT應(yīng)用中的幾個問題2.

25、4.1 用FFT計算 IDFTIFFT計算分三步： 將X(k)取共軛(虛部乘以-1) 對X*(k)直接作FFT 對FFT的結(jié)果取共軛并乘以1/N，得x(n)2.4.2 實數(shù)序列的FFT大多數(shù)場合下,信號是實數(shù)序列,任何實數(shù)都可看成虛部為零的復(fù)數(shù)：x(n)+j0求某實信號y(n)的復(fù)譜,可認(rèn)為是將實信號加上數(shù)值為零的虛部變成復(fù)信號,再用FFT求其離散付里葉變換。不經(jīng)濟(jì),存儲器要增加一倍,且計算機(jī)運行時,即使虛部為零,也要涉及虛部的運算,浪費了運算量。合理的解決方法是利用復(fù)數(shù)據(jù)FFT對實數(shù)據(jù)進(jìn)行有效計算(1)用 一個N點FFT同時計算兩個N點實序列的DFT設(shè)x(n)、y(n)是彼此獨立的兩個N點實

26、序列,且 X(k)=DFTx(n) ，Y(k)=DFTy(n) 則X(k)、Y(k)可通過一次FFT運算同時獲得。算法：將x(n)、y(n)構(gòu)成一復(fù)序列 g(n)=x(n)+jy(n)通過FFT運算可獲得g(n)的DFT值 G(k)=DFTx(n)+jDFTy(n)=X(k)+jY(k) Gr(k)+jGi(k) =Xr (k)-Yi (k)+j Xi (k)+Yr (k)g(n)的FFT運算結(jié)果G(k), 由上式可得到X(k)、Y(k)。(2)用N點的FFT運算獲得2N點實序列的DFT設(shè)x(n)是2N點實序列,并分為偶數(shù)組x1(n)和奇數(shù)組x2(n) x1(n)=x(2n) x2(n)=x(

27、2n+1) n=0,1,N-1將x1(n)及x2(n)組成一復(fù)序列： y(n)=x1(n)+jx2(n)通過N點FFT運算可得到： Y(k)=X1(k)+jX2(k) N點根據(jù)共軛對稱性，得X1(k)和X2(k) 。再按下式復(fù)合成X(k)2.4.3 線性卷積的FFT算法線性卷積是求離散系統(tǒng)響應(yīng)的主要方法之一許多重要應(yīng)用都建立在這一理論基礎(chǔ)上,如卷積濾波等。用圓周卷積計算線性卷積的方法：長為N2的序列x(n)延長到L,補L-N2個零長為N1的序列h(n)延長到L,補L-N1個零如果LN1+N2-1,則圓周卷積與線性卷積相等,此時,可用FFT計算線性卷積可用FFT計算線性卷積方法a. 計算X(k)

28、=FFTx(n)b. 求 H(k)=FFTh(n)c. 求 Y(k)=H(k)X(k) k=0L-1d. 求 y(n)=IFFTY(k) n=0L-1進(jìn)行二次FFT,一次IFFT就可完成線性卷積計算L32時,上述計算線性卷積的方法比直接計算線卷積有明顯的優(yōu)越性圓周卷積方法為快速卷積法將 x(n) 分為許多段,每段的長度與 h(n) 接近上述結(jié)論適用于 x(n)、h(n) 兩序列長度比較接近或相等的情況如果x(n)、h(n) 長度相差較多如, h(n) 為某濾波器的單位脈沖響應(yīng),長度有限,用來處理一個很長的輸入信號 x(n),或者處理一個連續(xù)不斷的信號，按上述方法, h(n) 要補許多零再進(jìn)行計

29、算,計算量有很大的浪費，或者根本不能實現(xiàn)。為了保持快速卷積法的優(yōu)越性,可將 x(n) 分為許多段,每段的長度與 h(n) 接近處理方法有兩種(1)重疊相加法由分段卷積的各段相加構(gòu)成總的卷積輸出N=N1+N2-1重疊相加法xi(n) 表示 x(n)的第i段只要將x(n)的每一段分別與h(n)卷積，再將這些卷積結(jié)果相加就可得到輸出序列。每一段的卷積都可用快速卷積來計算： 1)先對h(n)及xi(n)補零，補到具有N點長度，N=N1+N2-1。 一般選 N=2M。 2)用基2 FFT計算 yi(n)=xi(n)*h(n) 3)重疊部分相加構(gòu)成最后的輸出序列。由于yi(n)的長度為N，而xi(n)的長

30、度為N2，因此相鄰兩段yi(n)序列必然有N-N2=N1-1點發(fā)生重疊重疊相加法L=N=N1+N2-1重疊相加法N=N1+N2-1計算步驟a. 準(zhǔn)備好濾波器N點參數(shù) H(k)=DFTh(n)b. N點FFT計算Xi(k)=DFTxi(n)c. Yi(k)=Xi(k)H(k)d. N點IFFT求yi(n)=IDFTYi(k)e. 將重疊部分相加N=N1+N2-1重疊相加法例 n 0 1 2 3 4 5 6 7 8 9 10 11 12 13 1415 16h (n) 1 1 1x (n)15 14 13 12 1110 9 8 7 6 5 4 3 2 1x0(n)15 14 13 12 11x1(n)10 9 8 7 6x2(n) 5 4 3 2 1y0(n)15 29 42 39 3623 11y1(n) 10 19 27 24 2113 6y2(n) 5 9 12 9 6 3 1y(n)15 29 42 39 3633 30 27 24 2118 15 12 9 6 3 1 n N1-1 N2-1 N-1 N2+N-1 2N2+N-1N1=3 N2=5 N= N1+ N2-