用MATLAB实现线性卷积运算-北邮学习资料.docx

信息与通信工程学院
数字信号处理实验报告

实验题目：用MATLAB实现线性卷积运算

班 级： 2008211113
姓 名：
学 号：
日 期： 2010年5月

索 引
一、实验原理 1
1、算法产生背景 1
2、算法基本思想 1
1）重叠相加法 1
2）重叠保留法 2
二、流程图设计 3
1、重叠相加法 3
2、重叠保留法 4
三、MATLAB源代码 5
1、重叠相加源码 5
2、重叠保留源码 6
四、实验结果与分析 7
①调用conv()计算 7
②测试重叠相加算法 7
③测试重叠保留算法 7
五、讨论与总结 8
1、算法效率分析： 8
A.重叠相加法 8
B.重叠保留法 10
C.调用conv() 11
D.综合对比分析 12
2、故障和问题分析 13
①分段问题 13
②运算完整性问题 13
③算法硬件实现 13

一、实验原理
1、算法产生背景
DFT是连续傅里叶变换在时域和频域上都离散的形式，将时域信号的采样变换为在离散时间傅里叶变换频域的采样。在形式上，变换两端（时域和频域上）的序列是有限长的。DFT具备明确且合理的物理含义，适合应用于数字系统，同时可以方便地由计算机进行运算。
对于线性非移变离散系统，可由线性卷积表示时域输入输出关系，即

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

0 N-1 N 2N-1 2N

图1. 重叠相加法的分段示意图

L点循环卷积
M-1点缓存
1

L=N+M-1
h(n)
前N点
后M-1点
y(n)
图2. 重叠相加法算法示意图

2）重叠保留法
重叠保留法相当于将xl(n)和h(n)作循环卷积，然后找出循环卷积中相当于线性卷积的部分。在这种情况下，将序列y(n)分为长为N的若干段(如图3所示)，每个输入段和前一段有M-1个重叠点 。此时只需要将发生重叠的前M-1个点舍去，保留重叠的部分并输出，则可获得序列y(n)，算法如图4所示。

0 N-1 N 2N-1 2N

图3. 重叠保留法的分段示意图

序列衔接
M-1点缓存

每N点输入
h(n)
y(n)
图4. 重叠保留法算法示意图
后M-1点
M+N-1点循环卷积
后N点

二、流程图设计
1、重叠相加法

2、重叠保留法

三、MATLAB源代码
1、重叠相加源码

function y = overlap_add(x,h,N)
%重叠相加法实现
%核心为将高点数DFT转化为低点数DFT，且用循环卷积计算线性卷积
M = length(h); %获得h(n)的长度
if N
T = ceil(Lx/N); %确定分段数T
t = zeros(1,M-1); %初始化序列t(n)
x = [x,zeros(1, (T+1)*N-Lx)]; %不足的分段补零
y = zeros(1, (T+1)*N); %生成输出序列y(n),长度足够长

for i=0:1:T
xi=i*N+1;
x_seg = x(xi:xi+N-1); %选择低点数计算时的分段x(n)
y_seg = circular_conv(x_seg,h,L); %调用循环卷积计算线性卷积
y_seg(1:M-1) = y_seg(1:M-1)+t(1:M-1);%完成重叠相加
t(1:M-1) = y_seg(N+1:L); %重新对t(n)赋值为保留的后M-1点
y(xi:xi+N-1) = y_seg(1:N); %直接输出前N个点
end
y=y(1:Lx+M-1); %取出最终的输出序列

function y = circular_conv( x1,x2,L)
% 利用循环卷积计算线性卷积
% 循环卷积采用频域计算方法,已FFT代替DFT,降低运算量

X1k = fft(x1,L); %x1做L点FFT
X2k = fft(x2,L); %x1做L点FFT
Yk = X1k.*X2k; %频域相乘
y = ifft(Yk); %FFT反变换得循环卷积结果

2、重叠保留源码

function y = overlap_save(x,h,N)
%重叠保留法实现
%核心为将高点数DFT转化为低点数DFT，且用循环卷积计算线性卷积
Lx = length(x); %获得xn)的长度
M = length(h); %获得h(n)的长度
if N = 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); %取出实际的输出序

四、实验结果与分析

对两种算法采用同一序列进行测试分析。
设xn=n+1,0≤n≤9;hn={-2,0,+2} 。计算yn=xn*h(n) 。

①调用conv()计算
首先利用Matlab对两序列直接运算，得出正确结果。
代码为：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.0000 -4.0000 -4.0000 -4.0000 -4.0000 18.0000 20.0000 ]

由此可见，两种算法运行正常，计算正确。更多的测试也正确。算法正确。

五、讨论与总结
1、算法效率分析：
A.重叠相加法

分段长度
序列长度
4
10
100
1000
10000
10
0.013151
0.000266
0.018963
0.027378
0.074834
100
0.001173
0.000605
0.000319
0.000917
0.010007
1000
0.009936
0.002824
0.00092
0.000746
0.013927
10000

0.074181
0.027121
0.006682
0.00406
0.009922
100000
0.606933
0.265476
0.052852
0.030106
0.048245
1000000
6.033528
2.483526
0.396206
0.246052
0.33387
10000000
59.93776
25.10466
3.897444
2.328122
3.231499

