重疊保留法源程序設(shè)計(jì)課程設(shè)計(jì)

1、<p><b>　　課程設(shè)計(jì)說(shuō)明書(shū)</b></p><p>　　題目： 重疊保留法源程序設(shè)計(jì) </p><p>　　姓 名： </p><p>　　院 （系）： 計(jì)算機(jī)與通信工程學(xué)院 </p>&l

2、t;p>　　專(zhuān)業(yè)班級(jí)： 通信工程11-01 </p><p>　　學(xué) 號(hào)： </p><p>　　指導(dǎo)教師： </p><p>　　成 績(jī)： </p><p>　　時(shí)間： 2013

3、 年 12月 16 日至 2013 年 12月 20 日</p><p>　　課 程 設(shè) 計(jì) 任 務(wù) 書(shū)</p><p>　　題目 重疊保留法源程序設(shè)計(jì) </p><p><b>　　主要內(nèi)容：</b></p><p>　

4、　1、編寫(xiě)重疊保留法源程序，不能使用matlab自帶的函數(shù)</p><p>　　2、程序運(yùn)行結(jié)果與matlab自帶函數(shù)結(jié)果進(jìn)行對(duì)比</p><p>　　3、完成符合學(xué)校要求的設(shè)計(jì)說(shuō)明書(shū)</p><p><b>　　基本要求：</b></p><p>　　1、小組討論并完善重疊保留法的源程序</p><

5、p>　　2、個(gè)人整理重疊保留法源程序設(shè)計(jì)的實(shí)驗(yàn)報(bào)告</p><p>　　完 成 期 限： 2013年12月18日 </p><p>　　指導(dǎo)教師簽名： </p><p>　　課程負(fù)責(zé)人簽名： </p><p>　　2013 年 12 月 18 日&l

6、t;/p><p>　　重疊保留法源程序設(shè)計(jì) </p><p>　　摘要：重疊保留法在運(yùn)用時(shí)，隨著數(shù)據(jù)規(guī)模的增大，運(yùn)算耗時(shí)呈線(xiàn)性增長(zhǎng)。當(dāng)數(shù)據(jù)達(dá)到千萬(wàn)量級(jí)時(shí)，運(yùn)算延時(shí)最少大約為2.335s，由此可見(jiàn)，此方法可運(yùn)用于對(duì)信號(hào)的實(shí)時(shí)處理，同時(shí)重疊保留法具有較好的時(shí)間和空間復(fù)雜度。本次課程設(shè)計(jì)以matlab為工具得到重疊保留法的源程序，通過(guò)對(duì)序列的線(xiàn)性卷積計(jì)算，進(jìn)而對(duì)重疊保留法進(jìn)行更深層次的認(rèn)識(shí)。<

7、/p><p>　　關(guān)鍵字：重疊保留法 序列線(xiàn)性卷積</p><p><b>　　目錄</b></p><p>　　一、前言···················

8、····························5</p><p>　　二、重疊保留法原理5</p><p

9、>　　1、背景 ···································

10、;·········5</p><p>　　2、原理·······················

11、;·······················5</p><p>　　三、設(shè)計(jì)·········

12、;····································

13、83;·6</p><p>　　1、設(shè)計(jì)思想······························&

14、#183;··········6</p><p>　　2、流程圖·····················

15、·······················6</p><p>　　3、程序及結(jié)果········

16、83;·······························7</p><p>　　四、遇到問(wèn)題及

17、解決方法8</p><p><b>　　五、總結(jié)9</b></p><p>　　1、算法效率分析······················

18、83;··············9 2、體會(huì)··················

19、···························9</p><p>　　六、參考文獻(xiàn)····

20、3;····································10

21、</p><p><b>　　前言</b></p><p>　　重疊保留法可運(yùn)用于對(duì)信號(hào)的實(shí)時(shí)處理，具有較好的時(shí)間和空間復(fù)雜度。此次實(shí)驗(yàn)，使用matlb對(duì)重疊保留法進(jìn)行源程序設(shè)計(jì)，通過(guò)對(duì)序列的線(xiàn)性卷積計(jì)算，我們可以對(duì)重疊保留法的優(yōu)缺點(diǎn)進(jìn)行更深刻的認(rèn)識(shí)。</p><p><b>　　二、重疊保留法原理</b></p&g

