序列的卷積和快速卷積運(yùn)算的編程實(shí)現(xiàn)

1、課程設(shè)計(jì)任務(wù)書(shū)學(xué)生姓名： 韓新穎 專(zhuān)業(yè)班級(jí)： 電信1203班 指導(dǎo)教師： 闕大順 王虹 工作單位： 信息工程學(xué)院 題 目: 序列的卷積和快速卷積運(yùn)算的編程實(shí)現(xiàn) 初始條件：1. Matlab6.5以上版本軟件；2. 課程設(shè)計(jì)輔導(dǎo)資料：“Matlab語(yǔ)言基礎(chǔ)及使用入門(mén)”、“數(shù)字信號(hào)處理原理與實(shí)現(xiàn)”、“Matlab及在電子信息課程中的應(yīng)用”等；3. 先修課程：信號(hào)與系統(tǒng)、數(shù)字信號(hào)處理、Matlab應(yīng)用實(shí)踐及信號(hào)處理類(lèi)課程等。要求完成的主要任務(wù)：（包括課程設(shè)計(jì)工作量及其技術(shù)要求，以及說(shuō)明書(shū)撰寫(xiě)等具體要求）1. 課程設(shè)計(jì)時(shí)間：1周（課內(nèi)實(shí)踐）；2. 課程設(shè)計(jì)內(nèi)容：序列的卷積和快速卷積運(yùn)算的編程實(shí)現(xiàn)，具體

2、包括：直接卷積及應(yīng)用、快速卷積方法及實(shí)現(xiàn)、兩者的比較分析等；3. 本課程設(shè)計(jì)統(tǒng)一技術(shù)要求：研讀輔導(dǎo)資料對(duì)應(yīng)章節(jié)，對(duì)選定的設(shè)計(jì)題目進(jìn)行理論分析，針對(duì)具體設(shè)計(jì)部分的原理分析、建模、必要的推導(dǎo)和可行性分析，畫(huà)出程序設(shè)計(jì)框圖，編寫(xiě)程序代碼（含注釋?zhuān)?，上機(jī)調(diào)試運(yùn)行程序，記錄實(shí)驗(yàn)結(jié)果（含計(jì)算結(jié)果和圖表），并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析和總結(jié)；4. 課程設(shè)計(jì)說(shuō)明書(shū)按學(xué)?！罢n程設(shè)計(jì)工作規(guī)范”中的“統(tǒng)一書(shū)寫(xiě)格式”撰寫(xiě)，具體包括： 目錄； 與設(shè)計(jì)題目相關(guān)的理論分析、歸納和總結(jié)； 與設(shè)計(jì)內(nèi)容相關(guān)的原理分析、建模、推導(dǎo)、可行性分析； 程序設(shè)計(jì)框圖、程序代碼（含注釋?zhuān)?、程序運(yùn)行結(jié)果和圖表、實(shí)驗(yàn)結(jié)果分析和總結(jié)； 課程設(shè)計(jì)的心得體會(huì)

3、（至少500字）； 參考文獻(xiàn)； 其它必要內(nèi)容等。 指導(dǎo)教師簽名： 年 月 日系主任（或責(zé)任教師）簽名： 年 月 日 摘 要卷積在數(shù)字信號(hào)處理中有著重要的作用。然而直接計(jì)算卷積的運(yùn)算量非常大，它與序列長(zhǎng)度的平方成反比，因此制約了卷積的應(yīng)用。快速卷積是實(shí)現(xiàn)卷積的一種快速算法，減少了運(yùn)算量，節(jié)約了時(shí)間。通過(guò)分析我們可在MATLAB里編程實(shí)現(xiàn)。關(guān)鍵詞：卷積；快速卷積；MATLAB。目錄1、直接卷積及應(yīng)用11.1卷積的定義11.2、卷積的運(yùn)用12、快速卷積方法及實(shí)現(xiàn)22.1快速卷積運(yùn)算原理22.2實(shí)現(xiàn)方法3重疊相加法3重疊保留法33、直接卷積和快速卷積的分析比較44、程序設(shè)計(jì)及仿真結(jié)果分析45、心得體會(huì)

4、116、參考文獻(xiàn)121、直接卷積及應(yīng)用1.1卷積的定義設(shè):f(x),g(x)是R1上的兩個(gè)可積函數(shù)，作積分：可以證明，關(guān)于幾乎所有的實(shí)數(shù)x，上述積分是存在的。這樣，隨著x的不同取值，這個(gè)積分就定義了一個(gè)新函數(shù)h(x)，稱為函數(shù)f與g的卷積，記為h(x)=(f*g)(x)。1.2、卷積的運(yùn)用 卷積是數(shù)字信號(hào)處理中最常見(jiàn)，也是最重要的運(yùn)算之一，利用卷積可以實(shí)現(xiàn)相關(guān)計(jì)算和FIR濾波等等，正因?yàn)榫矸e如此重要，所以半個(gè)世紀(jì)以來(lái)，學(xué)者們提出了多種不同卷積實(shí)現(xiàn)結(jié)構(gòu)。設(shè)輸入信號(hào)為x（t）,其頻譜函數(shù)為X（j）該信號(hào)通過(guò)濾波器h（t）后，其輸出信號(hào)y（t）的頻譜函數(shù)Y（j）是頻譜函數(shù)x（j）與濾波器的頻譜函數(shù)H

