ASKSAGE: Sage Q&A Forum - Latest question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Wed, 25 Mar 2015 15:11:12 -0500Playing with LFSR in sagehttp://ask.sagemath.org/question/26331/playing-with-lfsr-in-sage/ Hi there,
so this is only half a sage question and half a math question, I think. I'm trying to play around with LFSRs. Please help a computer scientist understand :-)
Let's say I have a 16 bit LFSR that is defined by the polynomial
poly = x^16 + x^14 + x^13 + x^11 + 1
(that's the Wikipedia polynomial from http://en.wikipedia.org/wiki/Linear_feedback_shift_register)
Now I have some code that gives me the whole bitsequence the polynomial generates. But I want to understand the mathematical side and would like to get the same bit sequence by doing polynomial division in sage. But I haven't really understood what the LFSR is mathematically, I think. Here's my pathetic attempt:
<pre>
P.<x> = GF(2)[]
poly = x^16 + x^14 + x^13 + x^11 + 1
state = x^2
for i in range(20):
outbit = state // poly
state = state % poly
print(outbit, state)
</pre>
Which obviously always outputs (0, state). I do know why it does that and I know that my algorithm is wrong but I don't know how to write it so it does what I want. I would be forever grateful :-) if you could bring me up to speed.
Thank you so much! CarinacarinachenWed, 25 Mar 2015 15:11:12 -0500http://ask.sagemath.org/question/26331/berlekamp 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.evrimSat, 09 Feb 2013 14:00:43 -0600http://ask.sagemath.org/question/9792/