Playing with LFSR in sage

asked 2015-03-25 21:11:12 +0100

This post is a wiki. Anyone with karma >750 is welcome to improve it.

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_f...)

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:

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)

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! Carina

edit retag flag offensive close merge delete

add a comment

2 Answers

Sort by » oldest newest most voted

answered 2015-03-26 09:32:44 +0100

rws
1149 ●2 ●20 ●44 http://google.com/+Ral...

While you got already a good specific answer you might be interested in Sage's LFSR implementation, see http://sagemath.org/doc/reference/cry...

edit flag offensive delete link

add a comment

answered 2015-03-26 01:26:14 +0100

tmonteil
27423 ●31 ●204 ●517 http://wiki.sagemath.o...

Here are some bits to start thinking.

First, the polynomial should have coefficients in the field of two elements GF(2). In this binary field, the addition correspond to the xor operation:

sage: F = GF(2)
sage: F(1) + F(1)
0
sage: F(1) + F(0)
1
sage: F(0) + F(1)
1
sage: F(0) + F(0)
0

and the multiplication corresponds to the and operation:

sage: F(1) * F(1)
1
sage: F(1) * F(0)
0
sage: F(0) * F(1)
0
sage: F(0) * F(0)
0

When you write

sage: poly = x^16 + x^14 + x^13 + x^11 + 1

you define a symbolic expression, such as cos(x) or log(pi) but you do not tell Sage that the coefficients belong to GF(2), the field with two elements:

sage: poly.parent()
Symbolic Ring
sage: cos(x).parent()
Symbolic Ring

Instead you should do:

sage: x = polygen(GF(2), 'x')
sage: poly = x^16 + x^14 + x^13 + x^11 + 1
sage: poly.parent()
Univariate Polynomial Ring in x over Finite Field of size 2 (using NTL)

Now, you have a polynomial with coefficients in GF(2), as you can check:

sage: poly + 1
x^16 + x^14 + x^13 + x^11
sage: poly + x
x^16 + x^14 + x^13 + x^11 + x + 1
sage: poly + x^11
x^16 + x^14 + x^13 + 1
sage: poly + poly
0

You can check that this polynomial is primitive:

sage: poly.is_primitive()
True

and that it divides x^(2^16-1)+1:

sage: poly.divides(x^(2^16-1)+1)
True

According to your links, both properties together imply that the period of the LFSR is 2^16-1=65535.

edit flag offensive delete link

Comments

Oooops I accidantly posted this as an answer. Here it goes again:

Hey there,

thank you so much for your answer :-)

Oh yes I forgot the most important line when I copy and pasted my code. I used

P.<x> = GF(2)[]

Is that the same effect as the definition you described or am I doing it wrong still?

I'm still not sure how I would get the feedback right. Yes the period should be 65535, this is correct. So basically I want to write some code which repeatedly divies and modulos some polynomials and outputs a 65535 bit sequence before it start over. But I'm still not sure how to start. Maybe there's another pointer?

Thank you so much for your help! Carina

carinachen ( 2015-03-26 08:24:04 +0100 )edit

Wtiring

 sage: P.<x> = GF(2)[]

define both P as the polynomial ring over GF(2) and the indeterminate x as an element of P.

Writing

sage: x = polygen(GF(2), 'x')

defines the same indeterminate x, as you can see by typing:

sage: x.parent() == P
True

So this is the same effect and you were right.

tmonteil ( 2015-03-26 18:39:00 +0100 )edit

add a comment

Your Answer

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

Add Answer

Playing with LFSR in sage

2 Answers

Comments

Your Answer

Question Tools

Stats

Related questions

Playing with LFSR in sage edit

2 Answers

Comments

Your Answer

Question Tools

Stats

Related questions

Playing with LFSR in sage