由上表和图1可以看出，随着数据规模增大，运算耗时呈线性增长，因而算法的时间复杂度为O(n)，其中n为数据规模。因而重叠相加算法具有可行性和实用性。再从算法的空间复杂度来看，由于分配的缓存空间只由分段长度确定，不随数据规模的变化而变化，因而空间复杂度为O(1)。综合考察，重叠相加法具有较好的时间和空间复杂度。当数据量达到千万量级时，运算延时最少大约为2.328s，可运用于对信号的实时处理。
B.重叠保留法

分段长度
序列长度
4
10
100
1000
10000
10
0.000512
0.000225
0.001249
0.000881
0.008454
100
0.001014
0.000514
0.000272
0.000836
0.008802
1000
0.009297
0.002402
0.000787
0.000687
0.011107
10000
0.05674
0.023194
0.006122
0.003941
0.011083
100000
0.558865
0.216818
0.039175
0.026044
0.042643
1000000
5.221879
2.144089
0.357428
0.236277
0.327539
10000000
52.2464
22.02215
3.593282
2.335725
3.251762

由上表和图2可以看出，同重叠相加法类似，随着数据规模的增大，运算耗时呈线性增长，算法的时间复杂度为O(n)，其中n为数据规模。同样由于分配的缓存空间只由分段长度确定，空间复杂度为O(1)。综合考察，重叠保留法也具有较好的时间和空间复杂度。当数据量达到千万量级时，运算延时最少大约为2.335s，可运用于对信号的实时处理。

C.调用conv()

序列长度
10
100
1000
10000
100000
1000000
1000000
运算耗时(s)
0.000113
0.000081
0.000117
0.000275
0.002492
0.032155
0.32588

由上表和图3可以看出，调用系统自带的线性卷积运算函数conv()计算线性卷积，运算时间和序列长度也有线性关系。时间复杂度为O(n)。但此时的信号处理延时很小，当数据达到千万量级时，延时仅为0.325s，实时性非常好！

D.综合对比分析

分段长度

平均耗时(s)
4
10
100
1000
10000
重叠相加
9.52527

3.983497
0.624769
0.376769
0.531758
重叠保留
8.299243
3.487056
0.571188
0.372056
0.523056
调用conv()
0.05163
0.05163
0.05163
0.05163
0.05163

重叠保留法和重叠相加法运行效率与分段长度相关性较强。分段数和卷积运算的序列长度为非线性关系，且当分段长度维持在大约1000点左右时，获得最高的平均运行效率。内置函数conv()运行效率与分段数无关。重叠相加和重叠保留两者效率几乎一致。
在实际应用中，重叠保留和重叠相加主要用于实施信号处理，因而输入序列是连续输入，在保证实时性的要求下，输入序列的分段不能太长。设想实际情况如下：设语音信号采样率为8KHz，相当于每秒输入8000点序列，由重叠相加法处理(重叠保留法类似)。如若分段为1000点，考虑实际系统中为实时输出（Matlab算法模拟里面是将所有序列保存之后再输出），因而每分段处理延时0.00406/8s，又接收1000点延时为1/8s，故处理总延时为0.1255075s。此时接收延时起主要作用，影响实时性。减小接收延时则需要减小分段点数，同时使得处理延时增加。接收延时和处理延时两者是不可调和的矛盾。实际处理时，可根据实时性要求，折中选择分段点数，既满足实时性要求，又降低系统开销。
2、故障和问题分析
①分段问题
初始时没有考虑到分段长度的限制，导致用户输入分段小于系统冲击响应h(n)的长度时运算出错。后增加一个判断语句，当出现前述情况时，自动提升分段点数，问题解决。
②运算完整性问题
在写好代码之后的测试中，出现了一个十分奇怪的现象，即：当输入点数为1000、10000或者更大时卷积运算最后M-1个结果为0。反复测试发现，不仅1000和10000，只要是分段数N的倍数的输入点数都存在同样问题，而其他非倍数的输入，运算与conv() 函数运算结果完全一致。通过设置断点，逐句调试，最终发现问题的症结，当输入序列为N的倍数时，最后的一段卷积实际上没有做。因而将循环次数增加1，将最后一次保留的M-1个点补全N个0，做最后一次分段卷积。修改后，测试结果正确。
③算法硬件实现
第一，重叠保留和重叠相加算法在硬件实现时将算法中的临时变量都化为缓存，所以考虑缓存的大小限制，不能将输入序列分段过长，否则所需的缓存将加大，成本加大。
第二，接收延时和处理延时两者存在矛盾，减少分段长度，可减少接收延时但会增加处理延时，同理，增大分段长度，可减少处理延时，但将增加接收延时。具体实现时需要综合考虑两者的作用，去最优化值。
第三，算法实际实现时，可实时输出处理过的分段序列，与直接线性卷积相比，实时性大大增强，需要的计算单元特别是系统缓存明显减少。因而实用性很强。
第四，<报告结束>
分段卷积能灵活计算长输入序列对IIR滤波器的响应，且延时较小，因而很常用。从硬件实现角度讲，重叠保留和重叠相加法效率几乎一致。
第五，测试算法性能时采用较短的h(n)序列，主要考虑到分段卷积应用在单位冲击响应较短的IIR滤波器。