數(shù)字信號(hào)處理重疊保留法

1、武漢理工大學(xué)數(shù)字信號(hào)處理課程設(shè)計(jì)說明書課程設(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ù)要求，以及說明書撰寫等具體要求）1、獨(dú)立編寫程序?qū)崿F(xiàn)基于重疊保留法的圓周卷積2、用Matlab驗(yàn)證程序結(jié)果，并分析重疊保留法的圓周卷積的原理3、完成符合學(xué)校要求的設(shè)計(jì)說明書時(shí)間安排：一周，其中3天程序設(shè)計(jì)，2天程序調(diào)試指導(dǎo)教師簽名： 年 月 日系主任（或責(zé)任教師）簽名：

2、 年 月 日目錄摘要.(1)1 概述. (2)2 理論分析.(3)2.1圓周卷積與線性卷積.(3)2.2圓周卷積的計(jì)算.(4)2.3重疊保留法.(5)3 程序設(shè)計(jì).(7) 3.1程序流程.(7) 3.2程序流程圖.(8) 3.3具體程序設(shè)計(jì).(9) 3.4編寫完整的程序.(10)4 結(jié)果及分析.(11)5 心得體會(huì).(12)參考文獻(xiàn).(13)摘要重疊保留法在運(yùn)用時(shí)，隨著數(shù)據(jù)規(guī)模的增大，運(yùn)算耗時(shí)呈線性增長。當(dāng)數(shù)據(jù)達(dá)到千萬量級(jí)時(shí)，運(yùn)算延時(shí)最少大約為2.335s，由此可見，此方法可運(yùn)用于對(duì)信號(hào)的實(shí)時(shí)處理，同時(shí)重疊保留法具有較好的時(shí)間和空間復(fù)雜度。本次課程設(shè)計(jì)以matlab為工具得到重疊保留法的源程序

3、，通過對(duì)序列的線性卷積計(jì)算，進(jìn)而對(duì)重疊保留法進(jìn)行更深層次的認(rèn)識(shí)。關(guān)鍵字：重疊保留法 序列線性卷積 matlab1 概述對(duì)于一個(gè)長序列和一個(gè)短序列，長度分別為，圓周卷積的長度為，在長序列的前面加上個(gè)零，然后對(duì)長序列進(jìn)行分段，使得每段的長度為不足的用零補(bǔ)。且前一分段的后個(gè)抽樣值和后一分段的前個(gè)抽樣值相同。這樣形成的分段序列為：. (1.1)分成的段數(shù)為： (1.2)然后計(jì)算與各個(gè)分段之間的圓周卷積， (1.3)顯然，的前個(gè)值發(fā)生了混疊，不等于和的圓周卷積，把的前個(gè)值舍去，保留沒發(fā)生混疊的后個(gè)值，形成序列： (1.4)最后將各段相加就可以得到最終的結(jié)果， (1.5) 132 理論分析2.1

4、圓周卷積與線性卷積設(shè)和為長度為N的有限長序列，且，如果，則 (2.1.1)證明：相當(dāng)于將作周期卷積和后，再取主值序列。 將周期延拓：則有： (2.1.2) 在主值區(qū)間 ，所以： (2.1.3)同樣可以證明： (2.1.4)定義式（1）為序列與的圓周卷積，習(xí)慣表示為 (2.1.5)從以上的證明過程也可以得出圓周卷積與周期卷積之間的關(guān)系，即有限長序列圓周卷積結(jié)果的周期延拓等于它們周期延拓后的周期卷積。也就是說，周期卷積的主值序列是各周期序列主值序列的圓周卷積。線性卷積是求離散系統(tǒng)響應(yīng)的主要方法之一，許多重要應(yīng)用都建立在這一理論基礎(chǔ)上，如卷積濾波等。用圓周卷積計(jì)算線性卷積的方法歸納如下: 將長為N2

5、的序列x(n)延長到L,補(bǔ)L-N2個(gè)零，將長為N1的序列h(n)延長到L,補(bǔ)L-N1個(gè)零。如果LN1+N2-1,則圓周卷積與線性卷積相等，此時(shí),可有FFT計(jì)算線性卷積，方法如下：         a.計(jì)算X(k)=FFTx(n)         b.求H(k)=FFTh(n)         c.求Y(k)=H(k)X(k) （ k=0L-1）   

