Ask Your Question
0

Playing with LFSR in sage

asked 2015-03-25 15:11:12 -0500

this post is marked as community wiki

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

2 answers

Sort by ยป oldest newest most voted
0

answered 2015-03-25 19:26:14 -0500

tmonteil gravatar image

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 more

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 gravatar imagecarinachen ( 2015-03-26 02:24:04 -0500 )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 gravatar imagetmonteil ( 2015-03-26 12:39:00 -0500 )edit
0

answered 2015-03-26 03:32:44 -0500

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 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: 2015-03-25 15:11:12 -0500

Seen: 98 times

Last updated: Mar 26 '15