berlekamp massey

savecancel

Yes, there is a problem with the Sage implementation. But other implementations such as the one at bma.bozhu.me may give varying results. The point is that for your sequence $s_0,s_1,\dots,s_{35}$ there does not exist a unique sequence $c_1,c_2,\dots,c_k$ in $GF(2)$ such that $$s_i+\sum_{j=1}^{k}c_js_{i-j}=0,\qquad\text{for $i=k,\dots,35$.}$$

The result that Sage produces comes from the fact that $$s_i+s_{i-2}+s_{i-3}+s_{i-4}+s_{i-5}=0,\qquad\text{for $i=16,\dots,33$.}$$ But this fails (generally) if $i=5,\dots,15$ or $i=34, 35$.

The degree 19 result indeed says that $$s_i+\sum_{j\in\lbrace1, 2, 5, 6, 9, 10, 11, 13, 16, 17, 19\rbrace}s_{i-j}=0,\qquad\text{for $i=19,\dots,35$.}$$ However, this is not unique (it cannot be because the input sequence only has length 36), for example we could add in $s_{i-2}+s_{i-4}+s_{i-5}+s_{i-6}+s_{i-7}$, which, as we have seen, is zero for $i=18,\dots,35$. Thus the degree 19 polynomial has no right to be called the minimal polynomial. Of course, Massey's 1969 paper "Shift-register synthesis and BCH decoding" is clear on this point; the algorithm he describes produces "one of the [linear feedback shift registers] of [minimum length] which generates $s_0,s_1,\dots,s_N$" [§ III].