Berlekamp Massey 算法

一些定义

$F,G$:这样的大写字母一般代表一个数列

$deg(f)$:数列f的长度,下标从1开始

功能

为一个序列,求一个非平凡的齐次线性递推方程。

解释

非平凡的齐次线性递推方程,即找到一种规律,使这个序列满足这个规律。同时这个规律必然是通过前$n-1$或更短的前缀找到的,然后后面几项依旧满足这个规律。

形式化定义

已知$F$,求最短的$G$使:
$$
\forall deg(F)\geq n>deg(G),\ F_n = \sum_{i=1}^{deg(G)}G_iF_{n-i}
$$

原理

  • 1.如果存在$F,G_0,G_1$,且$n=deg(F)=deg(G_0)=deg(G_1)$, $G_0,G_1$根据$F$生成的数列的第$n+1$项分别为$a,b$,那么$(G_0+G_1)$根据$F$生成的数列的第$n+1$项就是$a+b$。
  • 2.将$G$移动一位,第一位补0,则$G$根据$F$生成的数列整体移动一位。
  • 3.如果$G$通过$F$生成的第$[m+1,k]$项与$F$相同,那么$G$移动一位,第一项补-1再根据$F$生成的数列第$[m+2,k+1]$项为0。

以上三个原理的证明不难,在此略过。根据以上几个原理,我们就可以找到一种通过调整$G$获得正确的递推方程的方法。

步骤

  • ①随便给出一个递推数列$G={1}$,和一个用于调整$G$的数列$H={\frac{1}{F[1]}}$。
  • ②算法不断用$G$通过$F$生成第$i\in[1,n]$位,生成的数列叫做$I$
    • $I[i] = F[i]$:数列$G$暂时通过了检测,将$H$移动一位,第一位补$0$,返回②
    • $I[i] \not = F[i]$:数列$G$没有通过检测,通过将$G$加上$H$的倍数,使得$I[i]=F[i]$,然后$H$变为$G$,并移动一位,第一位补$-1$,然后整体缩放后,返回②
  • 最终得到的$G$,据说就是最短的$G$

疑问

  • 1.第二步的第二种情况,当$deg(H)<deg(G)$时为何还要将$H$赋值给$G$?或许这时是否赋值是无关紧要的?

以上的问题经过思考已经解决。不难证明$G$的度数永远会比$F$大。

分类: 文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *