It occurs that a noise source feeding an ADC would not be a good random number generator. WHite noise does not have an even spread of amplitude vs probability, it is actually a gausian curve - with the probability of a specific amplitude being greatest when the desired amplitude is zero and reducing in a bell-shaped curve as the desired amplitude gets further away from zero.
If you amplify this noise, it gets limited at the ends of the ADC range, increasing the probability of these two values comming out of the ADC at the expense of all the other values.
Either way, a noise source feeding an ADC is unlikely to create a good random number generator.
Squaring off the noise and then either counting it or feeding it into a shift register gives better randomness, since then it is only the frequency of the noise that matters, not its amplitude. As long as you don't try and read the squared signal at too high a frequency, the result is a fairly good random number generator.
Random Number Generation Circuits
-
leeeeee
- In Memoriam
- Posts: 347
- Joined: 30 Aug 2002
- Location: UK
- Contact:
Leeeeee said that TV uses negative modulation, with no signal being white and peak signal being sync, which is "blacker than black." Thus, the noise tends to produce more white than black.
I suspect the effect comes about because of the biasing of the stages that follow the video detector - in the absence of a signal these stages arn't biased to black but to a partially lit screen. Thus the most common noise voltages produce a lit screen with brighter areas and dark areas (the noise peaks) being less common.
I suspect the effect comes about because of the biasing of the stages that follow the video detector - in the absence of a signal these stages arn't biased to black but to a partially lit screen. Thus the most common noise voltages produce a lit screen with brighter areas and dark areas (the noise peaks) being less common.
Shift to the left,
Shift to the right,
Mask in, Mask Out,
BYTE! BYTE! BYTE!
Shift to the right,
Mask in, Mask Out,
BYTE! BYTE! BYTE!
PaulF wrote:
Leeeeee said that TV uses negative modulation, with no signal being white and peak signal being sync, which is "blacker than black." Thus, the noise tends to produce more white than black.
-
ElEctric_EyE
- Posts: 3260
- Joined: 02 Mar 2009
- Location: OH, USA
Re:
PaulF wrote:
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 enough for the entire shift register to shift through, the numbers that come out appear to be truely random.
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 enough for the entire shift register to shift through, the numbers that come out appear to be truely random.
I would like to incorporate it into the next version of my video project.
Currently, the pseudo-RNG I am using is too predictable and also taking up some resources in the FPGA.
An internal shifter register would be all I need, at the cost of a few external components which I'm willing to add for a closer shot at true randomness.
Re: Random Number Generation Circuits
As a collage project I've built a random generator circuit of my own, and implemented it in tsmc 0.18 um topology, and made simulations in LT spice(which took forever on my pc).
I even built a prototype using only 4000 series IC, and it works.
The idea was using a pair of oscillators made out of inverters, but with extra xor gates that could invert the oscillators phase at any moment, and what I did is to take the output of one oscillator and use it to invert the phase of the next, and then I made such a ring of four of those, and had two such pairs. The end result got xor-ed, and fed into a sorta LFSR for a few cycles, and the output then is latched to a 8 bit latch. The 4000 series prototype could generate 12000 bytes per sec @5V and 24k @12V. The chip simulation was much faster.
I've made a schematic in Eagle later, but it is hopeless to try to fit the circuit on the board, even the auto router can't figure it out.
I've included the original documentation(you will need to use google translate if you want to read it, I didn't translate it yet) and the eagle files.
I did get a good grade for this project, but I've never tested the thing properly with the random testing algorithms, but I see no reason why it shouldn't pass them.
Edit: I've made the circuit interface so that it would nicely fit on the 68/65xx bus(or any other cpu bus).
I even built a prototype using only 4000 series IC, and it works.
The idea was using a pair of oscillators made out of inverters, but with extra xor gates that could invert the oscillators phase at any moment, and what I did is to take the output of one oscillator and use it to invert the phase of the next, and then I made such a ring of four of those, and had two such pairs. The end result got xor-ed, and fed into a sorta LFSR for a few cycles, and the output then is latched to a 8 bit latch. The 4000 series prototype could generate 12000 bytes per sec @5V and 24k @12V. The chip simulation was much faster.
I've made a schematic in Eagle later, but it is hopeless to try to fit the circuit on the board, even the auto router can't figure it out.
I've included the original documentation(you will need to use google translate if you want to read it, I didn't translate it yet) and the eagle files.
I did get a good grade for this project, but I've never tested the thing properly with the random testing algorithms, but I see no reason why it shouldn't pass them.
Edit: I've made the circuit interface so that it would nicely fit on the 68/65xx bus(or any other cpu bus).
- Attachments
-
- rndgen_col_project.zip
- (2.75 MiB) Downloaded 83 times
Re: Random Number Generation Circuits
Is there any way it could get stuck at all-zeros or all-ones, or some short repeating pattern? Did you check that the output is 50/50 between 0 and 1? That's the simplest possible test!
Cheers
Ed
Cheers
Ed
-
GARTHWILSON
- Forum Moderator
- Posts: 8775
- Joined: 30 Aug 2002
- Location: Southern California
- Contact:
Re: Random Number Generation Circuits
Quote:
even the auto router can't figure it out.
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?
Re: Random Number Generation Circuits
BigEd wrote:
Is there any way it could get stuck at all-zeros or all-ones, or some short repeating pattern? Did you check that the output is 50/50 between 0 and 1? That's the simplest possible test!
Cheers
Ed
Cheers
Ed
Re: Random Number Generation Circuits
Certainly sounds good enough for hobby purposes!
Cheers
Ed
Cheers
Ed
Re: Random Number Generation Circuits
It's curious that, after a solid 3 minutes on Google, there isn't a dedicated RNG chip out there. Apparently many chips, CPUs notably, have RNGs embedded on them, but there doesn't seem to be any standalone ones. You'd think they'd be able to put one in a 8 pin chip. I guess the demand isn't there, or they bury them for security purposes (doesn't help if your RNG can be replaced with a trace cut and fed what you want to it).
Re: Random Number Generation Circuits
A cryptographically secure random number generator is very hard to get right, especially in a stand alone chip.
For non-cryptographic purposes, a simple pseudo random generator usually doesn't need a stand alone chip.
For non-cryptographic purposes, a simple pseudo random generator usually doesn't need a stand alone chip.
Re: Random Number Generation Circuits
I think perhaps the SID and indeed the Beeb's sound chip contain PRNGs but they are no use to the CPU. A CPLD would be big enough.