卷積的快速算法

1、數(shù)字信號(hào)處理課程設(shè)計(jì)報(bào)告卷積的快速算法專 業(yè)： 通信工程 班 級(jí)： 通信08-2BF 組 次： 第10組 姓 名： 卷積的快速算法一、 設(shè)計(jì)目的卷積運(yùn)算是一種有別于其他運(yùn)算的新型運(yùn)算，是信號(hào)處理中一種常用的工具。隨著信號(hào)與系統(tǒng)理論的研究的深入及計(jì)算機(jī)技術(shù)發(fā)展，卷積運(yùn)算被廣泛地運(yùn)用到現(xiàn)代地震勘測(cè)，超聲診斷，光學(xué)診斷，光學(xué)成像，系統(tǒng)辨識(shí)及其他諸多新處理領(lǐng)域中。了解并靈活運(yùn)卷積運(yùn)算用去解決問題，提高理論知識(shí)水平和動(dòng)手能力，才是學(xué)習(xí)卷積運(yùn)算的真正目的。通過這次課程設(shè)計(jì)，一方面加強(qiáng)對(duì)數(shù)字信號(hào)處理這門課程的理解和應(yīng)用，另一方面體會(huì)到學(xué)校開這些大學(xué)課程的意義。二、設(shè)計(jì)任務(wù)探尋一種運(yùn)算量更少，算法步驟更簡(jiǎn)單的

2、算法來實(shí)現(xiàn)卷積運(yùn)算，文中主要通過階梯函數(shù)卷積計(jì)算方法和斜體函數(shù)卷積計(jì)算方法對(duì)比來得出最終結(jié)論。三、設(shè)計(jì)原理1，什么是卷積？卷積是數(shù)字信號(hào)處理中經(jīng)常用到的運(yùn)算。其基本的表達(dá)式為：換而言之，假設(shè)兩個(gè)信號(hào)f1(t)和f2(t)，兩者做卷積運(yùn)算定義為f(t)= -f1()f2(t-)d做一變量代換不難得出：f(t)= -f1()f2(t-)d=f1(t)*f2(t)=f2(t)*f1(t)在教材上，我們知道用圖解法很容易理解卷積運(yùn)算的過程，在此不在贅述。2，什么是階梯函數(shù) 所謂階梯函數(shù)，即是可以用階梯函數(shù)u(t) 和u(t-1)的線性組合來表示的函數(shù)，可以看做是一些矩形脈沖的集合，圖1-1給除了兩個(gè)階

3、梯函數(shù)的例子。 11其中f(t)=2u(t)+u(t-1)-2u（t-2）-u(t-3),h(t)= 2u(t)-u(t-1)+2u(t-2)-3u(t-3).以圖11中兩個(gè)階梯函數(shù)為例介紹本文提出的階梯函數(shù)卷積算法。根據(jù)卷積的性質(zhì)（又稱為杜阿美爾積分），上述f(t)與h(t)的卷積等于f(t)的導(dǎo)數(shù)與 h(t)的積分的卷積，即： f(t)*h(t)=df(t)dt*-thd.由于f(t)為階梯函數(shù)，因此其導(dǎo)數(shù)也為沖擊函數(shù)t及其延時(shí)的線性組合， 如圖12（a）所示。 12由于h(t)也為階梯函數(shù)，所以其積分-thd.也能方便地求得，其值為階梯函數(shù)圖像下方的面積，記作為H(t),如圖12(b)所

