Electronic – the smallest and simplest seed for a random number generator

random number

A small microcontroller (8-bit Atmel) controls a number of lights in order to present a light show with many fancy randomized light sequences.

A suitable pseudo-RNG does its job nicely, but I'm looking for a good seed for it. A seed will be necessary because if someone turns multiple such devices on at the same time, it won't look good if they all generated the same sequences of effects until they slowly drift apart due to the tiny differences in their individual clock sources.

A very good method to seed a pseudo-RNG, which I often used, is possible in case of a device which has to be started with the press of a button or flip of a switch. As soon as the µc is powered on, a very fast timer can be started, and the value of this timer seeds the RNG as soon as the button is pressed for the first time.

The problem is, in this scenario, there are no buttons. The program has to start as soon as the device is powered on.

The place on the PCB is extremely limited (nothing more than a few of the very smallest SMD parts might fit), so I'm looking for the smallest and simplest possible solution. Therefore I'll rule out fancy solutions like true RNG hardware, radio receivers, etc.

All I have is a 16 bit timer-counter in the CPU, and an unused portpin which has access to an ADC.

My current solution is to just use a resistor (as inaccurate as possible) to provide approximately half the supply voltage to the ADC pin, and seed the RNG with the first AD conversion value. However, nowadays most 10% resistors have an inaccuracy well under 1% (it would be fun to imagine the face of a supplier when I tell them we want the worst quality SMD resistors they can find), so there is a very high chance of multiple units starting with the same seed.

A better alternative would be to make multiple conversions and build a value out of the least significant bits of these measurements. However, I used the ADC of this µc type before and I know it's very accurate. Running the ADC at the fastest possible speed might help here.

Does anyone have a better suggestion? The seed is not required to be perfectly uniformly distributed, but the more uniform the distribution is, the better. A 16 bit seed with a perfectly uniform distribution would be a dream too good to be true, but I think a halfway decent distribution over 5 or 6 bits might be sufficient.

Best Answer

Put a parallel resistor and capacitor between the A/D pin and ground. Make the resistor fairly high, preferably well above the input signal impedance requirement for the A/D. Make the RC time constant maybe around 10 µs. For example, 100 kΩ and 100 pF sounds like a good combination.

To get a value with some randomness, drive the pin high for a while, then set it to high impedance and take a A/D reading a few µs later. Particularly if you properly abuse the A/D acquisition time, the voltage it will see will be dependent on the R and C values, the pin leakage current, other nearby noise, and temperature.

Grab the low bit or the low two bits and repeat as necessary to get any number of random bits.

For a more random pattern, perform this procedure occasionally and inject the low bit of the A/D result into the random number generator you are already using.