DSP实验报告重叠保留法和重叠相加法精

北京邮电大学实学班姓学日验报告MATLAB实现线性卷积运算院：信息与通信工程学院级：名：______号：期：实验名称：用索引一、实验原理.....................................................................................................................31、算法产生背景...........................................................................................................................32、算法基本思想...........................................................................................................................31）重叠相加法...........................................................................................................................32）重叠保存法...........................................................................................................................4二、流程图设计..................................................................................................................51、重叠相加法...............................................................................................................................52、重叠保存法...............................................................................................................................6三、MATLAB源代码............................................................................................................71、重叠相加源码...........................................................................................................................72、重叠保存源码...........................................................................................................................8四、实验成果与分析...........................................................................................................9①调用CONV(计算..........................................................................................................................9②测试重叠相加算法.....................................................................................................................9③测试重叠保存算法.....................................................................................................................9五、讨论与总结................................................................................................................101、算法效率分析：.....................................................................................................................10A.重叠相加法............................................................................................................................10B.重叠保存法............................................................................................................................11C.调用conv(.............................................................................................................................12D.综合对比分析........................................................................................................................132、故障和问题分析.....................................................................................................................14①分段问题...............................................................................................................................14②运算完整性问题....................................................................................................................14③算法硬件实现.......................................................................................................................14一、实验原理1、算法产生背景DFT是持续傅里叶变换在时域和频域上都离散的形式，将时域信号的采样变换为在离散时间傅里叶变换频域的采样。在形式上，变换两端（时域和频域上）的序列是有限长的。DFT含有明确且合理的物理含义，适合应用于数字系统，同时能够方便地由计算机进行运算。对于线性非移变离散系统，可由线性卷积表达时域输入输出关系，即y(nx(n*h(n普通采用循环卷积减少运算量，但实际中往往无法满足对信号解决的实时性规定。因此，产生了重叠相加法和重叠保存法两种典型的算法，用以快速计算线性卷积，成为了DFT的一种重要应用。2、算法基本思想1）重叠相加法重叠相加法是将待过滤的信号分割成长为N的若干段，如图1所示，每一段都能够和有限时宽单位取样响应作卷积，再将过滤后的各段重叠相加。具体算法实现原理如图2所示，建立缓存序列，每次输入N点序列，通过计算x(n和h(n的循环卷积实现线性卷积运算，将缓存的M-1点序列和卷积成果相加，并输出前N点作为计算成果，同时缓存后M-1点，如此循环，直至全部分段计算完毕，则输出序列y(n为最后计算成果。2）重叠保存法重叠保存法相称于将xl(n和h(n作循环卷积，然后找出循环卷积中相称于线性卷积的部分。在这种状况下，将序列y(n分为长为N的若干段(如图3所示，每个输入段和前一段有M-1个重叠点。此时只需要将发生重叠的前M-1个点舍去，保存重叠的部分并输出，则可获得序列y(n，算法如图4所示。二、流程图设计1、重叠相加法2、重叠保存法三、MATLAB源代码1、重叠相加源码2、重叠保存源码四、实验成果与分析对两种算法采用同一序列进行测试分析。设x(n=(n+1,0≤n≤9;ℎ(n=*−2,0,+2+。计算y(n=x(n∗h(n。①调用conv(计算首先运用Matlab对两序列直接运算，得出对的成果。代码为：x=*1:1:10+,h=*-2,0,+2+,conv(x,h成果为:*-2-4-4-4-4-4-4-4-4-41820+②测试重叠相加算法代码为：overlap_add(x,h,6成果为：*-2.0000-4.0000-4.0000-4.0000-4.0000-4.0000-4.0000-4.0000-4.0000-4.000018.000020.0000+③测试重叠保存算法代码为：overlap_save(x,h,4成果为：*-2.0000-4.0000-4.0000-4.0000-4.0000-4.0000-4.0000-4.0000-4.0000-4.000018.000020.0000+由此可见，两种算法运行正常，计算对的。更多的测试也对的。算法对的。五、讨论与总结1、算法效率分析：A.重叠相加法由上表和图1能够看出，随着数据规模增大，运算耗时呈线性增加，因而算法的时间复杂度为O(n，其中n为数据规模。因而重叠相加算法含有可行性和实用性。再从算法的空间复杂度来看，由于分派的缓存空间只由分段长度拟定，不随数据规模的变化而变化，因而空间复杂度为O(1。综合考察，重叠相加法含有较好的时间和空间复杂度。当数据量达成千万量级时，运算延时最少大概为2.328s，可运用于对信号的实时解决。MATLAB实验报告B.重叠保存法分段长度序列长度1010010001000010000010000001000000040.0005120.0010140.0092970.056740.5588655.22187952.2464100.0002250.0005140.0024020.0231940.2168182.14408922.022151000.0012490.0002720.0007870.0061220.0391750.3574283.59328210000.0008810.0008360.0006870.0039410.0260440.2362772.335725100000.0084540.0088020.0111070.0110830.0426430.3275393.251762图2.重叠保存法耗时与数据规模关系图605040运算耗时(s3020100-1.5-10序列长度Millions0.52.54.56.58.510.5从上至下,依次为:N=4,10,100,10000,1000由上表和图2能够看出,同重叠相加法类似,随着数据规模的增大,运算耗时呈线性增长,算法的时间复杂度为O(n,其中n为数据规模.同样由于分派的缓存空间只由分段长度拟定,空间复杂度为O(1.综合考察,重叠保存法也含有较好的时间和空间复杂度.当数据量达成千万量级时,运算延时最少大概为2.335s,可运用于对信号的实时解决.第11页MATLAB实验报告C.调用conv(序列长度运算耗时(s10100100010000100000100000010000000.0001130.0000810.0001170.0002750.0024920.0321550.32588图3.调用conv(函数耗时与数据规模关系图0.350.30.25运算耗时(s0.20.150.10.050-1.5-0.05序列长度Millions0.52.54.56.58.510.5由上表和图3能够看出,调用系统自带的线性卷积运算函数conv(计算线性卷积,运算时间和序列长度也有线性关系.时间复杂度为O(n.但此时的信号解决延时很小,当数据达成千万量级时,延时仅为0.325s,实时性非常好!第12页MATLAB实验报告D.综合对比分析分段长度4平均耗时(s重叠相加重叠保存调用conv(101001000100009.525278.2992430.051633.9834973.4870560.051630.6247690.5711880.051630.3767690.3720560.051630.5317580.5230560.05163图4.三种办法在不同分段长度下的耗时图9.52527103.9834978.299243运行耗时(对数坐标(s3.48705610.0010.010.6247690.10.5711880.3767691Thousands0.531758100.3720560.10.051630.051630.051630.051630.5230560.051630.01分段长度(对数坐标重叠相加重叠保存调用conv(重叠保存法和重叠相加法运行效率与分段长度有关性较强.分段数和卷积运算的序列长度为非线性关系,且当分段长度维持在大概1000点左右时,获得最高的平均运行效率.内置函数conv(运行效率与分段数无关.重叠相加和重叠保存两者效率几乎一致.在实际应用中,重叠保存和重叠相加重要用于实施信号解决,因而输入序列是持续输入,在确保明时性的规定下,输入序列的分段不能太长.构想实际状况以下:设语音信号采样率为8KHz,相称于每秒输入8000点序列,由重叠相加法解决(重叠保存法类似.如若分段为1000点,考虑实际系统中为实时输出(Matlab算法模拟里面是将全部序列保存之后再输出,因而每分段解决延时0.00406/8s,又接受1000点延时为1/8s,故解决总延时为0.1255075s.此时接受延时起重要作用,影响实时性.减小接受延时则需要减小分段点数,同时使得解决延时增加.接受延时和解决延时两者是不可调和的矛盾.实际处理时,可根据实时性规定,折中选择分段点数,既满足实时性规定,又减少系统开销.第13页MATLAB实验报告2