重叠保留法课程设计.doc

郑州轻工业学院课程设计说明书题目： 重叠保留法源程序设计 姓 名： 院 （系）： 计算机与通信工程学院 专业班级： 通信工程11-01 学 号： 指导教师： 杨永双 成 绩： 时间： 2013 年 12月 16 日至 2013 年 12月 20 日14郑州轻工业学院课 程 设 计 任 务 书题目 重叠保留法源程序设计 专业、班级 通信工程11-01 学号 姓名 主要内容： 1、编写重叠保留法源程序，不能使用matlab自带的函数 2、程序运行结果与matlab自带函数结果进行对比 3、完成符合学校要求的设计说明书基本要求： 1、小组讨论并完善重叠保留法的源程序 2、个人整理重叠保留法源程序设计的实验报告 完 成 期 限： 2013年12月18日 指导教师签名： 课程负责人签名： 2013 年 12 月 18 日重叠保留法源程序设计 摘要：重叠保留法在运用时，随着数据规模的增大，运算耗时呈线性增长。当数据达到千万量级时，运算延时最少大约为2.335s，由此可见，此方法可运用于对信号的实时处理，同时重叠保留法具有较好的时间和空间复杂度。本次课程设计以matlab为工具得到重叠保留法的源程序，通过对序列的线性卷积计算，进而对重叠保留法进行更深层次的认识。关键字：重叠保留法 序列线性卷积目录一、前言5二、重叠保留法原理5 1、背景 5 2、原理5三、设计6 1、设计思想6 2、流程图6 3、程序及结果7四、遇到问题及解决方法8五、总结9 1、算法效率分析9 2、体会9六、参考文献101、 前言 重叠保留法可运用于对信号的实时处理，具有较好的时间和空间复杂度。此次实验，使用matlb对重叠保留法进行源程序设计，通过对序列的线性卷积计算，我们可以对重叠保留法的优缺点进行更深刻的认识。二、重叠保留法原理1、背景 对于线性非移变离散系统，可由线性卷积表示时域输入输出关系，即 y(n)=x(n)*h(n) 线性卷积是求离散系统响应的主要方法之一，许多重要应用都建立在这一理论基础上，如卷积滤波等，但此方法适用于x(n)、h(n)两序列长度比较接近或相等的情况，如果x(n)、h(n)长度相差较多，按上述方法，h(n)要补许多零再进行计算，计算量有很大的浪费，或者根本不能实现。为了保持快速卷积法的优越性，可将x(n)分为许多段后处理，每小段的长与h(n)接近，其处理方法有两种：重叠相加法和重叠保留法。 通常采用循环卷积降低运算量，但实际中往往无法满足对信号处理的实时性要求。因此，产生了重叠相加法和重叠保留法两种典型的算法，用以快速计算线性积，成为了DFT的一个重要应用。2、原理 假定xi(n)表示图中第i段x(n)序列如下图： ，则输入序列可表为：于是输出可分解为： ，其中由此表明，只要将x(n)的每一段分别与h(n)卷积，然后再将这些卷积结果相加起来就可得到输出序列，这样，每一段的卷积都可用上面讨论的快速卷积来计算。先对h(n)及xi(n)保留原来的输入序列值，且保留在各段的前端，N=N1+N2-1，由于yi(n)长度为N，而xi(n)的长度为N2，因此相邻两yi(n)序列必然有N-N2=N1-1点发生重叠，这个重叠部分应该相加起来才能构成最后的输出序列。重叠保留法每一输入段均由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点。 重叠保留法每一输入段均由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=（510）N1，这样可接近于最高效的运算。3、 设计1、 设计思想 重叠保留法相当于将h(n)和xl(n)做循环卷积，然后找出循环卷积中相当于线性卷积的部分。在这种情况下，将序列y(n)分为唱为N的若干段，每个输入端和前一段有M-1个重叠点。此时只需要将发生重叠的钱M-1个点舍去，保留重叠部分并输出，则获得序列y(n)。M-1点缓存后N点x(n)后M-1个点N+M-点 循环卷积序列链接y(n)每N点输入h(n) 2、流程图 开始 输入序列X(n)，h(n) 计算各序列长度、分段数、生成临时序列 填入保留之后分段循环卷积 否输出前N 个点并为t(n)重新赋为保留值 完成所有分段 是计算？ 输出序列 y(n) 结束3、程序及结果 程序：function y = overlap_save( x, h, N ) %重叠保留法实现 %核心为将高点数DFT 转化为低点数DFT，且用循环卷积计算线性卷积 x=input(x=);h=input(h=);N=input(N=)Lx = length(x); %获得x(n)的长度 M = length(h); %获得h(n)的长度 if N M %为N 选择合适的值保证运算正确 N = M+1; end L = N+M-1; %为降低点数,取M+N-1 点循环卷积即可 t = zeros(1,M-1); %初始化序列t(n) T = ceil(Lx/N); %确定分段数 x = x,zeros(1, (T+1)*N-Lx); %为不足的分段补零 y = zeros(1, (T+1)*N); for i = 0:1:T xi = i*N+1; x_seg = t,x(xi:xi+N-1); %确定每个低点数卷积的分段x(n) t = x_seg(N+1:N+M-1); %为t(n)重新赋值为后M-1 个点的值 y_seg = circular_conv(x_seg,h,L); %循环卷积计算线性卷积 y(xi:xi+N-1) = y_seg(M:N+M-1); %直接取出后N 个点作为一次计算的输出 end y=y(1:Lx+M-1); %取出实际的输出序列 fprintf(结果n,y);输入： x=1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 h=1 0 2 N=5 N =5结果： ans =Columns 1 through 8 1.0000 2.0000 5.0000 8.0000 11.0000 9.0000 12.0000 5.0000 Columns 9 through 16 8.0000 11.0000 9.0000 12.0000 5.0000 8.0000 11.0000 8.0000Column 17 10.00004、 遇到问题及解决方法1、 程序中的分段补零不会，通过查资料后获得相关代码。2、 matlab刚开始不认识“ Lx = length(x)，M = length(h)”，通过设置“ x=input(x=)，h=input(h=)，N=input(N=)”形参即可。五、讨论与总结1、算法效率分析 重叠保留法运行效率与分段长度相关性较强。分段和卷积运算的序列 长度长度为非线性关系，且当分段长度维持在大约1000点左右时，获得最高的平均运行效率。内置函数conv()运行效率与分段数无关。 在实际应用中，重叠保留主要用于实施信号处理，因而输入序列是连续输入，在保证实时性的要求下，输入序列的分段不能太长。2、 心得体会 Matlab是一款功能强大且实用的软件，在这次的课程设计后，我对matlab有了更深刻的了解和掌握。通过在matlab上对线性卷积的调试，我逐渐发现，线性重叠法可实时输出处理过的分段序列，与直接线性卷积相比，实用性很强，需要的计算单元特别是系统缓存明显减少，同时也具有较好的时间和空间复杂度；与重叠相加法相比，重叠保留法省去了重叠相加法最后的相加运算。总而言之，重叠保留法在现实中的应用具有很好的优势。虽然此次课程设计中遇到了许许多多的问题，但是通过小组讨论解决这些问题后，我对自己不擅长的知识进行近一步的补充。在此次课程设计中，我们小组分工协作、互帮互助，最终完成了重叠保留法的源程序设计，结果无疑是令人兴奋的。通过这次课程设计以后，我不仅对重叠保留法有了更深入的了解，同时，我们小组的默契度也提高了，相信，在以后的课程设计中，我们小组对课题的完成率更高。6、 参考文献1、郑君里等编，信号与系统，北京：高等教育出版社，19812、丁玉梅，高西全编著，数字信号处理，西安：西安电子科技大学出版社，20083、杨永双等编，数字信号处理实验指导书，郑州：郑州轻工业学院，20074、李正周编著，MATLAB数字信号处理及应用，北京：清华大学出版社，2008 课程设计成绩评定表评定项目内 容满分评分总分学习态