5、（j）的乘積，即： Y（j）=X（j）H（j）而在時(shí)域，輸出信號(hào)y(t)實(shí)際是輸入信號(hào)x(t)與濾波器h(t)的卷積，就是說(shuō)頻譜函數(shù)的乘積相當(dāng)于時(shí)間函數(shù)的卷積，反之亦然，即： y(t)=x(t)*h(t)在數(shù)字信號(hào)處理系統(tǒng)中，無(wú)論在時(shí)域還是頻域都離不開(kāi)卷積運(yùn)算和快速傅里葉運(yùn)算，Matlab具有強(qiáng)大的矩陣運(yùn)算能力。方便實(shí)用的繪圖功能和語(yǔ)言的高度集成性。在DSP開(kāi)發(fā)中，使用Matlab可以快速對(duì)系統(tǒng)進(jìn)行仿真運(yùn)算。2、快速卷積方法及實(shí)現(xiàn)2.1快速卷積運(yùn)算原理在信號(hào)處理中，許多具體的應(yīng)用是以線性卷積為基礎(chǔ)的。當(dāng)滿足一定條件時(shí)，可以用圓周卷積來(lái)計(jì)算線性卷積。由圓周卷積定理知道，圓周卷積可以借助DFT來(lái)運(yùn)

6、算，因此DFT的快速算法FFT就可以用來(lái)計(jì)算線性卷積。設(shè)x1（n）與x2（n）分別是長(zhǎng)度為N與M的有限長(zhǎng)序列，它們的線性卷積為yl（n），L點(diǎn)的圓周卷積為yc（n），它們的關(guān)系為 yc（n）=yl(n+rL)Rl(n)由上式可知圓周卷積是線性卷積以L為周期進(jìn)行延拓后，再取主值序列的結(jié)果。當(dāng)滿足L>M+N-1時(shí)，周期延拓不發(fā)生混疊，就可以用圓周卷積來(lái)計(jì)算線性卷積。由圓周卷積定義可知，可以用FFT分別求出x1（n）與x2（n）的L點(diǎn)DFT X1（k）與X2（k），即 X1（k）=DFT x1(n）, X2（k）=DFT x2(n) ,再用IFFT計(jì)算X1(k）X2(k)的L點(diǎn)IDFT得yc（

7、n），也就是x1（n）與x2（n）的線性卷積為yl(n),即 yl(n)=yc(n)=IDFTX1(k)·X2（k）下圖為上述過(guò)程的示意圖L點(diǎn)的FFTx1(n)L點(diǎn)的IFFTyc(n）=yl(n)L點(diǎn)的FFTx2(n)2.2實(shí)現(xiàn)方法在實(shí)際應(yīng)用中，常遇到的問(wèn)題是參加卷積的兩個(gè)序列的長(zhǎng)度相差較大，這樣長(zhǎng)度小的序列就需補(bǔ)很多的零點(diǎn)，這樣就需要大的存儲(chǔ)量，運(yùn)算時(shí)間也會(huì)變長(zhǎng)。常用的解決方法有兩種，一是重疊相加法，另一種是重疊保留法。重疊相加法 設(shè)序列x1（n）為無(wú)限長(zhǎng)序列，序列x2（n）是長(zhǎng)度為M的序列，由x1(n)構(gòu)成長(zhǎng)度為N的有限長(zhǎng)序列 x1k(n)= x1(n), kN<n<

8、(k+1)N-1 = 0 其他 （式2.1）因此 x1k(n)= x1k(n) （式2.2）將式子代入卷積公式有 Y(n)=x1(n)*x2(n)=x2(n)* x1k(n) =x1k(n)*x2(n)= yk(n) （式2.3）式中， yk(n)=x2(n)*xk(n)= x2(m)xk(n-m) （式2.4）式（2.3）表示，計(jì)算x1(n)與x2（n）的線性卷積y(n)時(shí)，可以先分段計(jì)算yk(n),然后再疊加起來(lái)即可。因?yàn)閥k(n)的長(zhǎng)度為M+N-1，因此yk（n）的后N-1個(gè)值與yk+1(n)的前N-1個(gè)值重疊，因此必須把yk(n)的后N-1個(gè)值與yk+1（n）前的N-1個(gè)值相加，因?yàn)榉Q

9、為重疊相加法。重疊保留法 為了克服重疊相加法中分段卷積后任然需要相加的缺點(diǎn)，人們提出了重疊保留法。與重疊相加法不同的是，在對(duì)無(wú)限長(zhǎng)序列x1(n)的后M-1個(gè)抽樣值與后一段xk+1(n)的前M-1個(gè)抽樣值相同，且分段的長(zhǎng)度選圓周卷積的長(zhǎng)度L，這樣形成的分段序列為然后計(jì)算x2（n）與各分段x1k(n)之間的卷積： Yk=x2(n)*x1k(n)顯然，yk(n)的前M-1個(gè)值發(fā)生了混疊，不等于x2(n)與x1k(n)的線性卷積。把yk(n)的前M-1個(gè)值舍去，保留yk(n)沒(méi)有發(fā)生混疊的后N個(gè)值，形成序列 X1k= x(n+kN-M+1), 0<n<L-1 = 0 其他最后輸出序列 y(

10、n)= yk(n-kN+M-1)3、直接卷積和快速卷積的分析比較卷積是數(shù)字信號(hào)處理中最常見(jiàn)的，也是最重要的運(yùn)算之一。利用卷積可以實(shí)現(xiàn)相關(guān)計(jì) 算和FIR濾波等等，正因?yàn)榫矸e如此重要，所以半個(gè)世紀(jì)以來(lái)，學(xué)者們提出了多種不同卷積實(shí)現(xiàn)結(jié)構(gòu)，這些結(jié)構(gòu)各有優(yōu)點(diǎn)，針對(duì)不同應(yīng)用可以靈活選擇，而其中快速卷積無(wú)疑是重要的卷積方法之一。顧名思義，快速卷積重點(diǎn)在一個(gè)“快”，如果對(duì)卷積速度要求較高，快速卷積無(wú)疑是理想的工具。當(dāng)然，為了提高速度，就要犧牲面積和功耗4、程序設(shè)計(jì)及仿真結(jié)果分析1、已知線性非移變系統(tǒng)的h(n)=6,2,3,6,4,2，輸入為x(n)=1,2,3,4,5；(1)用人工計(jì)算系統(tǒng)輸出y(n)；(2)

