重疊保留法源程序設計課程設計

1、<p><b>　　課程設計說明書</b></p><p>　　題目： 重疊保留法源程序設計 </p><p>　　姓 名： </p><p>　　院 （系）： 計算機與通信工程學院 </p>&l

2、t;p>　　專業(yè)班級： 通信工程11-01 </p><p>　　學 號： </p><p>　　指導教師： </p><p>　　成 績： </p><p>　　時間： 2013

3、 年 12月 16 日至 2013 年 12月 20 日</p><p>　　課 程 設 計 任 務 書</p><p>　　題目 重疊保留法源程序設計 </p><p><b>　　主要內容：</b></p><p>　

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

5、p>　　2、個人整理重疊保留法源程序設計的實驗報告</p><p>　　完 成 期 限： 2013年12月18日 </p><p>　　指導教師簽名： </p><p>　　課程負責人簽名： </p><p>　　2013 年 12 月 18 日&l

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

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

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

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

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

11、;·······················5</p><p>　　三、設計·········

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

13、83;·6</p><p>　　1、設計思想······························&

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

15、·······················6</p><p>　　3、程序及結果········

16、83;·······························7</p><p>　　四、遇到問題及

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

18、83;··············9 2、體會··················

19、···························9</p><p>　　六、參考文獻····

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

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

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

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

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

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

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

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

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

29、;<b>　　設計思想</b></p><p>　　重疊保留法相當于將h(n)和xl(n)做循環(huán)卷積，然后找出循環(huán)卷積中相當于線性卷積的部分。在這種情況下，將序列y(n)分為唱為N的若干段，每個輸入端和前一段有M-1個重疊點。此時只需要將發(fā)生重疊的錢M-1個點舍去，保留重疊部分并輸出，則獲得序列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>　　計算？ </b></p><p>　　輸出序列

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

32、序：</b></p><p>　　function [y] = overlap_save( x, h, N ) %重疊保留法實現(xiàn) </p><p>　　%核心為將高點數(shù)DFT 轉化為低點數(shù)DFT，且用循環(huá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)的長度 </p><p>　　M = length(h); %獲得h(n)的長度 </p><p>　　if N < M

34、 %為N 選擇合適的值保證運算正確 </p><p><b>　　N = M+1; </b></p><p><b>　　end </b></p><p>　　L = N+M-1; %為降低點數(shù),取M+N-1 點循環(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)]; %為不足的分段補零 </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)]; %確定每個低點數(shù)卷積的分段x(n) </p><p>　　t = x_seg(N+1:N+M-1); %為t(n)重新賦值為后M-1 個點的值 </p><p>　　

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

38、 %取出實際的輸出序列 </p><p>　　fprintf('結果\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>　　結果：</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>　　遇到問題及解決方法</b></p><p>　　程序中的分段補零不會，通過查資料后獲得相關代碼。</p&g

42、t;<p>　　matlab剛開始不認識“ Lx = length(x)，M = length(h)”，通過設置“ x=input('x=')，h=input('h=')，N=input('N=')”形參即可。</p><p><b>　　五、討論與總結</b></p><p><b>　　1、算

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

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

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

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