《重叠相加法和重叠保留法的原理与实现》由会员分享,可在线阅读,更多相关《重叠相加法和重叠保留法的原理与实现(4页珍藏版)》请在金锄头文库上搜索。
1、重叠相加法与重叠保存法的原理实现侯凯(吉林大学 通信工程学院 吉林 长春 130012)0概述线性卷积是求离散系统响应的主要方法之一,许多重要应用都建立在这一理论基础上,如卷积滤波等。用圆周卷积计算线性卷积的方法归纳如下: 将长为N2的序列x(n)延长到L,补L-N2个零,将长为N1的序列h(n)延长到L,补L-N1个零。如果LN1+N2-1,则圆周卷积与线性卷积相等,此时,可有FFT计算线性卷积,方法如下: a.计算X(k)=FFTx(n) b.求H(k)=FFTh(n) c.求Y(k)=H(k)Y(k) k=0L-1 d.求y(n)=IFFTY(k) n=0L-1 可见,只要进行二次FFT
2、,一次IFFT就可完成线性卷积计算。上述结论适用于x(n)、h(n)两序列长度比较接近或相等的情况,如果x(n)、h(n)长度相差较多。例如,h(n)为某滤波器的单位脉冲响应,长度有限,用来处理一个很长的输入信号x(n),或者处理一个连续不断的信号,按上述方法,h(n)要补许多零再进行计算,计算量有很大的浪费,或者根本不能实现。为了保持快速卷积法的优越性,可将x(n)分为许多段后处理,每小段的长与h(n)接近,其处理方法有两种:重叠相加法和重叠保留法。1重叠相加法由分段卷积的各段相加构成总的卷积输出假定xi(n)表示图中第i段x(n)序列如下图:则输入序列可表为: 图1 长序列分段滤波于是输出
3、可分解为: 其中 由此表明,只要将x(n)的每一段分别与h(n)卷积,然后再将这些卷积结果相加起来就可得到输出序列,这样,每一段的卷积都可用上面讨论的快速卷积来计算。先对h(n)及xi(n)补零,补到具有N点长度,N=N1+N2-1。 一般选择N=2M,然后用基2 FFT算法通过正反变换计算 由于yi(n)长度为N,而xi(n)的长度为N2,因此相邻两yi(n)序列必然有N-N2=N1-1点发生重叠,这个重叠部分应该相加起来才能构成最后的输出序列。 计算步骤: a. 事先准备好滤波器参数,N点 b.用N点FFT计算c.d.用N点IFFT求e.将重叠部分相加 图2 重叠相加法示意图2重叠保存法这
4、种方法和第一种方法稍有不同,即将上面分图序列中补零的部分不是补零,而是保留原来的输入序列值,且保留在各段的前端,这时,如利用DFT实现h(n)和xi(n)的圆周卷积,则每段卷积结果的前N1-1个点不等于线性卷积值需舍去。 为了清楚地看出这点,研究一下x(n)中一段长为N的序列xi(n)与h(n)(长为N1)的圆周卷积情况: 由于h(n)的长度为N1,当0nN1-2时,h(n-m)N将在xi(m)的尾部出现有非零值,所以0nN1-2这部分yi(n)值中将混入xi(m)尾部与h(n-m)N的卷积值,从而使yi(n)不同于线性卷积结果,但当n=N1-1N-1时,则有h(n-m)N =h(n-m),因
5、此从n=N1-1点开始圆周圈卷积值完全与线性卷积值一样,yi(n)的后面N2点才是正确的卷积值,而每一段卷积运算结果的前N1-1点个值需去掉。图2 重叠保留过程为了不造成输出信号遗漏,对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个点所组成。值得注意的是,对于有限长时间
6、序列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=(510)N1,这样可接近于最高效的运算。3应用举例例:已知有长序列X=1,2,3,4,
7、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,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)
8、;a=floor(Lx/N);y2=fft(h,N+M-1);for K=0:a %循环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);重叠保留法:结果与上述相同,程序如下: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,N);a=floor(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);endY=Y(1:Lx+M-1);