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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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