《信号处理第五章》由会员分享，可在线阅读，更多相关《信号处理第五章（28页珍藏版）》请在金锄头文库上搜索。
1、现代数字信号处理：第五章 列文森递归算法5-1第五章第五章 列文森递归算法列文森递归算法5.1 引言引言第四章中已看到，很多种信号建模问题都需要求解如下形式的线性方程组：(5.1)xpR ab其中是 Toeplitz 矩阵。例如在 Pade 逼近法中，估计由矢量所表示的分母系数就是求xRpa( )pak解象式(5.1)的一组 Toeplitz 方程，其中是一个非对称的 Toeplitz 矩阵，其第一列是信号值xR，第一行是，另外矢量由信号值( ), (1),., (1)x q x qx qp( ), (1),., (1)x q x qx qpb组成，因此与矩阵的元素值密切相关。ARMA 过程建
2、模中的修(1), (2),., ()x qx qx qpxR正 Yule-Walker 方程也是这一类的线性方程组。在用 Prony 法或自相关法对确定性信号进行全极点 建模，以及用 Yule-Walker 法对随机过程的全极点建模中，都要遇到 Toeplitz 方程。但与 Pade 逼 近时不同，这时的是自相关值的哈密顿 Toeplitz 矩阵。另外，由于这时xR(0),(1),.,(1)xxxrrrp 的，式(5.1)右边矢量还是与 Toeplitz 矩阵的元素值密切相关。在求解(1),(1)T xxrrpLb分子系数的 Shanks 法中，又会遇到一组哈密顿 Toeplitz 方程，但与
3、前面不同的是这时的矢量中b 不含有矩阵的元素值。在第七章的 FIR 维纳滤波器设计中，还要遇到 Toeplitz 方程，与 ShanksxR法中一样，其是哈密顿 Toeplitz 的，但的取值与的值无关。xRbxR由于在很多问题中求解 Toeplitz 方程的重要性，本章介绍求解这类方程的有效算法。在导出这 些算法的过程中，我们将发现这类方程的解的一系列有趣的性质，由此可进一步获得信号建模的 其它方法。在5.2 节，我们首先导出 Levinson-Durbin 递归算法，该算法可用于求解 Prony 全极点 正则方程和自相关正则方程。Levinson-Durbin 递归将导致几个重要的结果，包
4、括格型滤波器结构、 数字滤波器的 Schur-Cohn 稳定性测试、Toeplitz 矩阵的 Cholesky 分解，以及 Toeplitz 矩阵的递归 求逆。5.3 节介绍求解一般的哈密顿 Toeplitz 方程的 Levinson 递归方法，注意这时对矢量没有b 约束。该算法可用在 Shanks 法中，也可用于求解第七章中的一般 FIR 维纳滤波问题。5.4 节将导 出分基 Levinson 递归算法，它比 Levinson-Durbin 递归的效率要稍高些，并引入了奇异预测器多项奇异预测器多项 式式和线谱对线谱对的思想，它们在语音处理应用中很有用。5.2 Levinson-Durbin
5、递归递归1947 年 Levinson 给出了求解一般的线性对称对称 Toeplitz 方程组的递归算法。在一个有x=R ab关维纳线性预测问题的评注论文中，Levinson 称该算法是一个“数学上平凡的过程”16，但是， 这一递归算法导致了若干重要的发现，其中包括格型滤波器结构，它在语音处理、谱估计、数字 滤波器实现中获得了广泛的应用。后来在 1961 年，Durbin 针对方程右边是单位矢量的特例改进了 Levinson 递归算法7，本节我们就介绍该算法，称为 Levinson-Durbin 递归递归。另外，将给出该递 归的一些性质，说明它如何导致格型滤波器结构，并证明由自相关法所导出的全
6、极点模型是稳定 的。5.2.1 递归式的推导递归式的推导用 Prony 法或自相关法进行全极点建模时，要求解正则方程，对阶模型，方程为：p; (5.2)1( )( ) ()0pxpx lr kal r kl1,2,.,kp而建模误差为：(5.3)1(0)( ) ( )ppxpx lral r l将上面两个方程组合成矩阵，应有：现代数字信号处理：第五章 列文森递归算法5-2(5.4)*1(0)(1)(2)( )1(1)0(1)(0)(1)(1) (2)0(2)(1)(0)(2)0( )( )(1)(2)(0)xxxxpxxxxppxxxxpxxxxrrrrparrrrparrrrpaprprpr
7、pr L L LMMMMMM L它有个线性方程，也有个未知量，即和。上式的等效矩阵形1p 1p (1),(2),.,( )pppaaapp式为： (5.5)ppR au其中是的哈密顿 Toeplitz 矩阵，是单位矢量。对实值数据，pR(1)(1)pp1,0,.,0T=u将是对称 Toeplitz 矩阵。xR求解方程(5.5)的 Levinson-Durbin 递归是一个按模型阶递归的算法，换言之，阶全极点(1)j 模型的系数是由第阶模型的系数而获得。因此，我们首先说明如何由阶正则方程的解1jajjaj导出阶正则方程的解。设是如下的正则方程的解：1j ( )ja i(5.6)*1(0)(1)(
8、2)( )(1)(1)(0)(1)(1)0(2)0(2)(1)(0)(2)( )0( )(1)(2)(0)xxxxjjxxxxjxxxxjxxxxrrrrjarrrrjarrrrjajrjrjrjrL L LMMMMMM L方程的矩阵形式为：(5.7)1jjjR au给定，我们要导出如下的阶正则方程的解：ja(1)j (5.8)1111jj+jRau推导过程如下。假定我们将矢量补一个零，并用左乘新矢量，则结果应为：ja1jR(5.9)*1(0)(1)(2)( )(1) (1)(1)(0)(1)(1)( ) (2)(2)(1)(0)(2)(1)( )( )(1)(2)(0)(1) 0(1)( )
9、(1)(1)(0)xxxxxjxxxxxjxxxxxjxxxxxxxxxxrrrrjrj arrrrjrj arrrrjrjajrjrjrjrr rjrjrjrr L L L MMMMMM L L0 00jj M其中参数为：j(5.10)1(1)( ) (1)jjxjx irja i rji 注意若,则(5.9)式右边是一个维单位矢量,且是(j+1)0j(1)j 1= 1, (1), ., ( ), 0Tjjjaaja阶正则方程(5.8)的解。但通常，不是方程(5.8)的解。0j1,(1),(2),.,( ),0Tjjjaaaj推导 Levinson-Durbin 递归的关键步骤是利用的哈密顿
10、 Toeplitz 特性，使得可将式(5.9)写1jR成如下的等效形式：(5.11)*(0)(1)(2)( )(1)0 ( )(1)(0)(1)(1)( ) (1)(2)(1)(0)(2)(1)(1)( )(1)(2)(0)(1) 1(1)( )(1)(1)(0)xxxxxjxxxxxjxxxxxjxxxxxxxxxxrrrrjrj ajrrrrjrj ajrrrrjrjarjrjrjrr rjrjrjrr L L L MMMMMM L L0 00jj M现代数字信号处理：第五章 列文森递归算法5-3取式(5.11)的复数共轭并将所得方程与式(5.9)进行加权组合，则对任意的(复)常数，有：1
11、j(5.12)*111*01 ( )(1)00 (2)(1)00 .00( )( ) 01jjjjjjjjjjj jjaja aajajaj R由于我们是要求解矢量，使得它被相乘后得到一个维的单位矢量，显然，若取：1j+a1jR(1)j (5.13)1*j j j 则右边矢量最后一个分量为零，该矢量可写成维单位矢量，而式(5.12)就变为：(1)j 1111jj+jRau其中(5.14)*11*01 ( )(1) (2)(1)( )(1) 01jjjjj+jjjaja aajaja MMa它就是阶正则方程的解。另外，(1)j (5.15)2* 1111jjjjjj 是阶建模的误差。(注：由于是
12、实数，式(5.13)中的复数共轭可以去掉。)如果我们定义(1)j j，则被称为阶递归方程阶递归方程的式(5.14)可以简单表达为：(0)1ja(1)0jaj (5.16)* 11( )( )(1); 0,1,.,1jjjjaia iajiij 为完成该递归的推导，还必须定义该递归算法初始化的必要条件，这些条件由阶模型的0j 解给出，即为：0(0)1a(5.17)0(0)xr综上所述，可概括 Levinson-Durbin 递归算法的各步骤如下。首先用零阶模型的解(5.17)对其初 始化，然后对，由第阶模型的解分三步求第阶模型。第一步是用式(5.10)0,1,.,1jpj(1)j 和(5.13)
13、确定的值，也称为第个反射系数；第二步是利用 Levinson 阶更新方程由1j1j(1)j 计算系数；最后一步是用式(5.15)更新误差。该误差还有另外两个等效表达式，( )ja i1( )jai1j 在后面的讨论中要用到。第一个是：(5.18)122 11 11(0)1jjjjxi ir 第二个形式是来自式(5.3)，表达为：(5.19)111 1(0)( ) ( )jjxjx irai r i 完整的递归算法总结于表 5.1。图 5.1 给出了其 Matlab 程序。(注：不同的作者对 Levinson-Durbin递归中的变量定义有所不同，例如(5.12)中也可用或，结果就导致的符号不同
14、。)1j* 1j1j现代数字信号处理：第五章 列文森递归算法5-4表表 5.1Levinson-Durbin 递归递归算法算法0011* 111. (a)(0)1(b) (0) 2. 0,1,.,1(a) (1)( ) (1)(b) (c) 1,2,., , ( )( )(1)xjjxjx ij j jjjjja r jprja i rjiij aia iaji 初始化： 对，计算对计算11 211(d) (1)(e)13. (0)jjjjjpajb 图 5.1列文森杜宾递归的 Matlab 程序 _ 例 5.2.1求解自相关正求解自相关正则则方程。方程。 假定要用 Levinson-Durbin 递归求解自相关正则方程，以确定一个信号的 3 阶全极
