xorshift worked example

consider the irreducible polynomial a^4 + a + 1 = 0

place values are
1 | a | a^2 | a^3

The 1 position is the high bit, and the a^3 position is the low bit. An a^4 column has been included for explanation below.

So notice that multiplying by 'a' is achieved with downshift instead of upshift.
This makes it easier to detect the highest power term, as it is always the low bit, no matter what size of register/polynomial is used.

Now let us look at some powers of a:

power 1 a a^2 a^3 | a^4
-----------------------
1     1 0 0   0   | 0
a     0 1 0   0   | 0
a^2   0 0 1   0   | 0
a^3   0 0 0   1   | 0
a^4   0 0 0   0   | 1 // 1 bit in a^4 position. Apply a^4 + a + 1 = 0 to reduce this expression
      1 1 0   0   | 0
a^5   0 1 1   0   | 0
a^6   0 0 1   1   | 0
a^7   0 0 0   1   | 1 // reduce
      1 1 0   1   | 0
a^8   0 1 1   0   | 1 // reduce
      1 0 1   0   | 0
a^9   0 1 0   1   | 0
a^10  0 0 1   0   | 1 // reduce
      1 1 1   0   | 0
a^11  0 1 1   1   | 0
a^12  0 0 1   1   | 1 // reduce
      1 1 1   1   | 0
a^13  0 1 1   1   | 1 // reduce
      1 0 1   1   | 0
a^14  0 1 0   1   | 1 // reduce
      1 0 0   1   | 0
a^15  0 1 0   0   | 1 // reduce
      1 0 0   0   | 0 // = 1

See that the a^4 column is not needed in practice. We detect a '1' in the previous a^3 column, prior to multiplying by 'a'. Then after multiplying by 'a', we can reduce the polynomial if that '1' was present.

- multiplying by 'a' is equivalent to downshifting the register, with the bits in the a^3 column dropping off.
- We can be represent this poly by it's coefficients, 11001 = 1 + a + [0] + [0] + a^4.
- Because we can ignore the a^4 term, we can ignore the trailing 1. The hex value encoding this polynomial is 0xC = '1100'
- Reducing the expression is now equivalent to XORing in this HEX if the low bit was '1' before the downshift.
- It is important to note this reversal of the binary representation with this downshifting variant of the LFSR. For each irreducible polynomial, it's reverse is also irreducible, which could mask implementation errors.