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

1、北京邮电大学实学 班 姓 学日 验 报 告MATLAB 实现线性卷积运算院： 信息与通信工程学院 级：名： _号：期：实验名称：用索 引一、实验原理 . 3 1、算法产生背景 .3 2、算法基本思想 .3 1）重叠相加法 .3 2）重叠保留法 .4 二、流程图设计 . . 5 1、重叠相加法 . . 5 2、重叠保留法 . . 6 三、MATLAB 源代码 . . 7 1、重叠相加源码 .7 2、重叠保留源码 .8 四、实验结果与分析 . 9 调用CONV (计算 . . 9 测试重叠相加算法 .9 测试重叠保留算法 .9 五、讨论与总结 . . 10 1、算法效率分析： .10 A. 重叠相

2、加法 . . 10 B. 重叠保留法 . . 11 C. 调用conv( .12 D. 综合对比分析 . . 13 2、故障和问题分析 .14分段问题 . . 14 运算完整性问题. 14 算法硬件实现 .14一、实验原理1、算法产生背景DFT 是连续傅里叶变换在时域和频域上都离散的形式，将时域信号的采样变换为在离散时间傅里叶变换频域的采样。在形式上，变换两端（时域和频域上）的序列是有限长的。DFT 具备明确且合理的物理含义，适合应用于数字系统，同时可以方便地由计算机进行运算。对于线性非移变离散系统，可由线性卷积表示时域输入输出关系，即y (n x (n *h (n 通常采用循环卷积降低运算量

3、，但实际中往往无法满足对信号处理的实时性要求。因此，产生了重叠相加法和重叠保留法两种典型的算法，用以快速计算线性卷积，成为了DFT 的一个重要应用。2、算法基本思想1）重叠相加法重叠相加法是将待过滤的信号分割成长为N 的若干段，如图1所示，每一段都可以和有限时宽单位取样响应作卷积，再将过滤后的各段重叠相加。具体算法实现原理如图2所示，建立缓存序列，每次输入N 点序列，通过计算x(n和h(n 的循环卷积实现线性卷积运算，将缓存的M -1点序列和卷积结果相加，并输出前N 点作为计算结果，同时缓存后M -1点，如此循环，直至所有分段计算完毕，则输出序列y(n为最终计算结果。 2）重叠保留法重叠保留法

4、相当于将x l(n和h(n作循环卷积，然后找出循环卷积中相当于线性卷积的部分。在这种情况下，将序列y(n分为长为N 的若干段(如图3所示 ，每个输入段和前一段有M -1个重叠点 。此时只需要将发生重叠的前M -1个点舍去，保留重叠的部分并输出，则可获得序列y(n，算法如图4所示。 二、流程图设计1、重叠相加法 2、重叠保留法 三、MATLAB 源代码 1、重叠相加源码 2、重叠保留源码四、实验结果与分析对两种算法采用同一序列进行测试分析。设x(n =(n+1 , 0n9; (n =*2,0,+2+ 。计算y (n =x (n h(n 。调用conv(计算首先利用Matlab 对两序列直接运算，

5、得出正确结果。 代码为：x=*1:1:10+,h=*-2,0,+2+,conv(x,h结果为: * -2 -4 -4 -4 -4 -4 -4 -4 -4 -4 18 20 +测试重叠相加算法代码为：overlap_add(x,h,6结果为：* -2.0000 -4.0000 -4.0000 -4.0000 -4.0000 -4.0000 -4.0000 -4.0000-4.0000 -4.0000 18.0000 20.0000 +测试重叠保留算法代码为：overlap_save(x,h,4结果为：* -2.0000 -4.0000 -4.0000 -4.0000 -4.0000 -4.000

6、0 -4.0000 -4.0000-4.0000 -4.0000 18.0000 20.0000 +由此可见，两种算法运行正常，计算正确。更多的测试也正确。算法正确。五、讨论与总结1、算法效率分析：A. 重叠相加法 由上表和图1可以看出，随着数据规模增大，运算耗时呈线性增长，因而算法的时间复杂度为O(n，其中n 为数据规模。因而重叠相加算法具有可行性和实用性。再从算法的空间复杂度来看，由于分配的缓存空间只由分段长度确定，不随数据规模的变化而变化，因而空间复杂度为O(1。综合考察，重叠相加法具有较好的时间和空间复杂度。当数据量达到千万量级时，运算延时最少大约为2.328s ，可运用于对信号的实时

7、处理。MATLAB 实验报告 B.重叠保留法 分段长度 序列长度 10 100 1000 10000 4 0. 0. 0. 0.05674 0. 5. 52.2464 10 0. 0. 0. 0. 0. 2. 22.02215 100 0. 0. 0. 0. 0. 0. 3. 1000 0. 0. 0. 0. 0. 0. 2. 10000 0. 0. 0. 0. 0. 0. 3. 图2.重叠保留法耗时与数据规模关系图 60 50 40 运 算 耗 时 (s 30 20 10 0 -1.5 -10 序列长度 Millions 0.5 2.5 4.5 6.5 8.5 10.5 从上至下,依次为:N

8、=4,10,100,10000,1000 由上表和图 2 可以看出,同重叠相加法类似,随着数据规模的增大,运算耗时呈线性增 长,算法的时间复杂度为 O(n,其中 n 为数据规模.同样由于分配的缓存空间只由分段长度 确定,空间复杂度为 O(1.综合考察,重叠保留法也具有较好的时间和空间复杂度.当数据 量达到千万量级时,运算延时最少大约为 2.335s,可运用于对信号的实时处理. 第 11 页 MATLAB 实验报告 C.调用 conv( 序列长度 运算耗时 (s 10 100 1000 10000 0. 0. 0. 0. 0. 0. 0.32588 图3.调用conv(函数耗时与数据规模关系图

9、0.35 0.3 0.25 运 算 耗 时 (s 0.2 0.15 0.1 0.05 0 -1.5 -0.05 序列长度 Millions 0.5 2.5 4.5 6.5 8.5 10.5 由上表和图 3 可以看出,调用系统自带的线性卷积运算函数 conv(计算线性卷积,运 算时间和序列长度也有线性关系.时间复杂度为 O(n.但此时的信号处理延时很小,当 数据达到千万量级时,延时仅为 0.325s,实时性非常好! 第 12 页 MATLAB 实验报告 D.综合对比分析 分段长度 4 平均耗时(s 重叠相加 重叠保留 调用 conv( 10 100 1000 10000 9.52527 8. 0

10、.05163 3. 3. 0.05163 0. 0. 0.05163 0. 0. 0.05163 0. 0. 0.05163 图4.三种方法在不同分段长度下的耗时图 9.52527 10 3. 8. 运行耗时(对数坐标 (s 3. 1 0.001 0.01 0. 0.1 0. 0. 1 Thousands 0. 10 0. 0.1 0.05163 0.05163 0.05163 0.05163 0. 0.05163 0.01 分段长度(对数坐标 重叠相加 重叠保留 调用conv( 重叠保留法和重叠相加法运行效率与分段长度相关性较强.分段数和卷积运算的序 列长度为非线性关系,且当分段长度维持在大

11、约 1000 点左右时,获得最高的平均运行效 率.内置函数 conv(运行效率与分段数无关.重叠相加和重叠保留两者效率几乎一致. 在实际应用中,重叠保留和重叠相加主要用于实施信号处理,因而输入序列是连续输入, 在保证实时性的要求下,输入序列的分段不能太长.设想实际情况如下:设语音信号采 样率为 8KHz,相当于每秒输入 8000 点序列,由重叠相加法处理(重叠保留法类似.如若 分段为 1000 点,考虑实际系统中为实时输出(Matlab 算法模拟里面是将所有序列保存之 后再输出 ,因而每分段处理延时 0.00406/8s,又接收 1000 点延时为 1/8s,故处理总延 时为 0.s.此时接收

12、延时起主要作用,影响实时性.减小接收延时则需要减小分 段点数,同时使得处理延时增加.接收延时和处理延时两者是不可调和的矛盾.实际处 理时,可根据实时性要求,折中选择分段点数,既满足实时性要求,又降低系统开销. 第 13 页 MATLAB 实验报告 2,故障和问题分析 分段问题 初始时没有考虑到分段长度的限制,导致用户输入分段小于系统冲击响应 h(n的长 度时运算出错.后增加一个判断语句,当出现前述情况时,自动提升分段点数,问题解 决. 运算完整性问题 在写好代码之后的测试中,出现了一个十分奇怪的现象,即:当输入点数为 1000, 10000 或者更大时卷积运算最后 M-1 个结果为 0.反复测

13、试发现,不仅 1000 和 10000,只 要是分段数 N 的倍数的输入点数都存在同样问题,而其他非倍数的输入,运算与 conv( 函数运算结果完全一致.通过设置断点,逐句调试,最终发现问题的症结,当输入序列 为 N 的倍数时,最后的一段卷积实际上没有做.因而将循环次数增加 1,将最后一次保 留的 M-1 个点补全 N 个 0,做最后一次分段卷积.修改后,测试结果正确. 算法硬件实现 第一,重叠保留和重叠相加算法在硬件实现时将算法中的临时变量都化为缓存,所 以考虑缓存的大小限制,不能将输入序列分段过长,否则所需的缓存将加大,成本加大. 第二,接收延时和处理延时两者存在矛盾,减少分段长度,可减少接收延时但会增 加处理延时,同理,增大分段长度,可减少处理延时,但将增加接收延时.具体实现时 需要综合考虑两者的作用,去最