Sorceress

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 + [0] + [0] + 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