Hacker News Reader

Comment by linuxlizard | Hacker News Reader

Back when I worked at Marvell Semiconductor (circa 2005), we made laser printer ASICs for HP. We did a lot of dithering in hardware. We had a hardware block that did error diffusion, we had a hardware block that did regular diffusion. We also had a hardware block that did Blue Noise. I was responsible for implementing the firmware that drove those printers' scan/copy path: scan an image in monochrome, run through the dither hardware to create the bit pattern fed to the laser engine.

No one could explain to me how to use the blue noise block. I couldn't understand what the blue noise block was doing. This is the first article that explained, in terms I could understand, how blue noise dithering works.

I can die happy. Thank you.

View on HN

This is a lovely compliment. Thank you for taking the time to write it :)

Thank you for such a great blog post that even years later, I could catch up and understand!

(We never did turn on the blue noise block. Even today, it sits idle. Sad.)

Folks interested in learning more about dithering in genreal or blue noise dithering in particular should read Bart Wronski's blog posts here:

https://bartwronski.com/2016/10/30/dithering-in-games-mini-s...

Now that's amazing. Not only because it was hardware based, but because you were solving a real problem, a limitation, instead of just aesthetic endeavor. It was an engineering solution. There is a lot of aesthetic beauty in mundane engineering, rarely seen by anyone. So kudos to designers to pick out something interesting and giving it the light :) It's all cool.

There is no math.Random() in hardware, so I have to ask: what algorithm did the noise block use? :)

Not the OP, but since repeatability is not a problem you can just use any cheap and insecure random number generator and hardcode a constant for the seed.

The period needs to be sufficiently long such that it won’t show up as visible artifacts. I would think something like PRBS23 would do the trick and be trivial to implement.

That’s the cheapest choice. Better whiteness could come with some added complexity.

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.

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

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.

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)?

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.

Well, LFSR RNG-s are pretty efficient in terms of HW space. You take a single-bit wide shift registers of length n, and feed back its output to the beginning XOR-ed with predefined bits in the shift register.

We had to generate values in firmware then populate a LUT. IIRC we just used a simple pseudo-random number generator from the C library. Non-crypto so it didn't matter too much.

Reply on news.ycombinator.com