11、編寫(xiě)程序輸出y(n)，并作圖。人工計(jì)算： 長(zhǎng)度為m的向量序列h和長(zhǎng)度為n的向量序列x，卷積w的向量序列長(zhǎng)度為（m+n-1）,當(dāng)不等于n時(shí)，應(yīng)以0補(bǔ)齊階次低的向量的高位后進(jìn)行計(jì)算y(1)=h(1)*x(1)y(2)=h(1)*x(2)+h(2)*x(1).y(n)=h(1)*x(n)+h(2)*x(n-1)+.+h(n)*x(1).y(m+n-1)=h(1)*x(m+n-1)+h(2)*x(m+n-2)+.+h(m+n-1)*x(1)那么根據(jù)這個(gè)規(guī)律人工計(jì)算的結(jié)果為y(n)=6,14,25,36,63,50,55,52,28,10用matlab仿真編程程序如下：h=6,2,3,6,4,2;x=1

12、,2,3,4,5;y=conv(h,x);stem(y)結(jié)果如圖4.1所示：圖4.1由圖4.1和自己求出的y(n)函數(shù)相比較可以得到，用matlab編寫(xiě)程序得出的系統(tǒng)輸出函數(shù)與自己人工計(jì)算的結(jié)果相同。2、用函數(shù)conv和FFT計(jì)算長(zhǎng)為1000序列的卷積，比較其計(jì)算時(shí)間。在matlab實(shí)現(xiàn)卷積的.函數(shù)為CONV，對(duì)于N值較小的向量，這是十分有效的對(duì)于N大的向量卷積可用FFT加快計(jì)算速度。 若DFT和IDFT均采用FFT和IDFT法，可提高卷積速度。 計(jì)算x1(n)和x2(n)的線性卷積的FFT算法可由下面步驟實(shí)現(xiàn)： 1、計(jì)算X1(k)=FFTx1(n); 2、計(jì)算X2(k)=FFTx2(n);

