基于重疊相加法圓周卷積的實(shí)現(xiàn)

1、課程設(shè)計(jì)任務(wù)書學(xué)生姓名： 專業(yè)班級(jí)： 指導(dǎo)教師： 工作單位： 信息工程學(xué)院 題 目：基于重疊相加法圓周卷積的實(shí)現(xiàn)初始條件： 具備數(shù)字信號(hào)處理的理論知識(shí)；具備Matlab編程能力；分析重疊相加法的圓周卷積的原理；提供編程所需要的計(jì)算機(jī)一臺(tái)要求完成的主要任務(wù)：（包括課程設(shè)計(jì)工作量及其技術(shù)要求，以及說(shuō)明書撰寫等具體要求）1、獨(dú)立編寫程序?qū)崿F(xiàn)基于重疊相加法的圓周卷積2、用Matlab驗(yàn)證程序結(jié)果，并分析重疊相加法的圓周卷積的原理3、完成符合學(xué)校要求的設(shè)計(jì)說(shuō)明書時(shí)間安排：一周，其中3天程序設(shè)計(jì)，2天程序調(diào)試指導(dǎo)教師簽名： 年 月 日系主任（或責(zé)任教師）簽名： 年 月 日目 錄摘要21 概述32 理論分析

2、42.1圓周卷積原理42.2重疊相加法52.3重疊相加法圓周卷積62.4線性卷積、圓周卷積、重疊相加法、DFT、FFT之間的聯(lián)系83 程序設(shè)計(jì)93.1程序設(shè)計(jì)思路93.2程序設(shè)計(jì)流程圖103.3 程序代碼104結(jié)果分析124.1線性卷積結(jié)果124.2重疊相加法圓周卷積結(jié)果135心得體會(huì)14 參考文獻(xiàn)15摘要MATLAB是矩陣實(shí)驗(yàn)室（Matrix Laboratory）的簡(jiǎn)稱，是美國(guó)MathWorks公司出品的商業(yè)數(shù)學(xué)軟件，主要用于算法開發(fā)、數(shù)據(jù)可視化、數(shù)據(jù)分析以及數(shù)值計(jì)算等領(lǐng)域。本次課程設(shè)計(jì)將通過(guò)MATLAB軟件進(jìn)行重疊相加法圓周卷積的設(shè)計(jì)，并對(duì)其具體過(guò)程進(jìn)行分析。關(guān)鍵詞：MATLAB 重疊相

3、加法 圓周卷積1概述MATLAB的基本數(shù)據(jù)單位是矩陣，它的指令表達(dá)式與數(shù)學(xué)、工程中常用的形式十分相似，故用MATLAB來(lái)解算問(wèn)題要比用C，F(xiàn)ORTRAN等語(yǔ)言完成相同的事情簡(jiǎn)捷得多，并且MATLAB也吸收了像Maple等軟件的優(yōu)點(diǎn)，使MATLAB成為一個(gè)強(qiáng)大的數(shù)學(xué)軟件。在新的版本中也加入了對(duì)C，F(xiàn)ORTRAN，C+ ，JAVA的支持?？梢灾苯诱{(diào)用，用戶也可以將自己編寫的實(shí)用程序?qū)氲組ATLAB函數(shù)庫(kù)中方便自己以后調(diào)用，此外許多的MATLAB愛(ài)好者都編寫了一些經(jīng)典的程序，用戶可以直接進(jìn)行下載就可以使用。MATLAB具有以下特點(diǎn)：1.高效的數(shù)值計(jì)算及符號(hào)計(jì)算功能，能使用戶從繁雜的數(shù)學(xué)運(yùn)算分析中解

4、脫出來(lái)；2.具有完備的圖形處理功能，實(shí)現(xiàn)計(jì)算結(jié)果和編程的可視化；3.友好的用戶界面及接近數(shù)學(xué)表達(dá)式的自然化語(yǔ)言，使學(xué)者易于學(xué)習(xí)和掌握；4.功能豐富的應(yīng)用工具箱，為用戶提供了大量方便實(shí)用的處理工具。2 理論分析2.1圓周卷積原理對(duì)兩個(gè)N點(diǎn)序列和，除了可以做線性卷積外，還有一種很重要的卷積運(yùn)算，就是圓周卷積。令則圓周卷積結(jié)果長(zhǎng)度不變, 為N.由上式可以得出圓周卷積與周期卷積的關(guān)系，就是有限長(zhǎng)序列圓周卷積結(jié)果的周期延拓，等于它們周期延拓后的周期卷積。也就是說(shuō)，周期卷積的主值序列，是各周期序列主值序列的圓周卷積。若、分別是長(zhǎng)度為N、M的序列則與線性卷積至多M+N-1個(gè)非零值，如果LM+N-1時(shí)，周期延

