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:
- Fibonacci LFSR (aka 'External XOR LFSR' / 'Standard LFSR')
- Galois LFSR (aka 'Internal LFSR' / 'Modular LFSR')
Consider the following type 2 LFSR.
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$.
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!