重疊相加法和重疊保留法的原理與實現(xiàn)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上重疊相加法與重疊保存法的原理實現(xiàn)侯凱（吉林大學(xué) 通信工程學(xué)院 吉林 長春 ）0概述線性卷積是求離散系統(tǒng)響應(yīng)的主要方法之一，許多重要應(yīng)用都建立在這一理論基礎(chǔ)上，如卷積濾波等。用圓周卷積計算線性卷積的方法歸納如下: 將長為N2的序列x(n)延長到L,補L-N2個零，將長為N1的序列h(n)延長到L,補L-N1個零。如果LN1+N2-1,則圓周卷積與線性卷積相等，此時,可有FFT計算線性卷積，方法如下：         a.計算X(k)=FFTx(n)     &#

2、160;   b.求H(k)=FFTh(n)         c.求Y(k)=H(k)Y(k) k=0L-1         d.求y(n)=IFFTY(k) n=0L-1  可見，只要進(jìn)行二次FFT,一次IFFT就可完成線性卷積計算。上述結(jié)論適用于x(n)、h(n)兩序列長度比較接近或相等的情況，如果x(n)、h(n)長度相差較多。例如，h(n)為某濾波器的單位脈沖響應(yīng),長度有限，用來處理一個很長的輸入信號x(n)，或者處理

3、一個連續(xù)不斷的信號，按上述方法，h(n)要補許多零再進(jìn)行計算，計算量有很大的浪費，或者根本不能實現(xiàn)。為了保持快速卷積法的優(yōu)越性，可將x(n)分為許多段后處理，每小段的長與h(n)接近，其處理方法有兩種：重疊相加法和重疊保留法。1重疊相加法由分段卷積的各段相加構(gòu)成總的卷積輸出假定xi(n)表示圖中第i段x(n)序列如下圖：則輸入序列可表為： 圖1 長序列分段濾波于是輸出可分解為： 其中 由此表明，只要將x(n)的每一段分別與h(n)卷積，然后再將這些卷積結(jié)果相加起來就可得到輸出序列，這樣，每一段的卷積都可用上面討論的快速卷積來計算。先對h(n)及xi(n)補零，補到具有N點長度，N=N1+N2-

4、1。 一般選擇N=2M，然后用基2 FFT算法通過正反變換計算 由于yi(n)長度為N，而xi(n)的長度為N2，因此相鄰兩yi(n)序列必然有N-N2=N1-1點發(fā)生重疊，這個重疊部分應(yīng)該相加起來才能構(gòu)成最后的輸出序列。 計算步驟： a.  事先準(zhǔn)備好濾波器參數(shù),N點 b.用N點FFT計算c.d.用N點IFFT求e.將重疊部分相加 圖2 重疊相加法示意圖2重疊保存法這種方法和第一種方法稍有不同，即將上面分圖序列中補零的部分不是補零，而是保留原來的輸入序列值，且保留在各段的前端，這時，如利用DFT實現(xiàn)h(n)和xi(n)的圓周卷積，則每段卷積結(jié)果的前N1-1個點不等于線性卷積值需舍去

5、。 為了清楚地看出這點，研究一下x(n)中一段長為N的序列xi(n)與h(n)（長為N1）的圓周卷積情況： 由于h(n)的長度為N1，當(dāng)0nN1-2時，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時，則有h(n-m)N =h（n-m），因此從n=N1-1點開始圓周圈卷積值完全與線性卷積值一樣，yi(n)的后面N2點才是正確的卷積值，而每一段卷積運算結(jié)果的前N1-1點個值需去掉。圖2 重疊保留過程為了不造成輸出信號遺漏，對x(n)分段時，需使相鄰兩段有N

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

7、為此，因再補做這一段N1-1點，在其后填補N2點個零點保證長度仍為N點，一樣舍去前取N1-1點，并從N1-1點開始，保留N1-1點。 重疊保留法與重疊相加法的計算量差不多，但省去了重疊相加法最后的相加運算。一般來說，用FFT作信號濾波，只用于FIR濾波器階數(shù)h（n）大于32的情況下，且取N2=（510）N1，這樣可接近于最高效的運算。 3應(yīng)用舉例例：已知有長序列X=1,2,3,4,5,6,7,8,9,1,2,3,4,5,6,7,8,9,0,0,1,2,3,4,5,6,7,8,9,0, h=3,2,1,4,5，求線性卷積。解：重疊相加法得：Y=3,8,14,24,39,54,69,84

8、,99,87,84,90,69,39,54,69,84,99,84,76,79,53,14,24,39,54,69,84,99,84,76,76,45,0程序：function Y=overpl(x,h,N) %N為分段段長度；x為長序列;h為短序列Lx=length(x);M=length(h);x=x,zeros(1,N);t=zeros(1,M-1);Y=zeros(1,Lx+M-1);a=floor(Lx/N);y2=fft(h,N+M-1);for K=0:a %循環(huán)a+1次 A=x(K*N+1:K*N+N); y1=fft(A,N+M-1); y3=y1.*y2; q=ifft(y3,N+M-1); Y(K*N+1:K*N+M-1)=q(1:M-1)+t(1:M-1); Y(K*N+M:K*N+N)=q(M:N); t(1:M-1)=q(N+1:N+M-1);endY=Y(1:Lx+M-1);重疊保留法：結(jié)果與上述相同，程序如下：function Y=overlpsav(x,h,N)%N為分段長度；x為輸入長序列；h為短序列Lx=length(x);M=length(h);L=M+N-1; %分段后的總長度x=zeros(1,M-1),x,zeros(1