5、拓才不會(huì)發(fā)生混疊。之所以討論用圓周卷積來(lái)計(jì)算線性卷積的條件，是因?yàn)閳A周卷積可在頻域下利用DFT求得，從而可采用DFT的快速算法FFT來(lái)計(jì)算，這樣就可以利用FFT來(lái)計(jì)算線性卷積，大大提高運(yùn)算效率。圓周卷積的實(shí)現(xiàn)步驟如下圖：補(bǔ)零：按要求使兩序列補(bǔ)零后均為N點(diǎn)周期延拓：將一個(gè)序列按M點(diǎn)延拓為周期序列翻褶：將延拓后的周期序列翻褶取主值序列：對(duì)翻褶后的周期序列取主值 圓周移位：對(duì)此主值序列做圓周移位（n）相乘：每次移位后的序列與另一序列相乘相加：將諸m點(diǎn)（m=0,1m-1）的乘積值相加，即為移位n點(diǎn)后的y（n）值（n=0,1n-1）圖2.1 圓周卷積的實(shí)現(xiàn)步驟2.2重疊相加法DFT 是連續(xù)傅里葉變換在時(shí)

6、域和頻域上都離散的形式，將時(shí)域信號(hào)的采樣變換為在離散時(shí)間傅里葉變換頻域的采樣。在形式上，變換兩端（時(shí)域和頻域上）的序列是有限長(zhǎng)的。DFT 具備明確且合理的物理含義，適合應(yīng)用于數(shù)字系統(tǒng)，同時(shí)可以方便地由計(jì)算機(jī)進(jìn)行運(yùn)算。對(duì)于線性非移變離散系統(tǒng)，可由線性卷積表示時(shí)域輸入輸出關(guān)系，即y(n)=x(n)*h(n)通常采用循環(huán)卷積降低運(yùn)算量，但實(shí)際中往往無(wú)法滿足對(duì)信號(hào)處理的實(shí)時(shí)性要求。因此，產(chǎn)生了重疊相加法，用以快速計(jì)算線性卷積，成為了DFT 的一個(gè)重要應(yīng)用。重疊相加法是將待過(guò)濾的信號(hào)分割成長(zhǎng)為N 的若干段，如圖1 所示，每一段都可以和有限時(shí)寬單位取樣響應(yīng)作卷積，再將過(guò)濾后的各段重疊相加。具體算法實(shí)現(xiàn)原理

7、如圖2 所示，建立緩存序列，每次輸入N 點(diǎn)序列，通過(guò)計(jì)算x(n) 和h(n) 的循環(huán)卷積實(shí)現(xiàn)線性卷積運(yùn)算，將緩存的M-1 點(diǎn)序列和卷積結(jié)果相加，并輸出前N 點(diǎn)作為計(jì)算結(jié)果，同時(shí)緩存后M-1 點(diǎn)，如此循環(huán)，直至所有分段計(jì)算完畢，則輸出序列y(n)為最終計(jì)算結(jié)果。圖2.2 重疊相加法的分段示意圖圖2.3 重疊相加法算法示意圖2.3重疊相加法圓周卷積在實(shí)際應(yīng)用中利用FFT來(lái)計(jì)算兩個(gè)序列的圓周卷積從而實(shí)現(xiàn)計(jì)算其線性卷積，但是常遇到的問(wèn)題是參加卷積的兩個(gè)序列的長(zhǎng)度相差較大，這樣長(zhǎng)度小的序列就需要補(bǔ)很多的零點(diǎn)，這樣就需要較大的存儲(chǔ)量，運(yùn)算時(shí)間也會(huì)變長(zhǎng)。所以常用到的解決方法有兩種，其中一種就是重疊相加法。h

