Ask Your Question
0

berlekamp massey

asked 2013-02-09 14:00:43 -0600

evrim gravatar image

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.

edit retag flag offensive close merge delete

1 answer

Sort by » oldest newest most voted
1

answered 2013-02-24 23:09:05 -0600

Francis Clarke gravatar image

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].

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2013-02-09 14:00:43 -0600

Seen: 330 times

Last updated: Feb 24 '13