6、0;    d.求y(n)=IFFTY(k) （n=0L-1 ）可見，只要進(jìn)行二次FFT,一次IFFT就可完成線性卷積計(jì)算。上述結(jié)論適用于x(n)、h(n)兩序列長度比較接近或相等的情況，如果x(n)、h(n)長度相差較多。例如，h(n)為某濾波器的單位脈沖響應(yīng),長度有限，用來處理一個(gè)很長的輸入信號(hào)x(n)，或者處理一個(gè)連續(xù)不斷的信號(hào)，按上述方法，h(n)要補(bǔ)許多零再進(jìn)行計(jì)算，計(jì)算量有很大的浪費(fèi)，或者根本不能實(shí)現(xiàn)。為了保持快速卷積法的優(yōu)越性，可將x(n)分為許多段后處理，每小段的長與h(n)接近，其處理方法有兩種：重疊相加法和重疊保留法。本文討論重疊保留法。2.2

7、計(jì)算圓周卷積圓周卷積的具體步驟為：第一步：在啞元坐標(biāo)上做與；第二步：把沿著縱坐標(biāo)翻轉(zhuǎn)，得到；第三步：對(duì)做圓周移位，得； 第四步：與對(duì)應(yīng)的相同m的值進(jìn)行相乘，并把結(jié)果進(jìn)行相加，得到的對(duì)應(yīng)于自變量n的一個(gè)；第五步：換另一個(gè)n，重復(fù)第三、四步，直到n取遍0,N-1中的所有值，得到完整的。2.3重疊保留法 為了克服重疊相加法中分段卷積后，仍然需要相加的缺點(diǎn)，人們提出了重疊保留法。這種方法和重疊相加法稍有不同，即將重疊相加法中補(bǔ)零的部分不是補(bǔ)零，而是保留原來的輸入序列值，且保留在各段的前端，這時(shí)，如利用DFT實(shí)現(xiàn)h(n)和xi(n)的圓周卷積，則每段卷積結(jié)果的前N1-1個(gè)點(diǎn)不等于線性卷積值需舍去。 為了

8、清楚地看出這點(diǎn)，研究一下x(n)中一段長為N的序列xi(n)與h(n)（長為N1）的圓周卷積情況： (2.3.1)由于h(n)的長度為N1，當(dāng)0nN1-2時(shí)，h(n-m)N將在xi(m)的尾部出現(xiàn)有非零值，所以0nN1-2這部分yi(n)值中將混入xi(m)尾部與h(n-m)N的卷積值，從而使yi(n)不同于線性卷積結(jié)果，但當(dāng)n=N1-1N-1時(shí)，則有h(n-m)N =h（n-m），因此從n=N1-1點(diǎn)開始圓周圈卷積值完全與線性卷積值一樣，yi(n)的后面N2點(diǎn)才是正確的卷積值，而每一段卷積運(yùn)算結(jié)果的前N1-1點(diǎn)個(gè)值需去掉。圖2.1 重疊保留過程為了不造成輸出信號(hào)遺漏，對(duì)x(n)分段時(shí)，需使相

9、鄰兩段有N1-1個(gè)點(diǎn)的重疊（對(duì)于第一段，x(n)由于沒有前一段保留信號(hào)，在其前填補(bǔ)N1-1點(diǎn)個(gè)零點(diǎn)）。為此將xi(n)定義為 每段和h(n)的圓周卷積以yi(n)表示， ,由FFT算出，去掉yi(n)的前N1-1點(diǎn)，再把相鄰各段輸出順次連接起來就構(gòu)成了最終的輸出序列y(n)。 重疊保留法每一輸入段均由N-N1+1=N2個(gè)新點(diǎn)和前一段保留下來的N1-1個(gè)點(diǎn)所組成。值得注意的是，對(duì)于有限長時(shí)間序列x(n)（長度為L=MN2），在結(jié)束段（i=M-1）做完后，我們所得到的只是L點(diǎn)的線性卷積，還少了N1-1點(diǎn)，實(shí)際上就是h(-n)移出x(n)尾部時(shí)的不完全重合點(diǎn)，或者說是最后一段的重疊部分N1-1少做了

