4 ms·

For less visual artifacts it is recommended to use PRBS with 50% of the taps 0, 50% of the primitive polynomial tap 1. Same period (2^n-1), but less short-term

For less visual artifacts it is recommended to use PRBS with 50% of the taps 0, 50% of the primitive polynomial tap 1. Same period (2^n-1), but less short-term correlations.

vanderZwan 6y ago
I have no idea what those parameters represent, but I'm very curious! Could you give a layman's explanation?
- darusnna 6y ago
  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#Some_polynomials_for_maximal_LFSRs https://en.wikipedia.org/wiki/Linear-feedback_shift_register... [1] https://en.wikipedia.org/wiki/Primitive_polynomial_(field_theory) https://en.wikipedia.org/wiki/Primitive_polynomial_(field_th... [2] https://en.wikipedia.org/wiki/Avalanche_effect https://en.wikipedia.org/wiki/Avalanche_effect
  - vanderZwan 6y ago
    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!
    - darusnna 6y ago
      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.
  - rathel 6y ago
    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)?
linuxlizard 6y ago
The great thing ("great") was we did the lower end laser printer niche for HP. We were able to make ASICs cheaper than HP could make them for themselves. So we had the (cough) less impressive hardware (scan sensors, laser engines, motors) to work with. So image quality was so-so at even the best of times. We were able to bury a lot of bodies under the sensor noise and engine output. But we made a super reliable, super cheap laser printer -- VW Bug of Laser Printers, if I may brag a bit. Twelve years later, the M1005 is still selling like hotcakes I hear.

For less visual artifacts it is recommended to use PRBS with 50% of the taps 0, 50% of the primitive polynomial tap 1. Same period (2^n-1), but less short-term correlations.

vanderZwan 6y ago

I have no idea what those parameters represent, but I'm very curious! Could you give a layman's explanation?

darusnna 6y ago
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#Some_polynomials_for_maximal_LFSRs https://en.wikipedia.org/wiki/Linear-feedback_shift_register... [1] https://en.wikipedia.org/wiki/Primitive_polynomial_(field_theory) https://en.wikipedia.org/wiki/Primitive_polynomial_(field_th... [2] https://en.wikipedia.org/wiki/Avalanche_effect https://en.wikipedia.org/wiki/Avalanche_effect
- vanderZwan 6y ago
  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!
  - darusnna 6y ago
    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.
- rathel 6y ago
  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)?

linuxlizard 6y ago

The great thing ("great") was we did the lower end laser printer niche for HP. We were able to make ASICs cheaper than HP could make them for themselves. So we had the (cough) less impressive hardware (scan sensors, laser engines, motors) to work with. So image quality was so-so at even the best of times. We were able to bury a lot of bodies under the sensor noise and engine output. But we made a super reliable, super cheap laser printer -- VW Bug of Laser Printers, if I may brag a bit. Twelve years later, the M1005 is still selling like hotcakes I hear.