課程設計任務書
學生姓名專業班級
指導教師： 黃朝兵工作單位： 資訊工程學院
題目：基於重疊保留法圓周卷積的實現
初始條件：
具備數字訊號處理的理論知識；
具備matlab程式設計能力；
分析重疊保留法的圓周卷積的原理；
提供程式設計所需要的計算機一台
要求完成的主要任務：（包括課程設計工作量及其技術要求，以及說明書撰寫等具體要求）
1、獨立編寫程式實現基於重疊保留法的圓周卷積
2、用matlab驗證程式結果，並分析重疊保留法的圓周卷積的原理
3、完成符合學校要求的設計說明書
時間安排：
一周，其中3天程式設計，2天程式除錯
指導教師簽名年月日
系主任（或責任教師）簽名年月日
目錄摘要1)
1 概述2)
2 理論分析3)
2.1圓周卷積與線性卷積3)
2.2圓周卷積的計算4)
2.3重疊保留法5)
3 程式設計7)
3.1程式流程7)
3.2程式流程圖8)
3.3具體程式設計9)
3.4編寫完整的程式10)
4 結果及分析11)
5 心得體會12)
參考文獻13)
摘要重疊保留法在運用時，隨著資料規模的增大，運算耗時呈線性增長。當資料達到千萬量級時，運算延時最少大約為2.335s，由此可見，此方法可運用於對訊號的實時處理，同時重疊保留法具有較好的時間和空間複雜度。
本次課程設計以matlab為工具得到重疊保留法的源程式，通過對序列的線性卷積計算，進而對重疊保留法進行更深層次的認識。
關鍵字：重疊保留法序列線性卷積 matlab
對於乙個長序列和乙個短序列，長度分別為，，圓周卷積的長度為，在長序列的前面加上個零，然後對長序列進行分段，使得每段的長度為不足的用零補。且前一分段的後個抽樣值和後一分段的前個抽樣值相同。這樣形成的分段序列為：
1.1)
分成的段數為：
1.2)
然後計算與各個分段之間的圓周卷積，
1.3)
顯然，的前個值發生了混疊，不等於和的圓周卷積，把的前個值捨去，保留沒發生混疊的後個值，形成序列：
1.4)
最後將各段相加就可以得到最終的結果，
1.5)
設和為長度為n的有限長序列，且，，如果，則
2.1.1)
證明：相當於將作週期卷積和後，再取主值序列。
將週期延拓：則有：
2.1.2)
在主值區間，所以：
2.1.3)
同樣可以證明：
2.1.4)
定義式（1）為序列與的圓周卷積，習慣表示為
2.1.5)
從以上的證明過程也可以得出圓周卷積與週期卷積之間的關係，即有限長序列圓周卷積結果的週期延拓等於它們週期延拓後的週期卷積。也就是說，週期卷積的主值序列是各週期序列主值序列的圓周卷積。
線性卷積是求離散系統響應的主要方法之一，許多重要應用都建立在這一理論基礎上，如卷積濾波等。
用圓周卷積計算線性卷積的方法歸納如下:
將長為n2的序列x(n)延長到l,補l-n2個零，將長為n1的序列h(n)延長到l,補l-n1個零。如果l≥n1+n2-1,則圓周卷積與線性卷積相等，此時,可有fft計算線性卷積，方法如下：
a.計算x(k)=fft[x(n)]
b.求h(k)=fft[h(n)]
c.求y(k)=h(k)x(kk=0～l-1）
d.求y(n)=ifft[y(k)] （n=0～l-1 ）
可見，只要進行二次fft,一次ifft就可完成線性卷積計算。
上述結論適用於x(n)、h(n)兩序列長度比較接近或相等的情況，如果x(n)、h(n)長度相差較多。例如，h(n)為某濾波器的單位脈衝響應,長度有限，用來處理乙個很長的輸入訊號x(n)，或者處理乙個連續不斷的訊號，按上述方法，h(n)要補許多零再進行計算，計算量有很大的浪費，或者根本不能實現。為了保持快速卷積法的優越性，可將x(n)分為許多段後處理，每小段的長與h(n)接近，其處理方法有兩種：
重疊相加法和重疊保留法。本文討論重疊保留法。
2.2計算圓周卷積
圓周卷積的具體步驟為：
第一步：在啞元座標上做與；
第二步：把沿著縱座標翻轉，得到；
第三步：對做圓周移位，得；
第四步：與對應的相同m的值進行相乘，並把結果進行相加，得到的對應於自變數n的乙個；
第五步：換另乙個n，重複第
三、四步，直到n取遍[0,n-1]中的所有值，得到完整的。
2.3重疊保留法
為了克服重疊相加法中分段卷積後，仍然需要相加的缺點，人們提出了重疊保留法。這種方法和重疊相加法稍有不同，即將重疊相加法中補零的部分不是補零，而是保留原來的輸入序列值，且保留在各段的前端，這時，如利用dft實現h(n)和xi(n)的圓周卷積，則每段卷積結果的前n1-1個點不等於線性卷積值需捨去。
為了清楚地看出這點，研究一下x(n)中一段長為n的序列xi(n)與h(n)（長為n1）的圓周卷積情況： (2.3.1)
由於h(n)的長度為n1，當0≤n≤n1-2時，h((n-m))n將在xi(m)的尾部出現有非零值，所以0≤n≤n1-2這部分yi(n)值中將混入xi(m)尾部與h((n-m))n的卷積值，從而使yi(n)不同於線性卷積結果，但當n=n1-1～n-1時，則有h((n-m))n =h（n-m），因此從n=n1-1點開始圓周圈卷積值完全與線性卷積值一樣，yi(n)的後面n2點才是正確的卷積值，而每一段卷積運算結果的前n1-1點個值需去掉。
圖2.1 重疊保留過程
為了不造成輸出訊號遺漏，對x(n)分段時，需使相鄰兩段有n1-1個點的重疊（對於第一段，x(n)由於沒有前一段保留訊號，在其前填補n1-1點個零點）。為此將xi(n)定義為
每段和h(n)的圓周卷積以yi(n)表示， ,由fft算出，去掉yi(n)的前n1-1點，再把相鄰各段輸出順次連線起來就構成了最終的輸出序列y(n)。
重疊保留法每一輸入段均由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點，一樣捨去前取n1-1點，並從n1-1點開始，保留n1-1點。
重疊保留法與重疊相加法的計算量差不多，但省去了重疊相加法最後的相加運算。一般來說，用fft作訊號濾波，只用於fir濾波器階數h（n）大於32的情況下，且取n2=（5～10）n1，這樣可接近於最高效的運算。
3.1程式流程
要實現基於重疊保留法的圓周卷積，假設有兩個長度分別為n,m（）的序列，，要求做和的圓周卷積。首先要對長序列序列進行分段，分段的長度選圓周卷積的長度，形成的分段序列：
3.1.1)
然後將逐一和各分段進行圓周卷積，得到：
3.1.2)
最後輸出序列：
3.1.3)
這樣即完成了基於重疊保留法的圓周卷積的實現。
同樣，我們可以根據fft計算線性卷積，方法如下：
a.計算xi(k)=fft[xi(n)]
b.求h(k)=fft[h(n)]
c.求y(k)=h(k)xi(kk=0～l-1
d.求y(n)=ifft[y(k)] n=0～l-1
可見，只要進行二次fft,一次ifft就可完成線性卷積計算。
3.2程式流程圖
圖3-2 重疊保留法圓周卷積運算流程圖
3.3具體程式設計
首先編寫基於重疊保留法的圓周卷積的主函式。這個主函式的功能應當是計算出兩個序列的長度lx、m，將長序列進行分段，然後再將短序列和長序列的各個分段分別進行圓周卷積，將分段卷積的的結果序列的前m-1個值捨去，將各個結果合併到乙個序列中去，輸出這個新序列，程式功能基本完成。主函式的編寫過程如下：
定義主函式：function [y]=overlps**(x,h,n)
數字訊號處理複習
一 填空題 1 對模擬訊號 一維訊號，是時間的函式 進行取樣後，就是離散訊號，再進行幅度量化後就是數碼訊號。2 若線性時不變系統是有因果性，則該系統的單位取樣響應序列h n 應滿足的充分必要條件是當n 0時，h n 0 3 序列的n點dft是的z變換在單位圓的n點等間隔取樣。4 只有當迴圈卷積長度l...
數字訊號處理實驗
一 實驗目的 研究不同型別的窗函式，研究一些不同的方法來測試窗函式的效能 專注於有關窄帶訊號的幾個不同的情形。二 實驗原理 訊號是無限長的，而在進行訊號處理時只能採用有限長訊號，所以需要將訊號 截斷 在訊號處理中，截斷 被看成是用乙個有限長的 視窗 看無限長的訊號，或者從分析的角度是無限長的訊號x ...
數碼訊號與處理
姓名 李智鵬 學號 091204117 院系 電氣與電子工程學院 指導老師 方焯 2018 9 23 離散時間訊號與系統 一 一 實驗內容 計算一全通系統 z 1 0.5 1 0.5z 1 的單位取樣響應h n 矩形序列r5 n 的響應 比較該響應與r5 n h n 的結果.2 實驗原理 將單位取樣...