10、一次卷積，為此，因再補(bǔ)做這一段N1-1點(diǎn)，在其后填補(bǔ)N2點(diǎn)個(gè)零點(diǎn)保證長度仍為N點(diǎn)，一樣舍去前取N1-1點(diǎn)，并從N1-1點(diǎn)開始，保留N1-1點(diǎn)。 重疊保留法與重疊相加法的計(jì)算量差不多，但省去了重疊相加法最后的相加運(yùn)算。一般來說，用FFT作信號(hào)濾波，只用于FIR濾波器階數(shù)h（n）大于32的情況下，且取N2=（510）N1，這樣可接近于最高效的運(yùn)算。 3 程序設(shè)計(jì)3.1程序流程要實(shí)現(xiàn)基于重疊保留法的圓周卷積，假設(shè)有兩個(gè)長度分別為N,M（）的序列，要求做和的圓周卷積。首先要對(duì)長序列序列進(jìn)行分段，分段的長度選圓周卷積的長度，形成的分段序列： (3.1.1)然后將逐一和各分段進(jìn)行圓周卷積，得到：

11、 (3.1.2) 最后輸出序列： (3.1.3)這樣即完成了基于重疊保留法的圓周卷積的實(shí)現(xiàn)。同樣，我們可以根據(jù)FFT計(jì)算線性卷積，方法如下：         a.計(jì)算Xi(k)=FFTxi(n)         b.求H(k)=FFTh(n)         c.求Y(k)=H(k)Xi(k) k=0L-1       

12、0; d.求y(n)=IFFTY(k) n=0L-1  可見，只要進(jìn)行二次FFT,一次IFFT就可完成線性卷積計(jì)算。3.2程序流程圖開始輸入x(n),h(n),圓周卷積長度N計(jì)算x(n),h(n)長度及FFT變換長度x(n)序列前加M-1個(gè)0，若長度小于N，補(bǔ)0計(jì)算所需段數(shù)a，控制循環(huán)次數(shù)計(jì)算h(n)的離散傅里葉變換H(k)截取xi=x(K*N+1,K*N+L);X(k)=FFTxi,Y(k)=X(k)*H(k),y(n)=IFFTY(k)截去前M-1個(gè)重疊點(diǎn)，保留M到L點(diǎn)K=a?將保留的點(diǎn)相連，可得y(n)結(jié)束圖3-2 重疊保留法圓周卷積運(yùn)算流程圖3.3具體程序設(shè)計(jì)首先編寫基于重疊

13、保留法的圓周卷積的主函數(shù)。這個(gè)主函數(shù)的功能應(yīng)當(dāng)是計(jì)算出兩個(gè)序列的長度Lx、M，將長序列進(jìn)行分段，然后再將短序列和長序列的各個(gè)分段分別進(jìn)行圓周卷積，將分段卷積的的結(jié)果序列的前M-1個(gè)值舍去，將各個(gè)結(jié)果合并到一個(gè)序列中去，輸出這個(gè)新序列，程序功能基本完成。主函數(shù)的編寫過程如下：定義主函數(shù)：function Y=overlpsav(x,h,N)計(jì)算兩個(gè)序列的長度：Lx=length(x);M=length(h);計(jì)算FFT運(yùn)算序列長度： L=M+N-1;x序列前加M-1個(gè)0，序列后加N個(gè)0：x=zeros(1,M-1),x,zeros(1,N);求截取的段數(shù)：a=floor(Lx+M-1)/N);對(duì)

14、h做快速傅里葉變換：c=fft(h,L);設(shè)置for循環(huán)，截取x的某一段xk，對(duì)xk進(jìn)行FFT變換，對(duì)Y(k)=X(k)*H(k)進(jìn)行反傅里葉變換，截取前M-1點(diǎn)，保留其余點(diǎn)：for K=0:axk=x(K*N+1:K*N+L); b=fft(xk,L);H=ifft(b.*c,L); Y(K*N+1:K*N+N)=H(M:L);end將所有保留的點(diǎn)相連：Y=Y(1:Lx+M-1);3.4編寫完整的程序function Y=overlpsav(x,h,N) Lx=length(x); M=length(h); L=M+N-1; x=zeros(1,M-1),x,zeros(1,N); a=fl

15、oor(Lx+M-1)/N); c=fft(h,L); for K=0:a xk=x(K*N+1:K*N+L); b=fft(xk,L); H=ifft(b.*c,L); Y(K*N+1:K*N+N)=H(M:L); end Y=Y(1:Lx+M-1); 4 結(jié)果及分析假設(shè)有這樣的兩個(gè)序列，序列1為x=1,2,3,4,5,6,7,8,9，序列2為h=3,2要求這兩個(gè)序列基于重疊保留法的的圓周卷積。顯然第一個(gè)序列x的長度為9，第二個(gè)序列h的長度為2，在x序列的頭部加上2-1個(gè)零，尾部加上N=3個(gè)0，拓展為長度為12的序列:x=0,1,2,3,4,5,6,7,8,9,0,0各分段分別為：Xk1=0

