有限长序列卷积和求解法

第30 卷 第 1 期 2008 年 2 月 电气电子教学学报 JOURNAL OF EEE Vol. 30 No. 1 Feb. 2008 有限长序列卷积和求解法 李昌利 ( 广东海洋大学 信息学院, 广东 湛江 524088) 收稿日期: 2007 -08 -05; 修回日期: 2007 - 08 -06 作者简介: 李昌利( 1976 - ) , 男, 硕士, 讲师, 主要从事信号处理的研究和教学工作, E -mail: charlee. li gmail. com 摘 要: 有很多简单而直观的方法计算有限长序列的卷积和, 但国内一些教材对此缺乏系统介绍。个别教材仅介绍了一种方法, 且含糊不清, 不便于教师讲授和学生自学。本文简洁地介绍了四种方法, 其中包括笔作者提出的序号和匹配法。 关键词: 信号与系统; 卷积和; 列求和法; 游带法; 序号和匹配法; 多项式表示法 中图分类号: T N911. 7 文献标识码: A 文章编号: 1008 -0686( 2008) 01 -0045 -03 Methods for Calculating Two Finitely Long Series LI Chang -li (School of Inf ormation Engineering, Guangdong Ocean University , Zhanjiang 524088, China) Abstract:A few simple and intuitionistic methods can be used to calculate two finitely long series, but there are no any systemic introduction to them in some domestic textbooks. A few textbooks invovle one method but it is indistinctly discussed , so it is difficult for teachers to illustrate and for students to study . T his paper aims at concise and clear introduction to four methods including one brought forward by the author, which is named sum of serial numbers matching method. Keywords:signals and systems; convolution sum; column sum method; sliding strip method; sum of serial numbers matching method; polynomial expression method 0 引言 卷积和在求解离散时间线性时不变系统中有着 举足轻重的地位。如果已知系统的冲激响应为 h( n), 则对任意激励 e(n) 的响应 r( n) 就是 h(n) 和 e(n) 的卷积和( 卷积)。 可见在时域直接求解离散时 间线性时不变系统响应的过程就是卷积和运算。 序 列 x1(n) 和 x2(n) 序列的卷积和定义为: x1(n)* x2(n) = E m= - x1(m) x2(n -m)(1) 同连续时间卷积运算一样, 计算序列卷积和最 直接的方法是利用定义式直接求解, 另外一种方法 是图解法。在一般的信号与系统教材中, 对这两种 最基本的方法都有讲解, 这里不再赘述。 而在实际应用中, 需要处理的常常是有限长度 序列, 有多种方便而简单的方法求解它们的卷积和。 但在国内教材中鲜有介绍, 即便介绍了, 也只是寥寥 数语。笔者结合多年的教学体会, 在本文中详细地 介绍三种方法, 也简单介绍一种由笔作者提出的方 法 ) 序号和匹配法。 1 有限长序列卷积和的几种求解法 下文中都以序列 x1(n) = 2 5 | 0 4 和 x2( n) = 4 | 1 3 序列为例。 1. 1 列求和法 在列求和法中, 把参与求卷积和的其中一个序 列用冲激序列 D (n) 表示, 即 x1(n) = E m x1(m)D (n -m)( 2) 考虑到 D ( n -m) * x2(n) = x2(n -m)( 3) 从而 x1(n)* x2(n) = E m x1(m) D ( n -m) * x2(n) = E m x1(m)x2(n -m)( 4) 这表明 x1(n)* x2(n) 的结果是 x2( n) 移位加 权 x2(n -m) 的和, 权重为 x1(m)。 对本文中的两个序列, x1( n) 可以表示为 x1(n) = 2D ( n+ 1) + 5D (n) + 4D (n -2) 从而 x1(n)* x2(n) = 2D ( n+ 1) + 5D (n) + 4D ( n -2) * x2( n) = 2x2( n+ 1)+ 5x2( n)+ 4x2(n -2) 具体的计算过程用表1表示。 x2( n) 的起始序号 为零, 所以2x2( n+ 1) 的起始序号为-1, 表格的最后 一行标出了序号。 排列时要注意各列的相对位置, 5x2( n) 的起始序号较 2x2( n+ 1) 大1, 所以在右边1 格开始排列; 4x2(n -2) 的起始序号较 2x2(n+ 1) 大 3, 所以在右边 3 格开始排列。 表格的第 3-5 行按列 相加的结果就得到所求的卷积和为 x1(n)* x2(n) = 8 22 | 11 31 4 12 表 1 列求和法求卷积和实例 x1( n) x2( n) 2 5 0 4 4 1 3 2D ( n+ 1) * x2( n) = 2x2( n+ 1) 5D ( n) * x2( n) = 5x2( n) 4D ( n -2) * x2( n) = 4x2( n -2) 8 2 6 20515 16 412 x1(n)* x2( n) = 2x2(n+ 1) + 5x2( n) + 4x2( n -2) 8 22 11 31 4 12 序号-1 0 1 2 3 4 1. 2 游带法 反转 x2(n) 得到x2(-n) , 然后将x2(-n) 移位使 得它的最后一格元素与 x1(n) 的起始元素对齐。 接 着, 对 x2(-n) 一次右移一个元素, 求得它与 x1( n) 重叠元素的乘积之和, 就是每个序号上的卷积和。 游 带法是在纸条上列出反转序列的值并使其滑过固定 的序列。 游带法中的滑动实际上就是 n 递增的过程, 从 图 1 游带法求卷积和实例 x1( m) 和 x2( n -m) 刚好重叠开始, 到最终分离为止。 在求解过程中, 不变的序列为 x1(m) , 滑动的序列是 x2( n -m)。对 重 叠的 元素 按 列求 乘 积,就是 求 x1( m)x2( n -m)。 对这些乘积求和, 就是卷积和定义 式中的对 m 求和。 由此可见, 游带法的实质是卷积 和的定义和图解法的结合。 卷积和的起始序号为参 与运算的两个序列序号之和, 所以刚开始滑动时得 到的乘积之和 8为序号为 n = -1+ 0 = -1 的卷积 和, 其余的依次递增一个序号。 所以最后的结果为 x1( n)* x2( n) = 8 22 | 11 31 4 12 1. 3 序号和匹配法 考虑卷积和的定义式( 1) , 定义式其中对 m 求 和的每一项为 x1(m)x2( n -m) 。 但对固定的 n, m 变 动时, 乘积x1( m)x2( n -m) 中两项x1(m) 和x2( n -m) 的序号和为(n -m) + m = n, 保持不变为 n且与m 无 关, 称为序号和的不变性, 这就是序号和匹配法的出 发点。 序列 x1( n) 有非零值序号为 l1= -1 0 1 2 ; 序列 x2( n) 有非零值的序号为l2= 0 1 2 。 卷积和 x1( n)* x2( n) 有非零值的序号l 是l1和l2分别两两 相加的结果。 l 的最小值是l1和l2最小值之和, l 的最 大值是 l1和 l2最大值之和, 所以卷积和的起始序号 是两个序列起始序号值之和, 结束序号是两个序列 结束序号之和。 若 l1和 l2中的多对序号两两相加的 结果等于 k, 则 y(k) 就是由这些序号对的对应值乘 积之和。 比如 l1中的 0、 1、 2 分别和 l2中的 2、 1、 0 相 加等于 2, 所以 y(2) = x1(0) x2(2) + x1(1)x2(1) + x1( 2)x2(0) = 5 3+ 0 1+ 4 4= 15+ 16 = 31 表 2 直观地给出了一个计算实例。第 1 -2 行为 两个序列值, 括号内为序号。第 3 -5 行中的小括号 内给出了两个序列对应的序号, 序号和相同的乘积 排在同一列上。由表可以看出, 第 3 -5 行中的每一 行都是 x2( n) 中的一个序列值依次乘以 x1( n) 的全 46 电气电子教学学报 第 30 卷 部序列值得到的, 排列时每一行依次右移一格。每 一列的和就是最后的结果。 表 2 序号和匹配求卷积和实例 1. 4 多项式表示法 对参与卷积和运算的有限长序列用多项式表示, 一种最简单的方法是,多项式的系数是序列的各个值, 幂次数是序号值。比如,用多项式表示序列x1(n) 为 x1(z) = 2z-1+ 5+ 4z 2 用多项式表示序列 x2( n) 为 x2(z) = 4+ z + 3z 2 则卷积 x1( n)* x2(n) 和 的多 项式 表示 是乘 积 x1(z) x2(z ), 即 x1(z)x2(z) = 8z-1+ 22+ 11z + 31z 2 + 4z 3 + 12z 4 上式右端多项式中每一项的系数就是卷积和的结 果, 每一项的幂次数就是对应的序号。 从而 x1(n)* x2(n) = 8 22 | 11 31 4 12 在这种表示中多项式的幂次数是序号值, 求乘 积多项式的过程就是参与卷积和运算的两个序列的 序号相加、 序号和相等的项合并的过程, 由此可见这 种方法和序号和匹配法的实质是一致的。 2 结语 本文简明介绍了四种有限长序列卷积和的计算 方法, 包括笔者提出的序号和匹配法。列求和法是 把参与卷积和运算的其中一个序列用脉冲序列表 示, 而脉冲序列和一般序列的卷积和非常简单; 游带 法利用卷积和的定义式, 使得反转和移位的序列有 序地滑过固定的序列, 其实质就是图解法; 对每个固 定的 n, 序号和匹配法是基于卷积和定义式中的每 个乘积项的序号和保持不变, 把序号和相同的项相 加即可得到对应于序号 n 的卷积和; 多项式系数求 解法是把序列的值用多项式的系数表示, 序号值用 多项式的幂次数表示, 求乘积多项式的过程就是参 与卷积和运算的两个序列的序号相加、 序列值相乘、 序号和相等的乘积合并的过程, 这种方法与序号和 匹配法的实质是一致的。 为了弥补国内教材对有限长序列卷积和求解法 讲解的不足, 有少数教材简单介绍了一种类似于本 文序号和匹配法的方法, 但对具体的计算过程没有 讲解。本文系统地介绍了几种方法, 希望本文对同 行的教学有所裨益。 参考文献: 1 郑君里, 应启珩, 杨为理. 信号与系统( 第二版) M . 北京: 高等 教育出版社, 2000. 2 Ashok Ambardar 著, 冯博琴等译. 信号、 系统与信号处理 M . 北京: 机械工业出版社, 2001. 3 乐正友. 信号与系统 M . 北京: 清华大学出版社, 2004. 4 管致中, 夏恭恪. 信号与线性系统( 第三版) M . 北京: 高等教 育出版社, 1992. 5 吴大正主编. 信号与线性系统分析( 第三版) M . 北京: 高等教 育出版社, 1998. ( 上接第 40 页贾君霞文) 4 结论 取N = 2 10 = 1024 , 采用 Matlab 编写程序 4 -5 。 结果表明, 本文提出的改进的快速算法比传统的快 速算法运算速度快了将近 2 倍, 而时延和传统的快 速算法是相同的。 参考文献: 1 M. Vetterli,0 Running FIR and IIR filtering using multiply banks,0 IEEE T rans. Acoust. , Speech, Signal Process. , vol. 34. pp. 730 -738, May 1988. 2 I. Lin and S. K. M itra,0 Overlapped block digital filtering0, IEEE T rans. Circuits Sy st. II, vol. 43, no. 8, pp. 586 - 596, Aug. 1996. 3 P. P. Vaidyanathan, Multirate Systems and Filter Banks. F. Cliffs, NJ: Prentice - Hall, 1993. 4 J. W. Cooley, P. A. W. Lewis, and P. D. Welch,0 the fast Fou - rier transform algorithm: Programming considerations in the calculation of sine, cosine, and Laplace transforms,0 J. Sound Vibr