ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Sun, 24 Feb 2013 23:09:05 -0600berlekamp masseyhttp://ask.sagemath.org/question/9792/berlekamp-massey/Hello,
I am trying to use B/M algo included in Sage. Now,
berlekamp_massey([GF(2)(0),0,1,0,1,0,0,1,0,1,1,1,0,0,1,1,0,0,0,0,1,0,1,1,0,1,0,1,0,0,0,1,1,1,1,0])
evals to f(x)=x^5 + x^3 + x^2 + x + 1 which is the minimal poly.
Also, I know that when I take the reciprocal (x^5*f(1/x)), I find
g(x)=x^5+x^4+x^3+x^2+1 which is the connection poly. of this LFSR.
My question is how can I regenerate this sequence using this connection poly.?
Providing initial states 0,0,1,0,1 yields to another sequence:
(0 0 1 0 1 1 0 1 0 1 0 0 0 1 1 1 0 1 1 1 1 1 0 0 1 0 0 1 1 0 0)
I think, there might be a bug in B/M implementation because other implementations give
x^19 + x^18 + x^17 + x^14 + x^13 + x^10 + x^9 + x^8 + x^6 + x^3 + x^2 + 1
when fed with the same sequence.
Thanks,
evrim.Sat, 09 Feb 2013 14:00:43 -0600http://ask.sagemath.org/question/9792/berlekamp-massey/Answer by Francis Clarke for <p>Hello,</p>
<p>I am trying to use B/M algo included in Sage. Now,</p>
<p>berlekamp_massey([GF(2)(0),0,1,0,1,0,0,1,0,1,1,1,0,0,1,1,0,0,0,0,1,0,1,1,0,1,0,1,0,0,0,1,1,1,1,0])</p>
<p>evals to f(x)=x^5 + x^3 + x^2 + x + 1 which is the minimal poly.
Also, I know that when I take the reciprocal (x^5*f(1/x)), I find
g(x)=x^5+x^4+x^3+x^2+1 which is the connection poly. of this LFSR.</p>
<p>My question is how can I regenerate this sequence using this connection poly.?
Providing initial states 0,0,1,0,1 yields to another sequence:</p>
<p>(0 0 1 0 1 1 0 1 0 1 0 0 0 1 1 1 0 1 1 1 1 1 0 0 1 0 0 1 1 0 0)</p>
<p>I think, there might be a bug in B/M implementation because other implementations give </p>
<p>x^19 + x^18 + x^17 + x^14 + x^13 + x^10 + x^9 + x^8 + x^6 + x^3 + x^2 + 1</p>
<p>when fed with the same sequence.</p>
<p>Thanks,
evrim.</p>
http://ask.sagemath.org/question/9792/berlekamp-massey/?answer=14595#post-id-14595Yes, there is a problem with the Sage implementation. But other implementations such as the one at [bma.bozhu.me](http://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"](http://crypto.stanford.edu/~mironov/cs359/massey.pdf) 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].Sun, 24 Feb 2013 23:09:05 -0600http://ask.sagemath.org/question/9792/berlekamp-massey/?answer=14595#post-id-14595