22、t;<p><b>　　1、背景</b></p><p>　　對(duì)于線(xiàn)性非移變離散系統(tǒng)，可由線(xiàn)性卷積表示時(shí)域輸入輸出關(guān)系，即</p><p>　　y(n)=x(n)*h(n)</p><p>　　線(xiàn)性卷積是求離散系統(tǒng)響應(yīng)的主要方法之一，許多重要應(yīng)用都建立在這一理論基礎(chǔ)上，如卷積濾波等，但此方法適用于x(n)、h(n)兩序列長(zhǎng)度比較接

23、近或相等的情況，如果x(n)、h(n)長(zhǎng)度相差較多，按上述方法，h(n)要補(bǔ)許多零再進(jìn)行計(jì)算，計(jì)算量有很大的浪費(fèi)，或者根本不能實(shí)現(xiàn)。為了保持快速卷積法的優(yōu)越性，可將x(n)分為許多段后處理，每小段的長(zhǎng)與h(n)接近，其處理方法有兩種：重疊相加法和重疊保留法。</p><p>　　通常采用循環(huán)卷積降低運(yùn)算量，但實(shí)際中往往無(wú)法滿(mǎn)足對(duì)信號(hào)處理的實(shí)時(shí)性要求。因此，產(chǎn)生了重疊相加法和重疊保留法兩種典型的算法，用以快速計(jì)算線(xiàn)

24、性積，成為了DFT的一個(gè)重要應(yīng)用。</p><p><b>　　2、原理</b></p><p>　　假定xi(n)表示圖中第i段x(n)序列如下圖：</p><p>　　，則輸入序列可表為：</p><p>　　于是輸出可分解為： ，其中</p><p>　　由此表明，只要將x(n)的每一段分

25、別與h(n)卷積，然后再將這些卷積結(jié)果相加起來(lái)就可得到輸出序列，這樣，每一段的卷積都可用上面討論的快速卷積來(lái)計(jì)算。先對(duì)h(n)及xi(n)保留原來(lái)的輸入序列值，且保留在各段的前端，N=N1+N2-1，</p><p>　　由于yi(n)長(zhǎng)度為N，而xi(n)的長(zhǎng)度為N2，因此相鄰兩yi(n)序列必然有N-N2=N1-1點(diǎn)發(fā)生重疊，這個(gè)重疊部分應(yīng)該相加起來(lái)才能構(gòu)成最后的輸出序列。重疊保留法每一輸入段均由N-N1+1

26、=N2個(gè)新點(diǎn)和前一段保留下來(lái)的N1-1個(gè)點(diǎn)所組成。值得注意的是，對(duì)于有限長(zhǎng)時(shí)間序列x(n)（長(zhǎng)度為L(zhǎng)=MN2），在結(jié)束段（i=M-1）做完后，我們所得到的只是L點(diǎn)的線(xiàn)性卷積，還少了N1-1點(diǎn)，實(shí)際上就是h(-n)移出x(n)尾部時(shí)的不完全重合點(diǎn)，或者說(shuō)是最后一段的重疊部分N1-1少做了一次卷積，為此，因再補(bǔ)做這一段N1-1點(diǎn)，在其后填補(bǔ)N2點(diǎn)個(gè)零點(diǎn)保證長(zhǎng)度仍為N點(diǎn)，一樣舍去前取N1-1點(diǎn)，并從N1-1點(diǎn)開(kāi)始，保留N1-1點(diǎn)。 </

27、p><p>　　重疊保留法每一輸入段均由N-N1+1=N2個(gè)新點(diǎn)和前一段保留下來(lái)的N1-1個(gè)點(diǎn)所組成。值得注意的是，對(duì)于有限長(zhǎng)時(shí)間序列x(n)（長(zhǎng)度為L(zhǎng)=MN2），在結(jié)束段（i=M-1）做完后，我們所得到的只是L點(diǎn)的線(xiàn)性卷積，還少了N1-1點(diǎn)，實(shí)際上就是h(-n)移出x(n)尾部時(shí)的不完全重合點(diǎn)，或者說(shuō)是最后一段的重疊部分N1-1少做了一次卷積，為此，因再補(bǔ)做這一段N1-1點(diǎn)，在其后填補(bǔ)N2點(diǎn)個(gè)零點(diǎn)保證長(zhǎng)度仍為N點(diǎn)，