4、示：沖擊函數(shù)與其它函數(shù)的卷積有如下的關(guān)系：t-T*f(t)=f(t-T),因此 f(t)*h(t)=2H(t)+2H(t-1)-H(t-2)-H(t-3).即f(t)和(t)的卷積等于H(t)及其延時(shí)的線性組合，如圖1-3所示： 13 從以上分析可以看到，兩個(gè)階梯函數(shù)的卷積等于其中一個(gè)函數(shù)的積分H(t)及其延遲H(t-)的線性組合，組合系數(shù)對(duì)應(yīng)于各個(gè)沖擊函數(shù)的系數(shù)。 對(duì)于任意函數(shù)的卷積，可以先將他們的用矩形脈沖函數(shù)來逼近只要時(shí)間間隔足夠小就能達(dá)到足夠的逼近精度。逼近所得到的函數(shù)即為階梯函數(shù)，然后又采用上述方法即可得到任意兩個(gè)函數(shù)的卷積。 假設(shè)要計(jì)算任意兩個(gè)函數(shù)的卷積:y(t)=x(t)*h(t

5、)其中x(t),h(t)可謂無限長(zhǎng)，分別如圖14（a）,(b)所示?，F(xiàn)將x(t)和h(t)在0到t的區(qū)間用寬度為的矩形脈沖來近似的代替（顯然越小，逼近的精度越高，每一個(gè)矩形脈沖的高度分別等于該脈沖前沿的函數(shù)值。也就是說，用階梯形曲線xn(t)近似地代替x(t)的曲線，用hn(t)近似的代替h(t)(如圖14)。每一個(gè)矩形脈沖可用階躍函數(shù)鄙視如下表21,22.表達(dá)式又可以寫成如下形式：x(t)=m=0xm-xm-1ut-m, 12h(t)=n=0hn-hn-1ut-n, 13對(duì)式（2）求微分有：x(t)=m=0xm-xm-1t-m, 1-4設(shè)t=k,對(duì)3式求積分有：0thd=n=0k-1h(n)

6、 15令H(t)=0thd=H(k),則x't和Hk如圖15a,b所示： 15 x(t),h(t)的微積分 16 x(t),h(t)的卷積過程由y(t)=x(t)*h(t)=x*H(t)得到Y(jié)(k)=n=0kxm-xm-1H(k-m) 16由圖16(a)可以看出如果計(jì)算從t=0至t=k的N點(diǎn)的x(t)和h(t)的卷積，需要H(t)和x(t)對(duì)應(yīng)的個(gè)點(diǎn)分別相乘，由于H(t)和x(t)也為N點(diǎn)序列，所以共需要N2次乘法，屬于有效乘法，因?yàn)榘凑站矸e定義直接計(jì)算也是N2次乘法。3，什么是斜梯函數(shù)？所謂斜梯函數(shù)，表現(xiàn)為一條折線的形式，用諸如at+b形式的段組合在一起表示的函數(shù)。圖31給出了輸入函

7、數(shù)為斜梯函數(shù)的例子。 31其中f(t)=tu(t)-u(t-1)+u(t-1)+(0.5t+0.5)u(t-1)-u(t-2)+(-1.5t+4.5)u(t-2)-u(t-3), h(t)=3tu(t)-u(t-1)+(-t+4)u(t-1)-u(t-2)+(-2t+6)u(t-2)-u(t-3)根據(jù)卷積的性質(zhì)，上述f(t)和h(t)的卷積等于f(t)的二次導(dǎo)數(shù)與h(t)的二重積分的卷積【1】，即：由于f(t)為斜梯函數(shù)，因此其導(dǎo)數(shù)變?yōu)殡A梯函數(shù)u(t)及其延時(shí)的線性組合，df(t)dt=u(t)-0.5u(t-1)-2u(t-2),如圖32(a)所示。 32由于h(t)也為斜梯函數(shù)，所以其積分

8、-thd.也能方便的求得，其值為折現(xiàn)函數(shù)圖象下方的面積，記作為h(-1)(t),如圖32(b)所示。此時(shí)已經(jīng)與階梯函數(shù)卷積計(jì)算方法類似了，只是對(duì)于h(-1)(t)其為一二次曲線，繼續(xù)求積分比較困難，實(shí)際應(yīng)用中其可以用折現(xiàn)計(jì)算，從而引入一定的誤差，這也是采用次逼近所付出的代價(jià)。接下來對(duì)f(t)和h(-1)(t)再次進(jìn)行微分與積分處理，則f(t)變?yōu)闆_擊脈沖序列，如圖33(a)所示，h(-2)(t)用對(duì)應(yīng)折線下的買年紀(jì)也可算得對(duì)應(yīng)如圖33(b)所示。 33斜梯函數(shù)的二次微積分假設(shè)要計(jì)算任意函數(shù)的卷積：y(t)=x(t)*h(t)其中x(t),h(t)可謂無限長(zhǎng)，分別如圖34（a）,(b)所示。 3

