卷积的快速算法++选编.docx

《数字信号处理》课程设计报告卷积的快速算法专业：通信工程班级：通信08-2BF 组次：第10组姓名：学号：14082300925 卷积的快速算法设计目的卷积运算是一种有别于其他运算的新型运算，是信号处理中一种常用的工具。随着信号与系统理论的研究的深入及计算机技术发展，卷积运算被广泛地运用到现代地震勘测，超声诊断，光学诊断，光学成像，系统辨识及其他诸多新处理领域中。了解并灵活运卷积运算用去解决问题，提高理论知识水平和动手能力，才是学习卷积运算的真正目的。通过这次课程设计，一方面加强对《数字信号处理》这门课程的理解和应用，另一方面体会到学校开这些大学课程的意义。二、设计任务探寻一种运算量更少，算法步骤更简单的算法来实现卷积运算，文中主要通过阶梯函数卷积计算方法和斜体函数卷积计算方法对比来得出最终结论。三、设计原理1，什么是卷积？卷积是数字信号处理中经常用到的运算。其基本的表达式为：换而言之，假设两个信号f1(t)和f2(t)，两者做卷积运算定义为f(t)d做一变量代换不难得出：f(t)d=f1(t)*f2(t)=f2(t)*f1(t)在教材上，我们知道用图解法很容易理解卷积运算的过程，在此不在赘述。2，什么是阶梯函数所谓阶梯函数，即是可以用阶梯函数u(t)和u(t-1)的线性组合来表示的函数，可以看做是一些矩形脉冲的集合，图1-1给除了两个阶梯函数的例子。 1—1其中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).以图1—1中两个阶梯函数为例介绍本文提出的阶梯函数卷积算法。根据卷积的性质（又称为杜阿美尔积分），上述f(t)与h(t)的卷积等于f(t)的导数与 h(t)的积分的卷积，即： f(t)*h(t)=*由于f(t)为阶梯函数，因此其导数也为冲击函数及其延时的线性组合，如图1—2（a）所示。 1—2由于h(t)也为阶梯函数，所以其积分也能方便地求得，其值为阶梯函数图像下方的面积，记作为H(t),如图1—2(b)所示：冲击函数与其它函数的卷积有如下的关系：*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所示： 1—3从以上分析可以看到，两个阶梯函数的卷积等于其中一个函数的积分H(t)及其延迟H(t)的线性组合，组合系数对应于各个冲击函数的系数。对于任意函数的卷积，可以先将他们的用矩形脉冲函数来逼近只要时间间隔足够小就能达到足够的逼近精度。逼近所得到的函数即为阶梯函数，然后又采用上述方法即可得到任意两个函数的卷积。 假设要计算任意两个函数的卷积:y(t)=x(t)*h(t)其中x(t),h(t)可谓无限长，分别如图1—4（a）,(b)所示。现将x(t)和h(t)在0到t的区间用宽度为的矩形脉冲来近似的代替（显然值。也就是说，用阶梯形曲线xn(t)近似地代替x(t)的曲线，用hn(t)近似的代替h(t)(如图1—4)。每一个矩形脉冲可用阶跃函数鄙视如下表2—1,2—2.表达式又可以写成如下形式：x(t)= 1—2h(t)= 1—3对式（2）求微分有：x(t)= 1--4设t=k 1—5令H(t)= 1—5 x(t),h(t)的微积分 1—6 x(t),h(t)的卷积过程由y(t)=x(t)*h(t)=x’*H(t)得到Y(k)= 1—6由图1—6(a)可以看出如果计算从t=0至t=k的N点的x(t)和h(t)的卷积，需要H(t)和x’(t)对应的个点分别相乘，由于H(t)和x’(t)也为N点序列，所以共需要N2次乘法，属于有效乘法，因为按照卷积定义直接计算也是N2次乘法。3，什么是斜梯函数？所谓斜梯函数，表现为一条折线的形式，用诸如at+b形式的段组合在一起表示的函数。图3—1给出了输入函数为斜梯函数的例子。 3—1其中f(t)=t[u(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)=3t[u(t)-u(t-1)+(-t+4)[u(t-1)-u(t-2)]+(-