13、3、Y(k)=X1(k)·X2(k); 4、計(jì)算x1(n)×x2(n)=IFFTY(k) 在本題目中計(jì)算的兩個(gè)函數(shù)分別是x1(n)=2*10n,x2(n)=cos(n3)。用Matlab編寫(xiě)的程序如下：L=1000; N=L*2-1; n=1:L; x1=2*(n.10); x2=cos(n.3); t0=clock; yc=conv(x1,x2); conv_time=etime(clock,t0) N=pow2(nextpow2(L*2-1);t0=clock; yf=ifft(fft(x1,N).*fft(x2,N); fft_time=etime(clock,t0)

14、 subplot(221),stem(x1, '.');ylabel('x(n)');subplot(222),stem(x2,'.');ylabel('h(n)'); subplot(212),stem(real(yc),'.');ylabel('y(n)');在Matlab中編程以及得出的完成程序所需的時(shí)間如圖4.2： 圖4.2輸出結(jié)果如圖4.3： 圖4.3 該題要求的是對(duì)用函數(shù)conv和FFT計(jì)算1000點(diǎn)的序列卷積所需的時(shí)間進(jìn)行對(duì)比，通過(guò)圖4.2可知，用函數(shù)conv計(jì)算該卷積需要0.0100

15、s，而用FFT計(jì)算該卷積需要0s，由此可以得出：FFT算法所消耗的時(shí)間遠(yuǎn)小于函數(shù)conv要消耗的時(shí)間。3、用快速卷積法計(jì)算和兩個(gè)序列的卷積；并測(cè)試直接卷積和快速卷積的時(shí)間。利用快速卷積原理求兩個(gè)函數(shù)的卷積可以用題目二中所用的方法（先分別對(duì)兩個(gè)函數(shù)求傅里葉變換得到X(k)與H(k)，再兩個(gè)函數(shù)傅里葉變換的點(diǎn)乘的結(jié)果y(k)，最后直接對(duì)y(k)求傅里葉反變換得到y(tǒng)(n)）快速卷積，得到所要求的結(jié)果。 因?yàn)樵谶@次題目中與 兩個(gè)函數(shù)中M與N沒(méi)有給出，所以就分別取M=50，N=30和M=1500，N=1100分別求該題目所說(shuō)并得到結(jié)果: 所用的程序以及輸出結(jié)果分別如下圖所示：（1）M=50，N=30的情

16、況：圖4.4圖4.5（2）M=1500，N=1100的情況：圖4.6 圖4.7題目3要求計(jì)算兩序列的卷積，比較直接卷積和快速卷積的時(shí)間對(duì)比由上圖的結(jié)果可知，當(dāng)說(shuō)算積分的點(diǎn)數(shù)比較少時(shí)，快速卷積并不占有優(yōu)勢(shì)，反而快速卷積所用時(shí)間多于正常的卷積conv函數(shù)。只有當(dāng)積分的點(diǎn)數(shù)比較多時(shí)才會(huì)有快速卷積所用時(shí)間少于普通卷積的conv函數(shù)。5、心得體會(huì)在得到這次課設(shè)題目以后，我就開(kāi)始準(zhǔn)備資料了，先是上網(wǎng)查閱基本資料，做一個(gè)大概的了解，然后發(fā)現(xiàn)此次題目卷積和快速卷積在課本上能找到相關(guān)的內(nèi)容，就再在書(shū)上進(jìn)行尋找，發(fā)現(xiàn)了書(shū)上有介紹快速卷積的方法就進(jìn)行閱讀并學(xué)習(xí)，在做好準(zhǔn)備后就開(kāi)始進(jìn)行課設(shè)的三個(gè)題目了，第一題很好解答

17、很快也完成了，感覺(jué)信心倍增，但是在做第二題時(shí)，符號(hào)打入Matlab中老是不符合規(guī)范，進(jìn)行了多次改進(jìn)也沒(méi)辦法，于是就在網(wǎng)上找到了類(lèi)似的借用了一下，過(guò)程中也發(fā)現(xiàn)了問(wèn)題，快速傅里葉計(jì)算所花費(fèi)的時(shí)間比直接卷積的時(shí)間花費(fèi)更多，這是個(gè)遺留問(wèn)題，對(duì)程序進(jìn)行了很多改進(jìn)，但是結(jié)果每次出來(lái)都不一樣，但是多幾次就會(huì)發(fā)現(xiàn)規(guī)律，還是快速傅里葉變化時(shí)間短的次數(shù)更多，第三題用第二題的方法類(lèi)似的方法進(jìn)行，雖然也遇到了類(lèi)似的問(wèn)題但是還是多次實(shí)驗(yàn)取數(shù)目得到規(guī)律使實(shí)驗(yàn)完成，這次課設(shè)讓我收獲了很多，從書(shū)本走到了實(shí)際這是長(zhǎng)足的進(jìn)步，也讓我對(duì)知識(shí)有了更深得的理解，紙上得來(lái)終覺(jué)淺，只有真正實(shí)際操作過(guò)，才能有所得，所以我覺(jué)得課設(shè)還是要自己做才有意義，一是多多鍛煉自己，二是鞏固知識(shí)加深記憶，遇到問(wèn)題想辦法克服問(wèn)題，這是很重要的一步，也是自身能力的體現(xiàn)，我希望以后的課設(shè)都能靠自己的力量去完成得到更多的東西！6、參考文獻(xiàn)1 劉泉等.數(shù)字信號(hào)處理原理與實(shí)