9、4 連續(xù)時(shí)間函數(shù) 對(duì)上述x(t)和h(t),用寬度為的梯形脈沖函數(shù)逼近，x(t)和h(t)就轉(zhuǎn)化為斜梯函數(shù)，顧客用折現(xiàn)函數(shù)及其延時(shí)的線性組合表示，如圖34(a),(b)中虛線所示。x(t)=m=0x(m+1-x(m)t+c1u(t-m)-u(t-(m+1) ), 22h(t)= n=0h(n+1-h(n)t+c1u(t-n)-u(t-(n+1) ), 23此處c1,c2為常數(shù)，由于球x(t)和h(t)的微積分時(shí)，與此常數(shù)無關(guān)，所以此處可不必求出。對(duì)式子22，求微分有：x(t)= m=0x(m+1-x(m)t+c1u(t-m)-u(t-(m+1) ), 24設(shè)t=k,對(duì)23式求積分有：0thd=

10、n=0k-112hn+hn+1. 25則 x(t)和h(t)如圖25(a),(b)所示: 35 斜梯函數(shù)的一次微分與積分X(t)=m=0xm+1+x(m-1)-2x(m)t-m 26H(-2)(t)=n=01422(n-1)h(0)+k=1n-14n-khk+h(n) 27式26,27如下圖36所示。 36 斜梯函數(shù)的二次額積分令H(k)=h(-2)(t), 27 x(t)和h(t)的卷機(jī)過程由 y(t)=x(t)*h(t)=x(t)*H(t)得Y(k)=m=0kxm+1+xm-1-2xmH(k-m). 28由圖27 可以清楚的看出如果計(jì)算從0到k的也為N點(diǎn)序列，所以共需要N2次乘法，屬于有效

11、算法。四、設(shè)計(jì)過程 假設(shè)有有一DSP系統(tǒng)，如果激勵(lì)信號(hào)的的波形如圖41所示，定義的時(shí)間區(qū)間是(t0,t)，表示從t0到t之前的任意時(shí)刻。對(duì)于任意輸入信號(hào)的作用，可以看成是一系列具有相同寬度的矩形脈沖用近似表示e().把時(shí)間區(qū)間(t0,t)分成相等的幾段，每段寬度為，即t1-t0=t2-t1=tk+1-tk=.因此e()可以用圖中的階梯曲線來近似表示，即可以看成是一系列的矩形脈沖的合成。這一系列的矩形脈沖可以通過單位脈沖函數(shù)和延遲的單位脈沖函數(shù)，即P()和P(-k)來表示。因此可以用上述矩形脈沖表示e(),即e()=e(t0)P(- t0) +e(t1)P(- t1) + e(t2)P(- t2

12、) + e(tk)P(- tk) +e(tn-1)P(- tn-1) =k=0n-1e(tk)P(- tk) 2-9輸入信號(hào)P()后，其響應(yīng)為h()對(duì)每一延遲的矩形脈沖P(-tk),在時(shí)刻t觀察到的相應(yīng)的響應(yīng)應(yīng)為h(t-tk), e(tk)P(- tk) 的響應(yīng)應(yīng)該為e(tk)h(- tk) ,所以29式的輸出信號(hào)應(yīng)該為： r=k=0n-1e(t- tk) 為了保證e()的階梯矩形近似更接近真實(shí)e()，令t0到t區(qū)間的脈沖數(shù)不斷增加。當(dāng)t時(shí)，0，每個(gè)單位矩形脈沖變成沖擊函數(shù)，h變成了沖擊函數(shù)h，e變成了原來的激勵(lì)e()，響應(yīng)rt則變成了對(duì)應(yīng)原激勵(lì)的響應(yīng)rt,同時(shí)上式的求和也變成了積分，tk變成了連續(xù)變量，則變成了d,于是有 r(t)=t0tetkh(t-)d其中t0為任意激勵(lì)施加的時(shí)刻，t為待求響應(yīng)對(duì)應(yīng)的時(shí)刻。特別的，當(dāng)t0=0時(shí)，有 r(t)=t0tetkh(t-)d 210式子110所示的積分就是卷積的積分。因此，只要知道系統(tǒng)的沖擊響應(yīng)，對(duì)于任意的激勵(lì)信號(hào)e(t)的作用，都可根據(jù)卷積的積分求出響應(yīng)。對(duì)于更為復(fù)雜的二階系統(tǒng)，運(yùn)用這種方法更能看出其優(yōu)勢(shì)，由于計(jì)算過程大致類似，我們應(yīng)用MATLAB自帶的命令計(jì)算結(jié)果繪制于42圖中 42 三種算法的比較 當(dāng)采樣精度為0