数字信号处理重叠保留法

1、武汉理工大学数字信号处理课程设计说明书课程设计任务书学生姓名： 专业班级： 指导教师： 黄朝兵 工作单位： 信息工程学院 题 目：基于重叠保留法圆周卷积的实现初始条件： 具备数字信号处理的理论知识；具备Matlab编程能力；分析重叠保留法的圆周卷积的原理；提供编程所需要的计算机一台要求完成的主要任务：（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）1、独立编写程序实现基于重叠保留法的圆周卷积2、用Matlab验证程序结果，并分析重叠保留法的圆周卷积的原理3、完成符合学校要求的设计说明书时间安排：一周，其中3天程序设计，2天程序调试指导教师签名： 年 月 日系主任（或责任教师）签名：

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为工具得到重叠保留法的源程序

3、，通过对序列的线性卷积计算，进而对重叠保留法进行更深层次的认识。关键字：重叠保留法 序列线性卷积 matlab1 概述对于一个长序列和一个短序列，长度分别为，圆周卷积的长度为，在长序列的前面加上个零，然后对长序列进行分段，使得每段的长度为不足的用零补。且前一分段的后个抽样值和后一分段的前个抽样值相同。这样形成的分段序列为：. (1.1)分成的段数为： (1.2)然后计算与各个分段之间的圆周卷积， (1.3)显然，的前个值发生了混叠，不等于和的圆周卷积，把的前个值舍去，保留没发生混叠的后个值，形成序列： (1.4)最后将各段相加就可以得到最终的结果， (1.5) 132 理论分析2.1

4、圆周卷积与线性卷积设和为长度为N的有限长序列，且，如果，则 (2.1.1)证明：相当于将作周期卷积和后，再取主值序列。 将周期延拓：则有： (2.1.2) 在主值区间 ，所以： (2.1.3)同样可以证明： (2.1.4)定义式（1）为序列与的圆周卷积，习惯表示为 (2.1.5)从以上的证明过程也可以得出圆周卷积与周期卷积之间的关系，即有限长序列圆周卷积结果的周期延拓等于它们周期延拓后的周期卷积。也就是说，周期卷积的主值序列是各周期序列主值序列的圆周卷积。线性卷积是求离散系统响应的主要方法之一，许多重要应用都建立在这一理论基础上，如卷积滤波等。用圆周卷积计算线性卷积的方法归纳如下: 将长为N2

5、的序列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)X(k) （ k=0L-1）   

6、0;    d.求y(n)=IFFTY(k) （n=0L-1 ）可见，只要进行二次FFT,一次IFFT就可完成线性卷积计算。上述结论适用于x(n)、h(n)两序列长度比较接近或相等的情况，如果x(n)、h(n)长度相差较多。例如，h(n)为某滤波器的单位脉冲响应,长度有限，用来处理一个很长的输入信号x(n)，或者处理一个连续不断的信号，按上述方法，h(n)要补许多零再进行计算，计算量有很大的浪费，或者根本不能实现。为了保持快速卷积法的优越性，可将x(n)分为许多段后处理，每小段的长与h(n)接近，其处理方法有两种：重叠相加法和重叠保留法。本文讨论重叠保留法。2.2

7、计算圆周卷积圆周卷积的具体步骤为：第一步：在哑元坐标上做与；第二步：把沿着纵坐标翻转，得到；第三步：对做圆周移位，得； 第四步：与对应的相同m的值进行相乘，并把结果进行相加，得到的对应于自变量n的一个；第五步：换另一个n，重复第三、四步，直到n取遍0,N-1中的所有值，得到完整的。2.3重叠保留法 为了克服重叠相加法中分段卷积后，仍然需要相加的缺点，人们提出了重叠保留法。这种方法和重叠相加法稍有不同，即将重叠相加法中补零的部分不是补零，而是保留原来的输入序列值，且保留在各段的前端，这时，如利用DFT实现h(n)和xi(n)的圆周卷积，则每段卷积结果的前N1-1个点不等于线性卷积值需舍去。 为了

8、清楚地看出这点，研究一下x(n)中一段长为N的序列xi(n)与h(n)（长为N1）的圆周卷积情况： (2.3.1)由于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），因此从n=N1-1点开始圆周圈卷积值完全与线性卷积值一样，yi(n)的后面N2点才是正确的卷积值，而每一段卷积运算结果的前N1-1点个值需去掉。图2.1 重叠保留过程为了不造成输出信号遗漏，对x(n)分段时，需使相

9、邻两段有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少做了

10、一次卷积，为此，因再补做这一段N1-1点，在其后填补N2点个零点保证长度仍为N点，一样舍去前取N1-1点，并从N1-1点开始，保留N1-1点。 重叠保留法与重叠相加法的计算量差不多，但省去了重叠相加法最后的相加运算。一般来说，用FFT作信号滤波，只用于FIR滤波器阶数h（n）大于32的情况下，且取N2=（510）N1，这样可接近于最高效的运算。 3 程序设计3.1程序流程要实现基于重叠保留法的圆周卷积，假设有两个长度分别为N,M（）的序列，要求做和的圆周卷积。首先要对长序列序列进行分段，分段的长度选圆周卷积的长度，形成的分段序列： (3.1.1)然后将逐一和各分段进行圆周卷积，得到：