28、一樣舍去前取N1-1點(diǎn)，并從N1-1點(diǎn)開(kāi)始，保留N1-1點(diǎn)。 </p><p>　　重疊保留法與重疊相加法的計(jì)算量差不多，但省去了重疊相加法最后的相加運(yùn)算。一般來(lái)說(shuō)，用FFT作信號(hào)濾波，只用于FIR濾波器階數(shù)h（n）大于32的情況下，且取N2=（5～10）N1，這樣可接近于最高效的運(yùn)算。</p><p><b>　　設(shè)計(jì)</b></p><p>

29、;<b>　　設(shè)計(jì)思想</b></p><p>　　重疊保留法相當(dāng)于將h(n)和xl(n)做循環(huán)卷積，然后找出循環(huán)卷積中相當(dāng)于線(xiàn)性卷積的部分。在這種情況下，將序列y(n)分為唱為N的若干段，每個(gè)輸入端和前一段有M-1個(gè)重疊點(diǎn)。此時(shí)只需要將發(fā)生重疊的錢(qián)M-1個(gè)點(diǎn)舍去，保留重疊部分并輸出，則獲得序列y(n)。</p><p>　　2、流程圖   </

30、p><p><b>　　輸入序列</b></p><p><b>　　X(n)，h(n)</b></p><p><b>　　完成所有分段 </b></p><p><b>　　計(jì)算？ </b></p><p>　　輸出序列

31、 y(n) </p><p><b>　　結(jié)束</b></p><p>　　3、程序及結(jié)果     </p><p><b>　　程

32、序：</b></p><p>　　function [y] = overlap_save( x, h, N ) %重疊保留法實(shí)現(xiàn) </p><p>　　%核心為將高點(diǎn)數(shù)DFT 轉(zhuǎn)化為低點(diǎn)數(shù)DFT，且用循環(huán)卷積計(jì)算線(xiàn)性卷積 </p><p>　　x=input('x=');</p><p>　　h=inpu

33、t('h=');</p><p>　　N=input('N=')</p><p>　　Lx = length(x); %獲得x(n)的長(zhǎng)度 </p><p>　　M = length(h); %獲得h(n)的長(zhǎng)度 </p><p>　　if N < M

34、 %為N 選擇合適的值保證運(yùn)算正確 </p><p><b>　　N = M+1; </b></p><p><b>　　end </b></p><p>　　L = N+M-1; %為降低點(diǎn)數(shù),取M+N-1 點(diǎn)循環(huán)卷積即可 </p><p>　　t =

35、zeros(1,M-1); %初始化序列t(n) </p><p>　　T = ceil(Lx/N); %確定分段數(shù) </p><p>　　x = [x,zeros(1, (T+1)*N-Lx)]; %為不足的分段補(bǔ)零 </p><p>　　y = zeros(1, (T+1)*N); </p><p&g

36、t;　　for i = 0:1:T </p><p>　　xi = i*N+1; </p><p>　　x_seg = [t,x(xi:xi+N-1)]; %確定每個(gè)低點(diǎn)數(shù)卷積的分段x(n) </p><p>　　t = x_seg(N+1:N+M-1); %為t(n)重新賦值為后M-1 個(gè)點(diǎn)的值 </p><p>　　

37、y_seg = circular_conv(x_seg,h,L); %循環(huán)卷積計(jì)算線(xiàn)性卷積 </p><p>　　y(xi:xi+N-1) = y_seg(M:N+M-1); %直接取出后N 個(gè)點(diǎn)作為一次計(jì)算的輸出 </p><p><b>　　end </b></p><p>　　y=y(1:Lx+M-1);

