Random Number Generation Circuits

[kc5tja]

In another thread on the characteristics of various flux compounds and the reasons for cleaning, it was detailed that water-soluble flux compounds introduce significant amounts of noise in a circuit.

Quote:

And further, those conductive paths don't act like a quiet resistor, but make a noise like frying bacon in the audio signals we deal with.

It seems to me that a circuit can exploit this characteristic to produce truly random numbers. Random number generation is a surprisingly difficult problem to solve with LFSRs and other algorithms. Amplifying the "frying bacon" effect and passing that to an ADC should work really well for truly random number generation.

[faybs]

I believe one can use Zener diodes to get random numbers like this, however I've never tried it myself.

[ElEctric_EyE]

I've heard this as well...

I'd like to learn more about random number generation. How many bits would it take to truly explore the limits of a chosen random number generator ADC "source"?

[kc5tja]

I don't think that question makes any sense in the context of RNGs. You can use as wide an ADC as you want, or as narrow. I've found a few "1-bit ADCs" (op-amps configured as a comparator) used with zener-based circuits already.

The fewer the bits, of course, the larger the gain you'll want to have.

I think a bigger problem isn't the bit-width, but rather, periodicities on the power supply rails which affects the white noise produced by the zener or flux. This is something I've not thought of before now, but it's something a few websites I've seen mention as concerns.

[ElEctric_EyE]

kc5tja wrote:

....The fewer the bits, of course, the larger the gain you'll want to have...

I am by no means anything close to an analog expert, but more gains/noise into any ADC would imply a pushing of the signal towards the rails thereby negating any randomness as the signal approaches the ADC ref voltage...

Am i wrong here?

[kc5tja]

If the signal is AC balanced and is true white noise, you will receive a random stream of high and low voltages, with varying duty cycles. Noise exhibits the nice property that it's fractal, so the more you amplify, it's still noise.

This property holds only as long as the signal is AC coupled to the amplifier though.

Another approach would be to use an automatic gain control feedback, where the digitized noise is piped back out through a (1-bit) DAC. You know you have the right gain setting when the DAC reports approximately one half its supply voltage.

[PaulF]

I've built a random number generator using this method.

Diode noise (from the reverse-biased base-emitter junction of a BC548) was amplified by an op-amp and then fed into a schmitt-trigger inverter. This fed into a shift register clocked at a constant rate. I then read random numbers from the shift register.

As long as the interval at which the random numbers are read is long enougth for the entire shift register to shift through, the numbers that come out appear to be truely random.

[BigEd]

There are techniques for mixing in new randomness to an existing pool of randomness, and for balancing a biased source so it's 50/50. How much work you do on the raw data depends on what you're trying to achieve. The crucial thing with mixing is that you don't have to arrange for your source to be carefully biased and measured to be full-scale. A voltage which varies between plus and minus 0.1 is just as good as one which varies between 4.8 and 5.0, all else being equal. (It's tempting to take the bottom few bits of a measurement and regard them as random, but mixing is better than that.)

Mixing also means you can take several sources, of different quality or trustworthiness, and always get as much randomness out as was truly in there. (It's tempting to XOR different sources together, but that's not as good.)

I'm not sure how valid a technique it is, but a cheap thing to do is XOR your noisy input byte into one end of your LFSR and take your random bits out the other end.

The other thing is, I'm pretty sure that if you want say 8 random bits, you really need to shift your LFSR 8 times. I think I've seen people shifting once and then taking a byte from it.

[PaulF]

BigEd wrote:

The other thing is, I'm pretty sure that if you want say 8 random bits, you really need to shift your LFSR 8 times. I think I've seen people shifting once and then taking a byte from it.

Very true. If you only do 1 shift, then 7 out of your 8 bits are directly dependant on the previous value read - hardly random!

[ElEctric_EyE]

The shift register w/comparator concept is easier to adapt to a wider data bus too, just need a 16-bit shift register. Cheaper than an 8-bit vs. 16-bit ADC...

So curiosity is getting me again. Instead of a hi-res ADC, now the concept is a hi-speed shift register. How fast can the shift clock be, before it starts repeating bits on that diode source?...

BTW, Excellent info!

[kc5tja]

That I don't know, but I would think that the clock should not be a harmonic of any other nearby clocking signal, and definitely not a harmonic of the CPU's clock. Prime number relationships should probably be used.

[PaulF]

ElEctric_EyE wrote:

How fast can the shift clock be, before it starts repeating bits on that diode source?...

It depends on the bandwidth of the noise source. Diode noise extends up to several hundred MHz but the bandwidth of the following amplifier is likely to be far lower.

In the unit I built, using a standard op-amp, the fastest speed I could run the shift register clock at was 100kHz. Above this speed, the shift register started repeating bits.

If you want to run the shift-register faster, you are going to need a high-bandwidth noise amplifier built using radio-frequency techniques. This is only really necessary if you want to generate random numbers in quick succession.

I used a divided-down CPU clock to clock the shift-register. I didn't notice any patterns caused as a result (although my maths isn't good enougth to do a full analysis and say I had real random numbers...) and the clock synchronisation meant I could simply read the shift register directly instead of through a synchroniser circuit.

[kc5tja]

The issue with clocking doesn't have anything to do with injecting patterns into the bitstream through the shift register. It has to do with voltage ripple (either from supply rail or electromagnetically coupled) influencing the amplifier. The AM-mixing effect it introduces apparently can (depending on how the circuit is laid out, I guess) introduce statistically significant deviations from true-random bit streams.

Concerning speed of random number generation, one approach is to use an analog RNG at 100kHz as a periodic seed for a traditional LFSR. A 32-bit LFSR could be used for, say, 2 billion reads, after with the analog RNG circuit could reseed it for continued randomness.

[Nightmaretony]

For me, a flickering candle circuit trick works. taking 2 to 5 seperate waveform sources then mixing the results together. In the original case, it was an anlog waveform or a digital program version. The same conceptual can be applied to several noise sources mixed?

[kc5tja]

When I worked at Hifn, the 6500[1] chips generated random numbers through multiple LFSRs XOR'ed together, each running at different clock speeds.

_______________
1. Other than it being a microprocessor, it bears no relation at all to the 65xx architecture we're familiar with. The Hifn 6500 was tailor-made to work on line-speed encryption and decryption, sporting a 1024-bit wide ALU and registers, and instructions capable of 3072-bit modular math in only a handful of clock cycles.