What is the smallest and simplest seed for a random number generator?

Question

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.

Answer 1

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.

Answer 2

Some possible options:

1. Pre-program a unique serial address for each device. If you have a good enough RNG algorithm, then even a sequential list of serial addresses will produce wildly different results.

2. Depending on your MCU/setup, you might have two different clock sources available for the system clock and the watchdog timer/timer counter input. If one/both of these have significant variance, you can use this to generate a suitably different seed. Here is an example I wrote which uses an Arduino's internal watchdog timer and an external XTAL system clock.

3. Use a BJT transistor and build a highly beta dependent amplifier. This can be read from an ADC for the seed.

4. Capacitors/inductors are typically specified to a much worse tolerance than resistors. You could build some kind of filter circuit (RC, RL, LC) with these and measure the output with the ADC.

Answer 3

Uninitialized memory

You could try to use the uninitialized memory in the micro controller. The trick is to find the bits that have the most 'balanced' flip-flops, and are actually random. The procedure is to read all the memory, reset, and repeat a few times to measure which bits are truly random. Then you use this map to read out enough random bits to seed your PRNG or LFSR!

This method should give you random seeds, even with identical hardware, more details (and links) are available in this hack-a-day article

I like this method because it doesn't require any additional circuitry or pins; your AVR already has ram, you just need to find the unstable (random) bits. Also the mapping procedure could be automated; you can apply the same code and procedure to each device, and have truly random results!

Answer 4

What I did for a MP3 player with random capability is to just use a different sequential seed at every power on. I started at 1 and stored this in the EEPROM so that at the next power cycle I used 2 etc. This was on an ATMEGA168. As helloworld922 noted even a simple sequential seed will generate completely different pseudo random sequences.

I used one of the linear congruent random sequence generators, this gives a uniform distribution.

int i;
seed = seed * 2053 + 13849;
i = (seed % max) + 1;  // max is the maximum value I want out of the function

Of course if you want multiple units to have different sequences even though they may have had the same number of power cycles then you need something to start out randomly.

This could be done by any of the methods proposed by the other posters - One method I can think of could use the AC zero crossing going into the processor if you have it (for lamp phase control for example)? This could be used to sample the timer on the first crossing following power-up and then used as the seed.

Are there any push-buttons on the unit to select mode etc? If so you can sample the counter the very first time the button is pushed after the MCU is programmed you can generate a random seed initially and store it in EEPROM. Every Power-up after this point would use the stored seed.

Answer 5

An ADC is a very good source for randomness.

You do not need to rely on resistor tolerances. Any resistor will generate thermal noise, and the same physical effect will introduce noise into the ADC when doing all the sampling and conversion steps. (The datasheet will tell you about the amount of noise, and what configuration settings are worst/best.)

You should not leave the ADC pin floating; this might let the voltage float too far, and risks saturating the input.
(Many MCUs allow you to use something like half of the supply voltage as an ADC input, for calibration. This saves the external resistor, and still gives you noise. Again, see the datasheet for the worst/best configuration.)

You do not need to rely on a single ADC measurement; you can combine multiple measurements with a simple hash or checksum function (CRC would suffice). If you need to start using the RNG immediately, you can later combine the ADC result with the current RNG seed.

Answer 6

Can you save the seed from session to session? If so, is it feasible to turn every unit on for some random time period upon creation? That way all the units will be shipped with preset seeds that are unlikely to be the same.

Another thought: How do you link multiple units together so they turn on simultaneously? If they're in series, add some kind of capacitor so the (n+1)th device starts a few clock cycles after the nth device. Ideally, capacitors would discharge very rapidly on device shutdown, so every start/restart there's a larger gap between the sequences.

If they're in parallel, you could still randomize the start-up time a bit. I assume there's some kind of power filtration using capacitors. If so, fabricating the devices with slightly different filtration circuits would cause each device to start at a slightly different time, causing divergence after several restarts.

A variation on this is to add variance to your clock signals if possible. A 0.1% difference in clock speed might have little impact on the light show, while changing the rate you traverse the PRNG table pretty quickly.

Answer 7

If you running on internal "calibrated" clock source. Could you not save a seed after some time, preferable into the EEPROM. The clock will drift, and it will differ from unit to unit. To save a new value after some time again (maybe each 10 minute or so, or after a time that is short enough to occur within the normal on-time for the device. The longer the device is on, the more likely it will save a "different" value into the EEPROM.

Also take a leap once every now and then (not to often) and reseed while device is on (save this new value in EEPROM).

Answer 8

What about extendinging your original idea of AD converting based on a varying resistor by adding a LDR or thermistor? (The first would need to be able to "look" outside, I don't know if that's feasible; but the variation in light may be higher than the variation in temperature among devices started at about the same time in about the same place ...)

Answer 9

Abuse ADC bandgap reference stabilization

Another way I have successfully used at program startup (atMega series) that doesn't use any external pins (permanently) is abusing the following fact from the datasheet (in this case 1284P):

A normal conversion takes 13 ADC clock cycles. The first conversion after the ADC is switched on (ADEN in ADCSRA is set) takes 25 ADC clock cycles in order to initialize the analog circuitry. When the bandgap reference voltage is used as input to the ADC, it will take a certain time for the voltage to stabilize. If not stabilized, the first value read after the first conversion may be wrong.

Emphasis added.

So at program start

• Shut down the ADC
• Wait a few clock cycles
• Initialize ADC
• Immediately read a value while the reference has not stabilized
• Combine with solutions mentioned above, like repeating 16 times and shifting, etc...

Answer 10

2 potential solutions, both assuming you need a unique seed per unit.

1. If you flash your units one by one in the factory, The hex file can be programmatically modified by some intermediate script in the programmer. If it is pc controlled, you can overwrite a variable initialisation with the date and time. Guaranteed to be unique for each unit!

2. Dallas 1 wire devices use only one pin and each come with a unique 64 bit serial number. You can use this as the seed.

Answer 11

You can leave a floating ADC pin to feed the random number generator (RNG) with captured noise. It should be enough to generate a seed or even use it as the RNG generator.

Don't forget to use the minimum possible conversion time.

The other solution could be a noise generator applied into the ADC pin.