Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

My question is regarding LFSRs (Linear Feedback Shift Registers), and the binary Galois Field produced by them (also commonly termed GF($2^n$) ).

I understand that a given n-bit LFSR produces a cyclic sequence of ($2^n-1$) bitvectors, which are all the non-zero elements of GF($2^n$).
An LFSR can be one of 2 types:

  1. Fibonacci LFSR (aka 'External XOR LFSR' / 'Standard LFSR')
  2. Galois LFSR (aka 'Internal LFSR' / 'Modular LFSR')

Consider the following type 2 LFSR.

TYPE 2 LFSR FIGURE

Here $n=3$, and the sequence of elements produced by this LFSR is as follows:

$100 <=> 1$
$010 <=> x$
$001 <=> x^2$
$110 <=> 1+x$
$011 <=> x+x^2$
$111 <=> 1+x+x^2$
$101 <=> 1+x^2$

The 'Characteristic polynomial' or 'Modulus Polynomial' for this LFSR is: $P = 1+x+x^3$
The 'Primitive Element' or 'Generator' is: $G = x$
This means that taking successive powers of $x$ modulo the polynomial $P$, will produce all non-zero elements of the ring (the elements above are easily verified). All arithmetic is modulo-2.

An analogous type 1 LFSR may be constructed, using the same $P=1+x+x^3$.

TYPE 1 LFSR FIGURE

It produces the following (cyclic) bitvector sequence:

$001$
$100$
$010$
$101$
$110$
$111$
$011$

How do I determine the 'Generator' element for this new Galois Field?
How do I decide on a bitvector <-> Polynomial name mapping for this field (as was done for the Type 2 LFSR above)?
Is $P=1+x+x^3$ even the true 'Characteristic Polynomial'/'Modulus Polynomial' for this new field?

Thanks for your help!

share|improve this question
    
For starters take a look at Dilip Sarwate's answer to another question. His reply to my comment may also be helpful. –  Jyrki Lahtonen Mar 17 '12 at 14:19
    
Thanks Jyrki.. I read all comments on the page. I understand that the 'Companion Matrices' of a Galois LFSR and the corresponding Fibonacci LFSR are transposes of one another, which in turn means that their 'Characteristic Polynomials' are identical. However, I am still not sure how to determine the 'Primitive Element' for a Fibonacci LFSR. What would be a generic procedure to find a generator for a Fib.LFSR? –  dhrumeel Mar 17 '12 at 20:13

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.