11、 (3.1.2) 最后输出序列： (3.1.3)这样即完成了基于重叠保留法的圆周卷积的实现。同样，我们可以根据FFT计算线性卷积，方法如下：         a.计算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  可见，只要进行二次FFT,一次IFFT就可完成线性卷积计算。3.2程序流程图开始输入x(n),h(n),圆周卷积长度N计算x(n),h(n)长度及FFT变换长度x(n)序列前加M-1个0，若长度小于N，补0计算所需段数a，控制循环次数计算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个重叠点，保留M到L点K=a?将保留的点相连，可得y(n)结束图3-2 重叠保留法圆周卷积运算流程图3.3具体程序设计首先编写基于重叠

13、保留法的圆周卷积的主函数。这个主函数的功能应当是计算出两个序列的长度Lx、M，将长序列进行分段，然后再将短序列和长序列的各个分段分别进行圆周卷积，将分段卷积的的结果序列的前M-1个值舍去，将各个结果合并到一个序列中去，输出这个新序列，程序功能基本完成。主函数的编写过程如下：定义主函数：function Y=overlpsav(x,h,N)计算两个序列的长度：Lx=length(x);M=length(h);计算FFT运算序列长度： L=M+N-1;x序列前加M-1个0，序列后加N个0：x=zeros(1,M-1),x,zeros(1,N);求截取的段数：a=floor(Lx+M-1)/N);对

14、h做快速傅里叶变换：c=fft(h,L);设置for循环，截取x的某一段xk，对xk进行FFT变换，对Y(k)=X(k)*H(k)进行反傅里叶变换，截取前M-1点，保留其余点：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将所有保留的点相连：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 结果及分析假设有这样的两个序列，序列1为x=1,2,3,4,5,6,7,8,9，序列2为h=3,2要求这两个序列基于重叠保留法的的圆周卷积。显然第一个序列x的长度为9，第二个序列h的长度为2，在x序列的头部加上2-1个零，尾部加上N=3个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将每个分段与h卷积后的序列为：Y1=0,3,8,13Y2=9,18,23,28Y3=18,33,38,43Y4=27,18,0,0的前2-1个值舍去，再按顺序将序列合并，得到序列：Y=3,8,13,18,23,28,33,38,43,18以上的结果是根据计算所得到的结果。下面用程序来验证。运行程序在comand window中输入>> x=1,2,3,4,5,6,7,8,9;>> h=3,2;>> Y=overlpsav(x,h,3)得到的结果为：显然，计算结果和程序运行结果相同.

17、5 心得体会在本次课程设计中，让我知道了以前所学信号与系统与数字信号处理的结合，并在实际运用中设计滤波器的过程。课程设计不仅要求对滤波器理论的研究，更重要的是实际设计中遇到的问题。因为有了这次课程设计，我不得不对其设计原理进行更深一层次的理解，对书中原来学到的理论，仅知道了其表面，而不知其原因。在设计中也使我对一些概念有了更深刻的认识。例如：在指标方面，我混淆了模拟指标和数字指标的概念，经过老师的点拨，自己更加明确，而且记忆深刻。还有在课程设计中每一次的数据输入都有其重要意义，用MATLAB编译程序时，可以根据滤波器指标的要求实时知道对滤波器的影响。例如，编好程序后，调试成功，任意改变输入阻带

18、或者通带衰减，可以看到输出波形的变化，改变截止频率wc（带通和带阻滤波器为wcl wcu）同样可以看到输出波形的变化。由此，对理论的理解就更加简单方便，而且记忆力深刻。除此之外，对程序的编译不是一蹴而就的，而是经过多次的编译与调试。以前用MATLAB就是简单的输入，可以说都不是自己的劳动成果，但这次不一样，课程设计没有别人给你编好，而是自己写，出错率就大大提高了，但这是过程，学习就是在过程中进行的，经过自己几天的脑力劳动，再加上同学们的帮助，不仅对读程序有了很大提高，而且自己的编译水平也上了一个新台阶，更加熟系了MATLAB的应用，也对其中的函数有了大概的了解，对其中一些函数也相当熟练，abs（）、log、exp（）这些都很简单，滤波器设计中用到了ceil（）、freqz（）等很重要的函数，虽然可以用fir1（）、fir2（）可以直接调用，但那样就达不到对真正理论设计过程的 理解和运用。完成整个设计过程后，学到的东西已经不仅仅上面的那些东西，还有同组员的共同努力和探讨和设计过程中的每一个细节，也许每一个细节的错误就可能导致结局的失败，所以我认为这次收获最大的莫过于静心，学习不能急，一定要冷静，心无旁骛，不放过任何一个细节，就能带来凯旋的消息。在此，感谢老师一学年以来对我们不仅学习上的关心，还有生活中的照顾，我也不会辜负老师的期望，继续努力深造。参考文献