#用MATLAB实现线性卷积运算.docx

#用MATLAB实现线性卷积运算.docx

《#用MATLAB实现线性卷积运算.docx》由会员分享，可在线阅读，更多相关《#用MATLAB实现线性卷积运算.docx（14页珍藏版）》请在冰点文库上搜索。

#用MATLAB实现线性卷积运算

北京邮电大学

实验报告

实验名称：

用MATLAB实现线性卷积运算

学院：

信息与通信项目学院

班级：

姓名：

学号：

日期：

2018年5月

一、实验原理

1、算法产生背景

DFT是连续傅里叶变换在时域和频域上都离散的形式，将时域信号的采样变换为在离散时间傅里叶变换频域的采样。

在形式上，变换两端<时域和频域上）的序列是有限长的。

DFT具备明确且合理的物理含义，适合应用于数字系统，同时可以方便地由计算机进行运算。

对于线性非移变离散系统，可由线性卷积表示时域输入输出关系，即

（>（>*（>ynxnhn

通常采用循环卷积降低运算量，但实际中往往无法满足对信号处理的实时性要求。

因此，产生了重叠相加法和重叠保留法两种典型的算法，用以快速计算线性卷积，成为了DFT的一个重要应用。

2、算法基本思想

1）重叠相加法

重叠相加法是将待过滤的信号分割成长为N的若干段，如图1所示，每一段都可以和有限时宽单位取样响应作卷积，再将过滤后的各段重叠相加。

具体算法实现原理如图2所示，建立缓存序列，每次输入N点序列，通过计算x（n>和h（n>的循环卷积实现线性卷积运算，将缓存的M-1点序列和卷积结果相加，并输出前N点作为计算结果，同时缓存后M-1点，如此循环，直至所有分段计算完毕，则输出序列y（n>为最终计算结果。

2）重叠保留法

重叠保留法相当于将x�l（n>和h（�n>作循环卷积，然后找出循环卷积中相当于线性卷积的部分。

在这种情况下，将序列y（n>分为长为N的若干段（如图3所示>，每个输入段和前一段有M-1个重叠点。

此时只需要将发生重叠的前M-1个点舍去，保留重叠的部分并输出，则可获得序列y（n>，算法如图4所示。

二、流程图设计

1、重叠相加法

2、重叠保留法

三、MATLAB源代码

1、重叠相加源码

2.重叠保留源码

2、四、实验结果与分析

对两种算法采用同一序列进行测试分析。

设�56421.（�56411.>=（�56411.+1>,0≤�56411.≤9。

ℎ�56411.>=*−,0,+2+。

计算y（n>=x（n>∗（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.重叠相加法耗时与数据规模关系图

从上至下，依次为：

N=4,10,100,10000,1000

五、讨论与总结

1、算法效率分析：

由上表和图1可以看出，随着数据规模增大，运算耗时呈线性增长，因而算法的时间复杂度为O（n>，其中n为数据规模。

因而重叠相加算法具有可行性和实用性。

再从算法的空间复杂度来看，因为分配的缓存空间只由分段长度确定，不随数据规模的变化而变化，因而空间复杂度为O（1>。

综合考察，重叠相加法具有较好的时间和空间复杂度。

当数据量达到千万量级时，运算延时最少大约为2.328s，可运用于对信号的实时处理。

由上表和图2可以看出，同重叠相加法类似，随着数据规模的增大，运算耗时呈线性增长，算法的时间复杂度为O（n>，其中n为数据规模。

同样因为分配的缓存空间只由分段长度确定，空间复杂度为O（1>。

综合考察，重叠保留法也具有较好的时间和空间复杂度。

当数据量达到千万量级时，运算延时最少大约为2.335s，可运用于对信号的实时处理。

由上表和图3可以看出，调用系统自带的线性卷积运算函数conv（>计算线性卷积，运算时间和序列长度也有线性关系。

时间复杂度为O（n>。

但此时的信号处理延时很小，当数据达到千万量级时，延时仅为0.325s，实时性非常好！

重叠保留法和重叠相加法运行效率与分段长度相关性较强。

分段数和卷积运算的序列长度为非线性关系，且当分段长度维持在大约1000点左右时，获得最高的平均运行效率。

内置函数conv（>运行效率与分段数无关。

重叠相加和重叠保留两者效率几乎一致。

在实际应用中，重叠保留和重叠相加主要用于实行信号处理，因而输入序列是连续输入，在保证实时性的要求下，输入序列的分段不能太长。

设想实际情况如下：

设语音信号采样率为8KHz，相当于每秒输入8000点序列，由重叠相加法处理（重叠保留法类似>。

如若分段为1000点，考虑实际系统中为实时输出

此时接收延时起主要作用，影响实时性。

减小接收延时则需要减小分段点数，同时使得处理延时增加。

接收延时和处理延时两者是不可调和的矛盾。

实际处理时，可根据实时性要求，折中选择分段点数，既满足实时性要求，又降低系统开销。

2、故障和问题分析

①分段问题

初始时没有考虑到分段长度的限制，导致用户输入分段小于系统冲击响应h（n>的长度时运算出错。

后增加一个判断语句，当出现前述情况时，自动提升分段点数，问题解决。

②运算完整性问题

在写好代码之后的测试中，出现了一个十分奇怪的现象，即：

当输入点数为1000、10000或者更大时卷积运算最后M-1个结果为0.反复测试发现，不仅1000和10000，只要是分段数N的倍数的输入点数都存在同样问题，而其他非倍数的输入，运算与conv（>函数运算结果完全一致。

通过设置断点，逐句调试，最终发现问题的症结，当输入序列为N的倍数时，最后的一段卷积实际上没有做。

因而将循环次数增加1，将最后一次保留的M-1个点补全N个0，做最后一次分段卷积。

修改后，测试结果正确。

③算法硬件实现

第一，重叠保留和重叠相加算法在硬件实现时将算法中的临时变量都化为缓存，所以考虑缓存的大小限制，不能将输入序列分段过长，否则所需的缓存将加大，成本加大。

第二，接收延时和处理延时两者存在矛盾，减少分段长度，可减少接收延时但会增加处理延时，同理，增大分段长度，可减少处理延时，但将增加接收延时。

具体实现时需要综合考虑两者的作用，去最优化值。

第三，算法实际实现时，可实时输出处理过的分段序列，与直接线性卷积相比，实时性大大增强，需要的计算单元特别是系统缓存明显减少。

因而实用性很强。

第四，分段卷积能灵活计算长输入序列对IIR滤波器的响应，且延时较小，因而很常用。

从硬件实现角度讲，重叠保留和重叠相加法效率几乎一致。

第五，测试算法性能时采用较短的h（n>序列，主要考虑到分段卷积应用在单位冲击响应较短的IIR滤波器。

申明：

所有资料为本人收集整理，仅限个人学习使用，勿做商业用途。