 # xorshift worked example

Jan 16th, 2021
84
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1.
2. consider the irreducible polynomial a^4 + a + 1 = 0
3.
4. place values are
5. 1 | a | a^2 | a^3
6.
7. 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.
8.
9. So notice that multiplying by 'a' is achieved with downshift instead of upshift.
10. 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.
11.
12. Now let us look at some powers of a:
13.
14. power 1 a a^2 a^3 | a^4
15. -----------------------
16. 1 1 0 0 0 | 0
17. a 0 1 0 0 | 0
18. a^2 0 0 1 0 | 0
19. a^3 0 0 0 1 | 0
20. a^4 0 0 0 0 | 1 // 1 bit in a^4 position. Apply a^4 + a + 1 = 0 to reduce this expression
21. 1 1 0 0 | 0
22. a^5 0 1 1 0 | 0
23. a^6 0 0 1 1 | 0
24. a^7 0 0 0 1 | 1 // reduce
25. 1 1 0 1 | 0
26. a^8 0 1 1 0 | 1 // reduce
27. 1 0 1 0 | 0
28. a^9 0 1 0 1 | 0
29. a^10 0 0 1 0 | 1 // reduce
30. 1 1 1 0 | 0
31. a^11 0 1 1 1 | 0
32. a^12 0 0 1 1 | 1 // reduce
33. 1 1 1 1 | 0
34. a^13 0 1 1 1 | 1 // reduce
35. 1 0 1 1 | 0
36. a^14 0 1 0 1 | 1 // reduce
37. 1 0 0 1 | 0
38. a^15 0 1 0 0 | 1 // reduce
39. 1 0 0 0 | 0 // = 1
40.
41. 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.
42.
43. - multiplying by 'a' is equivalent to downshifting the register, with the bits in the a^3 column dropping off.
44. - We can be represent this poly by it's coefficients, 11001 = 1 + a +  +  + a^4.
45. - Because we can ignore the a^4 term, we can ignore the trailing 1. The hex value encoding this polynomial is 0xC = '1100'
46. - Reducing the expression is now equivalent to XORing in this HEX if the low bit was '1' before the downshift.
47. - 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.
48.
RAW Paste Data