Comment by vanderZwan
5 years ago
I have no idea what those parameters represent, but I'm very curious! Could you give a layman's explanation?
5 years ago
I have no idea what those parameters represent, but I'm very curious! Could you give a layman's explanation?
The standard PRBS23 polynomial is X^23 + X^18 + 1. Most of the factors are zero. Only the factors for exp 23,18,1 are 1. This causes poor bit mixing - ie the output sequence will have strong correlation every 23 bits.
Choosing a "fat" primitive polynomial, ie a polynomial not from this list[0] but rather a polynomial with 50% of the taps are 1 (but it still must be primitive[1]), increases the avalanche effect[2] to the optimal 50% probability, ie 50% of the state bits affect the output at each step, instead of just 2 or 3 taps out of 23.
Note: the LFSR sequence length will remain the same, 2^23-1 in either case. It's just that the short-term correlation between bits will be lower.
[0] https://en.wikipedia.org/wiki/Linear-feedback_shift_register...
[1] https://en.wikipedia.org/wiki/Primitive_polynomial_(field_th...
[2] https://en.wikipedia.org/wiki/Avalanche_effect
Why aren't such dense polynomials used more often?
Is it that we trade off something in return for less short-term correlation (maybe more long-term correlation)?
I'll be honest, that is a bit terse for a lay-person like me, but the links hopefully give enough pointers to properly grok what you said with a bit of reading. Thank you!
Note: in the software world, the equivalent construction to the LFSR with "fat" polynomial is the xorshift PRNG. For more details, see the book: Numerical Recipes, 3rd edition (not 2nd ed!), Chapter 7 random numbers, section 7.1 uniform RNG - history.