38、 %取出實(shí)際的輸出序列 </p><p>　　fprintf('結(jié)果\n',y);</p><p><b>　　輸入：</b></p><p>　　x=[1 2 3 4 5 1 2 3 4 5 1 2 3 4 5]</p><p><b>　　h=[1 0 2]</b

39、></p><p><b>　　N=5</b></p><p><b>　　N =5</b></p><p><b>　　結(jié)果：</b></p><p><b>　　ans =</b></p><p>　　Columns 1

40、through 8 </p><p>　　1.0000 2.0000 5.0000 8.0000 11.0000 9.0000 12.0000 5.0000</p><p>　　Columns 9 through 16 </p><p>　　8.0000 11.0000 9.0000 12.0000 5.00

41、00 8.0000 11.0000 8.0000</p><p>　　Column 17 </p><p><b>　　10.0000</b></p><p><b>　　遇到問(wèn)題及解決方法</b></p><p>　　程序中的分段補(bǔ)零不會(huì)，通過(guò)查資料后獲得相關(guān)代碼。</p&g

42、t;<p>　　matlab剛開(kāi)始不認(rèn)識(shí)“ Lx = length(x)，M = length(h)”，通過(guò)設(shè)置“ x=input('x=')，h=input('h=')，N=input('N=')”形參即可。</p><p><b>　　五、討論與總結(jié)</b></p><p><b>　　1、算

43、法效率分析 </b></p><p>　　重疊保留法運(yùn)行效率與分段長(zhǎng)度相關(guān)性較強(qiáng)。分段和卷積運(yùn)算的序列 長(zhǎng)度長(zhǎng)度為非線(xiàn)性關(guān)系，且當(dāng)分段長(zhǎng)度維持在大約1000點(diǎn)左右時(shí)，獲得最高的平均運(yùn)行效率。內(nèi)置函數(shù)conv()運(yùn)行效率與分段數(shù)無(wú)關(guān)。</p><p>　　在實(shí)際應(yīng)用中，重疊保留主要用于實(shí)施信號(hào)處理，因而輸入序列是連續(xù)輸入，在保證實(shí)時(shí)性的要求下，輸入序列的分段不能太長(zhǎng)。</

44、p><p><b>　　心得體會(huì)</b></p><p>　　Matlab是一款功能強(qiáng)大且實(shí)用的軟件，在這次的課程設(shè)計(jì)后，我對(duì)matlab有了更深刻的了解和掌握。通過(guò)在matlab上對(duì)線(xiàn)性卷積的調(diào)試，我逐漸發(fā)現(xiàn)，線(xiàn)性重疊法可實(shí)時(shí)輸出處理過(guò)的分段序列，與直接線(xiàn)性卷積相比，實(shí)用性很強(qiáng)，需要的計(jì)算單元特別是系統(tǒng)緩存明顯減少，同時(shí)也具有較好的時(shí)間和空間復(fù)雜度；與重疊相加法相比，重

45、疊保留法省去了重疊相加法最后的相加運(yùn)算?？偠灾?，重疊保留法在現(xiàn)實(shí)中的應(yīng)用具有很好的優(yōu)勢(shì)。雖然此次課程設(shè)計(jì)中遇到了許許多多的問(wèn)題，但是通過(guò)小組討論解決這些問(wèn)題后，我對(duì)自己不擅長(zhǎng)的知識(shí)進(jìn)行近一步的補(bǔ)充。在此次課程設(shè)計(jì)中，我們小組分工協(xié)作、互幫互助，最終完成了重疊保留法的源程序設(shè)計(jì)，結(jié)果無(wú)疑是令人興奮的。通過(guò)這次課程設(shè)計(jì)以后，我不僅對(duì)重疊保留法有了更深入的了解，同時(shí)，我們小組的默契度也提高了，相信，在以后的課程設(shè)計(jì)中，我們小組對(duì)課題的完成率

46、更高。</p><p><b>　　。</b></p><p><b>　　參考文獻(xiàn)</b></p><p>　　1、鄭君里等編，信號(hào)與系統(tǒng)，北京：高等教育出版社，1981</p><p>　　2、丁玉梅，高西全編著，數(shù)字信號(hào)處理，西安：西安電子科技大學(xué)出版社，2008</p><