BM算法

Berlekamp-Massey算法

BM算法是用来求解一个数列的最短线性递推式的算法 在本文中，BM算法具体被用于求解产生已知序列的线性移位寄存器的特征多项式及级数

一些定义

• R₀={}      //初始递推式

• cnt       //递推式的修改次数

• delta_i=a_i - $\sum_{j=1}^m$ r_j*a_i-j   //递推式的正确性的判断，其中r_i是递推式的元素，m是递推式中元素的个数

• fail_k=i      //表示R第k次出错，在a_i处出错

• mul=$delta_i \over delt_{fail_{cnt-1}}$

• R′={   (i-fail_cnt-1-1个0)  ,  mul, -mul·R_cnt-1}

• R_cnt+1=R_cnt+R′  //(按位相加)

计算步骤

\[一、delta_i = \begin{cases} delta_i=0 & 不修改 \\ delta_i\neq0 & 计算fail_{cnt} \end{cases}\] \[二、faila_i=i\begin{cases} cnt=0 & R_{cnt}=\{\overbrace{0,0,···,0}^{i个}\} \\ cnt\neq0 & 转三 \end{cases}\] \[三、cnt\neq0 \begin{cases} mul={delta_i \over delt_{fail_{cnt-1}}\ } & \\ R′=\{\overbrace{0,0,···,0}^{i-fail_{cnt-1}个},mul,-mul·R_{cnt-1}\}&\\ R_{cnt+1}=R_{cnt}+R′(按位相加) \end{cases}\]

实例

令待测序列S=10101111

• R₀={} cnt=0

• a₁=1  delt₁=1  fail₀=1  R₁={0}  cnt=1

• a₂=0  delt₂=0   不修改

• a₃=1  delt₃=1  fail₁=3  mul=1  R′={0,1,0}  R₂={0,1,0}  cnt=2

• a₄=0  delt₄=0   不修改

• a₅=1  delt₅=0   不修改

• a₆=1  delt₆=1   fail₂=6  mul=1   R′={0,0,1,0} R₃={0,1,1,0}  cnt=3

• a₇=1  delt₇=0   不修改

• a₈=1  delt₈=-1  fail2=8  mul=-1 R′={0,-1,0,1,0} R₄={0,0,1,1,0}  cnt=4

综上，由R₄={0,0,1,1,0}  cnt=4可知目前为止得到的特征多项式为

1+0·x+0·x²+1·x³+1·x⁴+0·x⁵

级数为4.