卷积的快速算法

1、数字信号处理课程设计报告卷积的快速算法专 业： 通信工程 班 级： 通信08-2BF 组 次： 第10组 姓 名： 卷积的快速算法一、 设计目的卷积运算是一种有别于其他运算的新型运算，是信号处理中一种常用的工具。随着信号与系统理论的研究的深入及计算机技术发展，卷积运算被广泛地运用到现代地震勘测，超声诊断，光学诊断，光学成像，系统辨识及其他诸多新处理领域中。了解并灵活运卷积运算用去解决问题，提高理论知识水平和动手能力，才是学习卷积运算的真正目的。通过这次课程设计，一方面加强对数字信号处理这门课程的理解和应用，另一方面体会到学校开这些大学课程的意义。二、设计任务探寻一种运算量更少，算法步骤更简单的

2、算法来实现卷积运算，文中主要通过阶梯函数卷积计算方法和斜体函数卷积计算方法对比来得出最终结论。三、设计原理1，什么是卷积？卷积是数字信号处理中经常用到的运算。其基本的表达式为：换而言之，假设两个信号f1(t)和f2(t)，两者做卷积运算定义为f(t)= -f1()f2(t-)d做一变量代换不难得出：f(t)= -f1()f2(t-)d=f1(t)*f2(t)=f2(t)*f1(t)在教材上，我们知道用图解法很容易理解卷积运算的过程，在此不在赘述。2，什么是阶梯函数 所谓阶梯函数，即是可以用阶梯函数u(t) 和u(t-1)的线性组合来表示的函数，可以看做是一些矩形脉冲的集合，图1-1给除了两个阶

3、梯函数的例子。 11其中f(t)=2u(t)+u(t-1)-2u（t-2）-u(t-3),h(t)= 2u(t)-u(t-1)+2u(t-2)-3u(t-3).以图11中两个阶梯函数为例介绍本文提出的阶梯函数卷积算法。根据卷积的性质（又称为杜阿美尔积分），上述f(t)与h(t)的卷积等于f(t)的导数与 h(t)的积分的卷积，即： f(t)*h(t)=df(t)dt*-thd.由于f(t)为阶梯函数，因此其导数也为冲击函数t及其延时的线性组合， 如图12（a）所示。 12由于h(t)也为阶梯函数，所以其积分-thd.也能方便地求得，其值为阶梯函数图像下方的面积，记作为H(t),如图12(b)所

4、示：冲击函数与其它函数的卷积有如下的关系：t-T*f(t)=f(t-T),因此 f(t)*h(t)=2H(t)+2H(t-1)-H(t-2)-H(t-3).即f(t)和(t)的卷积等于H(t)及其延时的线性组合，如图1-3所示： 13 从以上分析可以看到，两个阶梯函数的卷积等于其中一个函数的积分H(t)及其延迟H(t-)的线性组合，组合系数对应于各个冲击函数的系数。 对于任意函数的卷积，可以先将他们的用矩形脉冲函数来逼近只要时间间隔足够小就能达到足够的逼近精度。逼近所得到的函数即为阶梯函数，然后又采用上述方法即可得到任意两个函数的卷积。 假设要计算任意两个函数的卷积:y(t)=x(t)*h(t

5、)其中x(t),h(t)可谓无限长，分别如图14（a）,(b)所示。现将x(t)和h(t)在0到t的区间用宽度为的矩形脉冲来近似的代替（显然越小，逼近的精度越高，每一个矩形脉冲的高度分别等于该脉冲前沿的函数值。也就是说，用阶梯形曲线xn(t)近似地代替x(t)的曲线，用hn(t)近似的代替h(t)(如图14)。每一个矩形脉冲可用阶跃函数鄙视如下表21,22.表达式又可以写成如下形式：x(t)=m=0xm-xm-1ut-m, 12h(t)=n=0hn-hn-1ut-n, 13对式（2）求微分有：x(t)=m=0xm-xm-1t-m, 1-4设t=k,对3式求积分有：0thd=n=0k-1h(n)

6、 15令H(t)=0thd=H(k),则x't和Hk如图15a,b所示： 15 x(t),h(t)的微积分 16 x(t),h(t)的卷积过程由y(t)=x(t)*h(t)=x*H(t)得到Y(k)=n=0kxm-xm-1H(k-m) 16由图16(a)可以看出如果计算从t=0至t=k的N点的x(t)和h(t)的卷积，需要H(t)和x(t)对应的个点分别相乘，由于H(t)和x(t)也为N点序列，所以共需要N2次乘法，属于有效乘法，因为按照卷积定义直接计算也是N2次乘法。3，什么是斜梯函数？所谓斜梯函数，表现为一条折线的形式，用诸如at+b形式的段组合在一起表示的函数。图31给出了输入函

7、数为斜梯函数的例子。 31其中f(t)=tu(t)-u(t-1)+u(t-1)+(0.5t+0.5)u(t-1)-u(t-2)+(-1.5t+4.5)u(t-2)-u(t-3), h(t)=3tu(t)-u(t-1)+(-t+4)u(t-1)-u(t-2)+(-2t+6)u(t-2)-u(t-3)根据卷积的性质，上述f(t)和h(t)的卷积等于f(t)的二次导数与h(t)的二重积分的卷积【1】，即：由于f(t)为斜梯函数，因此其导数变为阶梯函数u(t)及其延时的线性组合，df(t)dt=u(t)-0.5u(t-1)-2u(t-2),如图32(a)所示。 32由于h(t)也为斜梯函数，所以其积分

8、-thd.也能方便的求得，其值为折现函数图象下方的面积，记作为h(-1)(t),如图32(b)所示。此时已经与阶梯函数卷积计算方法类似了，只是对于h(-1)(t)其为一二次曲线，继续求积分比较困难，实际应用中其可以用折现计算，从而引入一定的误差，这也是采用次逼近所付出的代价。接下来对f(t)和h(-1)(t)再次进行微分与积分处理，则f(t)变为冲击脉冲序列，如图33(a)所示，h(-2)(t)用对应折线下的买年纪也可算得对应如图33(b)所示。 33斜梯函数的二次微积分假设要计算任意函数的卷积：y(t)=x(t)*h(t)其中x(t),h(t)可谓无限长，分别如图34（a）,(b)所示。 3

9、4 连续时间函数 对上述x(t)和h(t),用宽度为的梯形脉冲函数逼近，x(t)和h(t)就转化为斜梯函数，顾客用折现函数及其延时的线性组合表示，如图34(a),(b)中虚线所示。x(t)=m=0x(m+1-x(m)t+c1u(t-m)-u(t-(m+1) ), 22h(t)= n=0h(n+1-h(n)t+c1u(t-n)-u(t-(n+1) ), 23此处c1,c2为常数，由于球x(t)和h(t)的微积分时，与此常数无关，所以此处可不必求出。对式子22，求微分有：x(t)= m=0x(m+1-x(m)t+c1u(t-m)-u(t-(m+1) ), 24设t=k,对23式求积分有：0thd=

10、n=0k-112hn+hn+1. 25则 x(t)和h(t)如图25(a),(b)所示: 35 斜梯函数的一次微分与积分X(t)=m=0xm+1+x(m-1)-2x(m)t-m 26H(-2)(t)=n=01422(n-1)h(0)+k=1n-14n-khk+h(n) 27式26,27如下图36所示。 36 斜梯函数的二次额积分令H(k)=h(-2)(t), 27 x(t)和h(t)的卷机过程由 y(t)=x(t)*h(t)=x(t)*H(t)得Y(k)=m=0kxm+1+xm-1-2xmH(k-m). 28由图27 可以清楚的看出如果计算从0到k的也为N点序列，所以共需要N2次乘法，属于有效

11、算法。四、设计过程 假设有有一DSP系统，如果激励信号的的波形如图41所示，定义的时间区间是(t0,t)，表示从t0到t之前的任意时刻。对于任意输入信号的作用，可以看成是一系列具有相同宽度的矩形脉冲用近似表示e().把时间区间(t0,t)分成相等的几段，每段宽度为，即t1-t0=t2-t1=tk+1-tk=.因此e()可以用图中的阶梯曲线来近似表示，即可以看成是一系列的矩形脉冲的合成。这一系列的矩形脉冲可以通过单位脉冲函数和延迟的单位脉冲函数，即P()和P(-k)来表示。因此可以用上述矩形脉冲表示e(),即e()=e(t0)P(- t0) +e(t1)P(- t1) + e(t2)P(- t2

12、) + e(tk)P(- tk) +e(tn-1)P(- tn-1) =k=0n-1e(tk)P(- tk) 2-9输入信号P()后，其响应为h()对每一延迟的矩形脉冲P(-tk),在时刻t观察到的相应的响应应为h(t-tk), e(tk)P(- tk) 的响应应该为e(tk)h(- tk) ,所以29式的输出信号应该为： r=k=0n-1e(t- tk) 为了保证e()的阶梯矩形近似更接近真实e()，令t0到t区间的脉冲数不断增加。当t时，0，每个单位矩形脉冲变成冲击函数，h变成了冲击函数h，e变成了原来的激励e()，响应rt则变成了对应原激励的响应rt,同时上式的求和也变成了积分，tk变成了连续变量，则变成了d,于是有 r(t)=t0tetkh(t-)d其中t0为任意激励施加的时刻，t为待求响应对应的时刻。特别的，当t0=0时，有 r(t)=t0tetkh(t-)d 210式子110所示的积分就是卷积的积分。因此，只要知道系统的冲击响应，对于任意的激励信号e(t)的作用，都可根据卷积的积分求出响应。对于更为复杂的二阶系统，运用这种方法更能看出其优势，由于计算过程大致类似，我们应用MATLAB自带的命令计算结果绘制于42图中 42 三种算法的比较 当采样精度为0