8、(n)長(zhǎng)度為N，x(n)長(zhǎng)度為無(wú)限長(zhǎng)，x(n)取M點(diǎn)，且與N盡量接近x(n)與h(n)的卷積為圖2.4 重疊相加法的卷積示意圖重疊相加法的步驟如下（1）將h(n)補(bǔ)零延長(zhǎng)到L =M+ N -1，并計(jì)算長(zhǎng)為L(zhǎng)的FFT，得到 H(k)。（2）分別將xk(n)補(bǔ)零延長(zhǎng)到L =M+ N -1，并計(jì)算長(zhǎng)為L(zhǎng)的FFT，得到 Xk(k)（3）計(jì)算，并求長(zhǎng)為L(zhǎng)的反變換，即（4）將yk(n)的重疊部分相加，最后得到結(jié)果為2.4線性卷積、圓周卷積、重疊相加法、DFT、FFT之間的聯(lián)系由時(shí)域與頻域的關(guān)系可知，兩序列和在時(shí)域下進(jìn)行線性卷積的結(jié)果等于這兩個(gè)序列在頻域下相乘后進(jìn)行反變換回時(shí)域的結(jié)果。圓周卷積在一定條件下（

9、LM+N-1）與線性卷積得到的結(jié)果相同，而圓周卷積可在頻域下利用DFT求得，從而可采用DFT的快速算法FFT來(lái)計(jì)算，這樣就可以利用FFT來(lái)計(jì)算線性卷積，大大提高運(yùn)算效率。而在利用FFT來(lái)計(jì)算圓周卷積的過(guò)程中當(dāng)兩序列的長(zhǎng)度相差較大時(shí)采用重疊相加法來(lái)進(jìn)行計(jì)算可有效提高計(jì)算的效率，減小存儲(chǔ)空間的消耗。3 程序設(shè)計(jì)3.1程序設(shè)計(jì)思路線性卷積函數(shù)iconv (x1,x2,L)設(shè)計(jì)（1） x1(n)進(jìn)行N點(diǎn)快速傅里葉變換得X1(k)（2） x2(n)進(jìn)行N點(diǎn)快速傅里葉變換得X2(k)（3） 進(jìn)行頻域相乘Y(k)=X1(k)*X2k（4） 對(duì)Y(k)進(jìn)行反變換得到時(shí)域卷積結(jié)果y(n)圓周卷積函數(shù)oconv(

10、x,h,N)設(shè)計(jì)方案1：（1）首先取長(zhǎng)序列x(n)進(jìn)行分段的長(zhǎng)度N，以使其分段后的長(zhǎng)度與較短的相近（2）確定圓周卷積的周期L（3）填充序列使得循環(huán)中對(duì)序列的索引不會(huì)超出范圍（4）確定分段數(shù)K（5）對(duì)序列進(jìn)行分段調(diào)用conv ()函數(shù)計(jì)算圓周卷積（6）各段重疊相加（7）取出實(shí)際的輸出序列方案2：（1）首先取圓周卷積的周期L（即進(jìn)行L點(diǎn)的快速傅里葉變換）（2）計(jì)算每一分段的大小N（3）填充序列使得循環(huán)中對(duì)序列的索引不會(huì)超出范圍（4）計(jì)算分段數(shù)T（5）對(duì)序列進(jìn)行分段調(diào)用conv ()函數(shù)計(jì)算圓周卷積（6）各段重疊相加（7）取出實(shí)際的輸出序列結(jié)論：方案二比較接近我們平常的思維，使用較為方便，利于程序調(diào)試。3.2程序設(shè)計(jì)流程圖開始輸入序列x(n),h(n)計(jì)算各個(gè)序列長(zhǎng)度，分段數(shù)，生成臨時(shí)序列填入保留值后分段循環(huán)卷積輸出前N個(gè)點(diǎn)并為t(n)重新賦為保留值完成所有分段計(jì)算輸出序列y（n）結(jié)束圖3.1 程序設(shè)計(jì)流程圖3.3 程序代碼function y = iconv( x1,x2,L) % 利用循環(huán)卷積計(jì)算線性卷積 % 循環(huán)卷積采用頻域計(jì)算方法,已FFT代替DFT,降低運(yùn)算量 X1k = fft(x1,L); %x1做L點(diǎn)FFT X2k = fft(x2,L); %x1做L點(diǎn)FFT Yk = X1k.*X2k; %頻域相乘 y = ifft(Yk); %FFT反變換得循環(huán)卷積結(jié)