An efficient integer one dimensional dithering function?

Question

I've been playing with LEDs a lot recently, powered by 8-bit micro controllers. Sometimes it's necessary to use purely software implementations of Pulse Width Modulation to control LED brightness - that is turning the light on and off rapidly varying the ratio of time on and off. This works great until I get down to about 5% brightness, where the strobing starts looking uncomfortably flickery to the eye.

Implementing the PWM as a loop, it steps through each number from 0-255 setting the light on or off for that moment. A light which is set at the 20 value will be on for the first 20 loops then turned off.

I'm looking for a good function which will shuffle around those numbers, so instead of looping through 0, 1, 2, 3... my loop could sample semi-randomly from the pool of possibilities. The aggregate brightness over time is the same, but a light at 20 brightness value may switch on and off a dozen or so times spread across 256 loops instead of just lighting once then turning off for most of the loop. This reduces the flickering effect even if the loop runs slightly slower.

A good dithering function would need to return every number in the 8-bit range when called with every 8-bit number. It would therefore also need to produce no duplicate numbers - not random, just shuffled. It's best if it tends not to put similar numbers together in sequence - the difference between each number aught to be high - ideally about 64-127 I figure.

The limitations are also interesting - it's a time critical application. Addition, subtraction, and bitwise operations cost 1 arbitrary unit of time, multiplication costs 2 units, and division costs 4 units. Floats are out of the questions, and the costs roughly double for every multiple of 8 bits used in an intermediate number. Lookup tables are possible, but would use roughly half of the total memory capacity of the device - so fast algorithms are best for reusability, but good quality slow algorithms are also very useful when there's space to precompute.

Thanks for helping me out with any ideas or musings. :)

Answer 1

Not 100% sure I understand correctly, but basically I think that any numbers that doesn't divide 256 will generate the group of numbers 0..255 if you just keep adding it to itself modulo 256. Some flashbacks from the abstract algebra class...

like this:

s = {}

n = 157
for i in range(0, 256):
   s[n] = True
   print n
   n += 157
   n %= 256

print "check: has to be 256: ", len(s) 

EDIT: replaced small generator with a larger one to make the distribution more "random".

Answer 2

Example: Using a phase accumulator for 5 bit dither within an 8 bit register, where duty = 1 to 31 [% = duty / (1 << bits)].

// Easier to do in assembly, where there is access to the carry flag
unsigned bits = 5;  // states = 1 << bits
unsigned carry = 7; // keep carry bit within an 8 bit register, limits bits
unsigned frq = ((1 << carry) * duty) / (1 << bits); // More than 8 bit intermediate value
unsigned phs = 0;
for (i = 0; i < (1 << bits); i++) {
    phs += frq;  // Carry is high bit
    output((phs >> carry) & 1);  // Output carry
    phs &= (1 << carry) - 1;  // Discard carry
}

The dither patterns look like:

00: 00000000000000000000000000000000
01: 00000000000000000000000000000001
02: 00000000000000010000000000000001
03: 00000000001000000000010000000001
04: 00000001000000010000000100000001
05: 00000010000010000001000001000001
06: 00000100001000010000010000100001
07: 00001000010001000010001000010001
08: 00010001000100010001000100010001
09: 00010001001000100100010010001001
10: 00010010010010010001001001001001
11: 00100100100100100100100100100101
12: 00100101001001010010010100100101
13: 00101001010010100101001010010101
14: 00101010010101010010101001010101
15: 00101010101010100101010101010101
16: 01010101010101010101010101010101
17: 01010101010101011010101010101011
18: 01010101101010110101010110101011
19: 01010110101101011010110101101011
20: 01011011010110110101101101011011
21: 01011011011011011011011011011011
22: 01101101101101110110110110110111
23: 01101110110111011011101101110111
24: 01110111011101110111011101110111
25: 01110111101110111101110111101111
26: 01111011110111110111101111011111
27: 01111101111101111110111110111111
28: 01111111011111110111111101111111
29: 01111111110111111111101111111111
30: 01111111111111110111111111111111
31: 01111111111111111111111111111111

frq may need to be calculated in a loop one bit at a time if you don't have wide enough integers (or in assembler when there is no multiply nor divide).

Optionally the dither patterns can be pre-calculated and coded as constants in a look-up table.

Only the patterns for powers of two have no noise; this won't matter unless you are doing audio or RF synthesis. Otherwise the other patterns have birdies. Scrambling the order of pattern bits after outputting a pattern once would add noise, but remove the birdies. A LFSR function with a long repetition period that doesn't add nor remove bits (number of ones and zeros remains the same, just their order changes) could be used to do this.

Note that to output a complete pattern at 60 Hz frame rate requires a dither frequency of 60 Hz * (1 << bits) = 1.92 kHz. Probably can get away with much lower dither frequency for LED without flicker, like (1 << bits) = 32 Hz. Experiment!