16、,1,2,3Xk2=3,4,5,6Xk3=6,7,8,9Xk4=9,0,0,0將每個(gè)分段與h卷積后的序列為：Y1=0,3,8,13Y2=9,18,23,28Y3=18,33,38,43Y4=27,18,0,0的前2-1個(gè)值舍去，再按順序?qū)⑿蛄泻喜?，得到序列：Y=3,8,13,18,23,28,33,38,43,18以上的結(jié)果是根據(jù)計(jì)算所得到的結(jié)果。下面用程序來驗(yàn)證。運(yùn)行程序在comand window中輸入>> x=1,2,3,4,5,6,7,8,9;>> h=3,2;>> Y=overlpsav(x,h,3)得到的結(jié)果為：顯然，計(jì)算結(jié)果和程序運(yùn)行結(jié)果相同.

17、5 心得體會(huì)在本次課程設(shè)計(jì)中，讓我知道了以前所學(xué)信號(hào)與系統(tǒng)與數(shù)字信號(hào)處理的結(jié)合，并在實(shí)際運(yùn)用中設(shè)計(jì)濾波器的過程。課程設(shè)計(jì)不僅要求對(duì)濾波器理論的研究，更重要的是實(shí)際設(shè)計(jì)中遇到的問題。因?yàn)橛辛诉@次課程設(shè)計(jì)，我不得不對(duì)其設(shè)計(jì)原理進(jìn)行更深一層次的理解，對(duì)書中原來學(xué)到的理論，僅知道了其表面，而不知其原因。在設(shè)計(jì)中也使我對(duì)一些概念有了更深刻的認(rèn)識(shí)。例如：在指標(biāo)方面，我混淆了模擬指標(biāo)和數(shù)字指標(biāo)的概念，經(jīng)過老師的點(diǎn)撥，自己更加明確，而且記憶深刻。還有在課程設(shè)計(jì)中每一次的數(shù)據(jù)輸入都有其重要意義，用MATLAB編譯程序時(shí)，可以根據(jù)濾波器指標(biāo)的要求實(shí)時(shí)知道對(duì)濾波器的影響。例如，編好程序后，調(diào)試成功，任意改變輸入阻帶

18、或者通帶衰減，可以看到輸出波形的變化，改變截止頻率wc（帶通和帶阻濾波器為wcl wcu）同樣可以看到輸出波形的變化。由此，對(duì)理論的理解就更加簡單方便，而且記憶力深刻。除此之外，對(duì)程序的編譯不是一蹴而就的，而是經(jīng)過多次的編譯與調(diào)試。以前用MATLAB就是簡單的輸入，可以說都不是自己的勞動(dòng)成果，但這次不一樣，課程設(shè)計(jì)沒有別人給你編好，而是自己寫，出錯(cuò)率就大大提高了，但這是過程，學(xué)習(xí)就是在過程中進(jìn)行的，經(jīng)過自己幾天的腦力勞動(dòng)，再加上同學(xué)們的幫助，不僅對(duì)讀程序有了很大提高，而且自己的編譯水平也上了一個(gè)新臺(tái)階，更加熟系了MATLAB的應(yīng)用，也對(duì)其中的函數(shù)有了大概的了解，對(duì)其中一些函數(shù)也相當(dāng)熟練，abs（）、log、exp（）這些都很簡單，濾波器設(shè)計(jì)中用到了ceil（）、freqz（）等很重要的函數(shù)，雖然可以用fir1（）、fir2（）可以直接調(diào)用，但那樣就達(dá)不到對(duì)真正理論設(shè)計(jì)過程的 理解和運(yùn)用。完成整個(gè)設(shè)計(jì)過程后，學(xué)到的東西已經(jīng)不僅僅上面的那些東西，還有同組員的共同努力和探討和設(shè)計(jì)過程中的每一個(gè)細(xì)節(jié)，也許每一個(gè)細(xì)節(jié)的錯(cuò)誤就可能導(dǎo)致結(jié)局的失敗，所以我認(rèn)為這次收獲最大的莫過于靜心，學(xué)習(xí)不能急，一定要冷靜，心無旁騖，不放過任何一個(gè)細(xì)節(jié)，就能帶來凱旋的消息。在此，感謝老師一學(xué)年以來對(duì)我們不僅學(xué)習(xí)上的關(guān)心，還有生活中的照顧，我也不會(huì)辜負(fù)老師的期望，繼續(xù)努力深造。參考文獻(xiàn)