Dsp-matlab实验
实验一：重叠相加法和重叠保留法的实现
设
计报告课题名称：
学生姓名：
级：班
班内序号：
学号：
2015/06/15 日期：
目录
一、实验原理·········································
二、Matlab源代码·································
运行结果Matlab三、····························
结果分析Matlab四、····································
五、遇到的难题与解决方法····························
参考文献·························································
一、实验原理
1、算法来源
DFT 是连续傅里叶变换在时域和频域上都离散的形式，将时域信号的采样变换为在离散时间傅里叶变换频域的采样。

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

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

对于线性非移变离散系统，可由线性卷积表示时域输入输出关系，即
x(n)*h(n)=y(n)
通常采用循环卷积降低运算量，但实际中往往无法满足对信号处理的实时性要求。

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

2、两种算法基本思想
1）重叠相加法
重叠相加法和重叠保留法的实质都是以逐段地方式通过循环卷积来完成线性卷积的计算。

将输入序列x（n）进行分段，每段长为N,且N≥M（M为有限长因果序列h（n）的长度），x（n）逐段
与h（n）进行循环卷积，在重叠保留法中需在x（n）序列首部加入长度为M-1的0序列。

在算法中，在获得N个点的输入后，进行N+M-1点循环卷积计算，之后输出N个点。

通过for循环逐段进行循环卷积，使用fft和ifft计算两个有限长序列的N点循环卷积结果。

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

每次输入N 点序列，通过计算x(n) 和h(n) 的循环卷积实现线性卷积运算，将缓存的M-1 点序列和卷积结果相加，并输出前N 点作为计算结果，同时缓存后M-1 点，如此循环，直至所为最终计算结果。

y(n)有分段计算完毕，则输出序列
）重叠保留法2然后找出循环卷积中相当于线性卷积的部分。

作循环卷积，??))重叠保留法相当于将x(??和h(??M-1每个输入段和前一段有所示3)，的若干段将序列在这种情况下，y(n)分为长为N(如图则可获得序个点舍去，M-1保留重叠的部分并输出，个重叠点。

此时只需要将发生重叠的前所示。

y(n)列，算法如图4
源代码Matlab二、．
1）重叠相加法
三、Matlab运行结果
由此可见，两种算法运行正常，计算正确。

更多的测试也正确。

算法正确。

结果分析四、Matlab。

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

再从算法的空间复杂度来看，由空间复杂度为O(1)
可以看出，同重叠相加法类似，随着数据规模的增大，运算耗时呈线性增长，算法的时为数据规模。

同样由于分配的缓存空间只由分段长度确定，空，其中n间复杂度为O(n)O(1)。

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

间复杂度为
M（n）长度为；yx(n)长度为N，
，所以每生成一Mn，y（）可视为N个序列的叠加结果，序列长度为）（计算线性卷积yn）N-1（个序列依次向右移动一位故需N这次乘法运算。

MN共需完成次乘法，M个序列需完成．（M-1）次加法运算。

按照fft和ifft计算线性卷积时，设L=N=M-1,整个运算过程包含了2个fft、一个ifft和L次乘法运算，所以，按基2频域抽选算法实现fft或ifft，共需完成(3Llog2L/2+L)次乘法和（3Llog2L）次加法运算。

五、遇到的难题与解决办法matlab软件安装问题，因为电脑环境的
特殊性尝试了多次才成功；最开始遇到的问题是熟悉实验在建模过程中发现对实验原理因为学习时间过长有些不熟悉，于是翻书查阅复习，原理；细心调试之没有打符号等等之类问题使系统开始报错，在实验过程中因为粗心，忘记保存，后成功建模
参考文献重叠保留法与重叠相加法》来自百度文库《dsp-《数字信号处理·第二版》科学出版社。