为了使读者对Levinson-Durbin 算法的应用背景有所了解，在此我们先简单地描述一下基于最小均方误差的线性预测编码（LPC）算法。

假设是一实数据列，，我们可以用过去时刻的个数据来预测当前时刻的数据， 即：

这里即为预测系数。定义预测误差为

我们将采用最小均方误差准则来选择的值，使得式(A.3)总误差最小。

这种优化参数的方法导致了求解如下的正则方程组 

这里的是序列的自相关系数。式（A.4）可写成如下的矩阵形式：

          （A.5）

其中

        6)

        7)

注意到具有的性质，式(A.5)中的可写成如下形式

    8)

Levinson-Durbin算法是求解正则方程组中的预测系数的有效算法。这种算法利用了自相关矩阵中特殊的对称性。注意到，即对角线上的元素都相等，所以这个自相关矩阵是Toeplitz矩阵。

Levinson-Durbin 算法利用了Toeplitz矩阵的特点来进行迭代计算。即首先由一阶预测器()开始，计算预测系数。然后增加阶数，利用低阶的结果得到下一个高阶的计算结果。根据(A.4)式求解得到的一阶预测器的预测系数是：

其最小均方误差是：

 A.10)

这里是格形滤波器的第一反射系数。

下一步是求解二阶预测器的系数和，并将结果用表示，根据式(A.5)得到的两个方程是:

       （A.11）

通过用(A.9)的解来消去，我们得到解：

          （A.12）

这样我们得到了二阶预测器的预测系数，我们再次注意到是格形滤波器中的第二反射系数。

据此类推，我们可以用阶预测器的预测系数来表示阶预测器的系数。这样，我们可将阶预测系数矢量写成两矢量的和，也就是

        A.13)

这里矢量是第阶预测器的预测系数，维的矢量和标量是待定的。我们将自相关矩阵分区如下：

         (A.14)

这里，的上标b表示元素的倒序排列。

根据式(A.13)和(A.14)，式(A.5)可以写成如下形式

     (A.15)

这是Levinson-Durbin 算法中的关键一步，从式(A.15)中我们得到两个方程

      6)

     7)

由于， 由式(A.16)得到

          8)

又由于仅是倒序排列，且是Toeplitz，因此可得

           (A.19)

即： 

           (A.20)

因此式(A.18)可写成

       .21)

现在可用式(A.17)这个方程来求解，如果我们用式(A.21)来消去式(A.17)中的，可得

     （A.22）

注意到，由式(A.22)可得

因此，通过用式(A.21)和(A.23)的结果，替换式(A.13)中的值，我们得到了求解预测器系数的Levinson-Durbin 迭代算法。

    4)

最后我们来确定最小均方误差的表达式。对于阶预测器我们有

               6)

利用公式（A.24）可得

      A.27)

这里。

由于，根据式（A.27）知反射系数满足，这样预测器最小均方误差序列满足条件：

      （A.28）

至此，求解线性方程组的Levinson-Durbin算法就介绍完了。下载本文