Random number generator gizmo
Simon Booth
I'm after getting a gizmo built for me which will produce truly random
numbers.
I understand that, at least one upon a time if not now, ERNIE (the UK
premium bonds number picking machine) used some kind of (gonna make a prat
of myself here) leaky diode or something which produced truly random
numbers.
The random numbers produced by programming languages aren't really random.
If you feed in a seed number the next number generated wil *always* be the
same as such algorithms use a mathematical routine which although seemingly
random is actually predictable - and that's *exactly* what I don't want.
This gizmo has to interface to a PC somehow or another, it can be a standard
PCI or ISA card or it can transfer information by serial / parallel / USB -
anything fairly common will do.
It's got to generate numbers at quite a rate (the faster the better)
The numbers only need to be eight bit bytes, or even a bit stream will
suffice. Just as long as it's truly random.
Anyone able to help?
John Stephens
the random number generator with a random seed. This seed number is usually
derived from one of the inbuilt timers. Since this timer has been incrementing
at a very fast rate since the computer was turned on the chances of of starting
with the same seed is almost zilch.
Alternately you can have a fast incrementing loop in your program that is read
on 'random' event such as any mouse click or keypress.
For an electronic solution you can use a noisy transistor, diode, or just
atmospheric noise from an AM radio tuned off station.
Hope this helps.
----------------------------------------------------------------------
Bob Camp
One fairly simple way is to feed random noise into the input of a
sound card. One common example of random noise is a radio tuned to an
empty channel. That assumes of course that the radio is not set up
with a gizmo that disables the output when the channel is empty.
Another example is a noise diode.
Any audio recording program (like the one built into Windows) will
grab the data from the sound card. Generally you use a few bits from
each sample but that still gives you a lot of random numbers pretty
fast.
The results are only as good as you make them. There are still sources
of non-random behavior even in this kind of system. In order to be
*sure* the result is random you would need to do fairly extensive
analysis on the resulting data sets.
Don't know if that helps or makes it all more confusing.
Bob Camp
"Simon Booth" <simon...@btclick.com> wrote in message
news:MFJw7.5992$U97.15853@NewsReader...
John Larkin
This issue has been extensively thrashed in a number of ng's and web
sites. The jist is that there are various quality levels of random
numbers, and the very best - those remaining random under extensive
statistical analysis - are rather hard to generate.
A zener diode generates pretty good noise - a 12 volt zener at 1 mA
will make around 300 nV per root hertz (ie, 300 nV * sqrt of amplifier
bandwidth) but will have low frequency components, 1/0 asymmetries,
etc. Zener noise stirred into a pseudo-random linear shift register
can be pretty good.
Zener --> wideband AC amp --> zero crossing comparator --> PN shift
register. Maybe not crypto quality, but pretty good.
John
grog
How about white noise into the serial port.
FM radio tuned off station, speaker output (perhaps current/voltage limited)
into the RS232 receive. Embellish the design as required. Level clipping,
Schmitt logic for nicer edges, etc, etc..
Baud rate will determine how fast the numbers come out. Expect a few Framing
and over-run errors. This may be a software issue as I think windows will
generate the error events and not give the received byte event because it
has been deemed a crap byte. Probably easier to do on a small
microcontroller (PIC/AVR etc..w/UART) and sent to a PC up the serial port,
if that's where it needs to go.
Perhaps XOR a couple together or use the number as Randomize seed for
computer generated number.
Something like that anyway..
Be well,
Greg the Grog
"Simon Booth" <simon...@btclick.com> wrote in message
news:MFJw7.5992$U97.15853@NewsReader...
Mike
"John Stephens" <no_spam.j...@qut.edu.au> wrote in message
news:3BC388AB...@qut.edu.au...
> For an electronic solution you can use a noisy transistor, diode, or just
> atmospheric noise from an AM radio tuned off station.
Those electronic noise sources you cite need to be considered carefully, or
you'll end up with big problems. Atmospheric noise, especially as presented
at the speaker terminals of a radio, can be very non-white. The generated
electronic noise can have large 1/f components, and it's highly filtered by
the radio. The independence of samples becomes a strong function of the
sample rate, and the distribution of those samples can be much different
than you expect. If Simon's going to try to generate samples at "quite a
rate (the faster the better)," he would be well advised to avoid a noise
source that is likely to exhibit high correlation at sample rates above a
few kilohertz.
-- Mike --
Mike
"John Larkin" <jjla...@highlandSNIPTHIStechnology.com> wrote in message
news:a6fDO6AOqPYuzh...@4ax.com...
> A zener diode generates pretty good noise - a 12 volt zener at 1 mA
> will make around 300 nV per root hertz (ie, 300 nV * sqrt of amplifier
> bandwidth) but will have low frequency components, 1/0 asymmetries,
> etc. Zener noise stirred into a pseudo-random linear shift register
> can be pretty good.
>
> Zener --> wideband AC amp --> zero crossing comparator --> PN shift
> register. Maybe not crypto quality, but pretty good.
I'm not sure that the LFSR changes anything. It seems to me that you're just
convolving the zener noise sequence with the LFSR sequence. If that's the
case, then you're just multiplying the Fourier transforms. If the LFSR
spectrum is relatively white, then you're preserving the colored spectrum of
the zener. In any event, the only way the result turns out white is if the
LFSR and zener have spectra that multiply to a constant at all frequenies of
interest.
-- Mike --
Simon Booth
lack of knowledge on the subject but...
I don't think the whiteness if the noise is a real concern. Just the
non-predictability. The thing is that I want *lots* of non-predictable data,
looking at 1/2 a gig per run to start with, possibly quite a bit more later
on - hence the speed requirement.
An example of the speed issue for the 'quite a bit more' scenario is if the
data were later cut to a DVD - producing 4.7 GB via the oft cited radio
plugged into my soundcard would take about 7.25 hours, and that's keeping
all the data. Increasing the data rate by an order of magnitude puts things
in the realm of the managable.
I've had the suggestion of buying a high speed DAC of some sort, I don't
have the $5k spare to try that path though.
I thought the answer here was going to be somewhat simpler (diode and some
other bits connected to some PC interface method or something like that)
"Mike" <mi...@nospam.com> wrote in message
news:a6Rw7.38421$8a.21...@news1.rsm1.occa.home.com...
John Woodgate
<simon...@btclick.com> wrote (in <MFJw7.5992$U97.15853@NewsReader>)
about 'Random number generator gizmo', on Tue, 9 Oct 2001:
>I understand that, at least one upon a time if not now, ERNIE (the UK
>premium bonds number picking machine) used some kind of (gonna make a prat
>of myself here) leaky diode or something which produced truly random
>numbers.
Run two 12 V zener diodes at a few mA each. Couple the diode positive
terminals to the two inputs of an op-amp arranged as a differential-
input amplifier. This gets you good quality Gaussian white noise. Feed
the op-amp output to an A/D.
--
Regards, John Woodgate, OOO - Own Opinions Only. http://www.jmwa.demon.co.uk
Eat mink and be dreary!
Andrew
Regards:
Andrew.
--------------------------------------------------------------------------
This Message is the private opinion, suggestion or question of the
sender and does not represent the views of Jupiters Technology.
--------------------------------------------------------------------------
Bill Sloman
>On Tue, 9 Oct 2001 22:08:26 +0100, "Simon Booth"
Two minor points. One is that the "zener" diode has to be an avalanche
diode.
The Zener breakdown mechanism is only dominant for breakdown voltages
up to about 5V, and the breakdown mechanism in higher voltage diodes
includes an increasing proportion of avalanche multiplication, which
becomes the dominant mechanism for breakdown voltages above about 8V.
Avalanche multiplication is much noisier than Zener breakdown. It is
incredibly localised, and very fast - somewhere around one femtosecond
per multiplication IIRR, so your 1mA represents about six electrons
going through the process at any one time. Multiplication is a random
process, so there is one chance in 64 that none of the electrons
actually succeed in generating a new pair of charge carriers, which
briefly interrupts the current, which is where your noise comes from
at high currents.
The other point is that Motorola's zener diode applications book
recommended a slightly lower current - about 100uA - for a "zener"
diode being used as a noise source.
We had a thread on this at the end of 1997 - search on "Zener Diode
Oscillation" - where Tony Williams and Win Hill posted some
interesting measurements, and Win and I dug up some interesting old
papers.
Win's Motorola (ON Semiconductor) diodes behaved a bit differently
from Tony Williams' Philips parts. I'm inclined to suspect that this
may be due to differences in optical feedback - avalanche
multiplication generates light, and the zener junction can act as a
photodiode ...
---
Bill Sloman, Nijmegen
Mike
> I'm probably going to make a prat of myself again here and show my extreme
> lack of knowledge on the subject but...
>
> I don't think the whiteness if the noise is a real concern. Just the
> non-predictability. The thing is that I want *lots* of non-predictable
data,
> looking at 1/2 a gig per run to start with, possibly quite a bit more
later
> on - hence the speed requirement.
White <--> unpredictable.
Colored noise is in some sense predictable. Whether or not that's a problem
depends on what you're doing.
As an example, consider white noise fed into an integrator. The integrator
output is a continuous time random walk process (a Weiner process). It's
easy to see that since the integrator output is the sum of all past inputs
as well as the current input, the output at time t + dt is the output at
time t plus the additional integration over time dt. For small values of dt,
the output is highly correlated. In the frequency domain, the white noise
spectrum at the integrator input becomes a 1/f^2 spectrum at the integrator
output (we're talking power spectrum here; that's why it's a 1/f^2 spectrum
instead of 1/f).
Another example is low pass filtering the white noise. In this case, the low
pass filter effectively limits how quickly the output can change. Over a
long time interval, the filter output is uncorrelated, but over a short
enough time period, the filter output has a limited frequency response, and
can only change by a small amount, and is again highly correlated. Another
way to look at this is this: at frequencies above the cutoff frequency, a
single pole filter looks like an integrator. Below the cutoff frequency, it
has no effect. As long as the sample rate is lower than the filter cutoff
frequency, the samples will be uncorrelated. If the sample rate exceeds the
filter cutoff frequency, the samples will be correlated in the same way that
they were at the integrator output.
Semiconductors tend to exhibit thermal noise, which you can probably think
of as effectively white, as well as various amounts of 1/f and 1/f^2 noise.
The 1/f noise has less correlation than an integrator, but it's not
uncorrelated.
I think the primary effect of this in your case will be that the faster you
sample, the more successive samples are correlated with each other. As you
sample faster and faster, samples are correlated over a longer sequence
length.
> I thought the answer here was going to be somewhat simpler (diode and some
> other bits connected to some PC interface method or something like that)
That may very well work, but if the randomness of your noise is critical,
you should test your data before assuming that it's white. Since it's going
to be in a digital form, you could run an autocorrelation to test for
closely spaced sample dependencies.
Since your data is in the form of samples, you could conceivably shuffle the
samples to remove correlation. I don't know what a random shuffling process
would look like in the frequency domain, so I can't offer any method or
guarantee that it would work. Shuffling is a pretty common process, though
(and God knows, statisticians have spent way too much time analyzing card
games), so I'm sure someone has analyzed algorithms and shuffling processes.
-- Mike --
John Larkin
Mike,
what I had in mind was xor'ing the sliced zener noise *into* some
point in a PN shift register. This results in random jumps of the
otherwise predictable PN state sequence. The result should be perfect
1/0 symmetry and washout of low-frequency autocorrelations and other
zener artifacts. It should have the same spectral properties of a
plain PN sequence, except it would never repeat. This would just be a
cheap way to clean up zener-generated noise.
One could also just xor the zener datastream with a PN sequence, but,
at least at the 'crypto' level, traces of the PN sequence would still
be discernable to some extent.
John
John Larkin
wrote:
My limited experimenting with zener noise sources indicated that some
diodes actually go into a noisy sawtooth oscillation mode at low
currents, phasing into asymmetric noise, then pretty gaussian-looking
noise as current increases. I suspect diodes grown specifically as RF
noise diodes behave better at low currents... maybe tiny junctions
keep up the current density or something. For a 12-volt, 1N759-type
part, 1 mA seemed pretty safe.
John
John Larkin
<simon...@btclick.com> wrote:
>I'm probably going to make a prat of myself again here and show my extreme
>lack of knowledge on the subject but...
>
>I don't think the whiteness if the noise is a real concern. Just the
>non-predictability. The thing is that I want *lots* of non-predictable data,
>looking at 1/2 a gig per run to start with, possibly quite a bit more later
>on - hence the speed requirement.
>
>An example of the speed issue for the 'quite a bit more' scenario is if the
>data were later cut to a DVD - producing 4.7 GB via the oft cited radio
>plugged into my soundcard would take about 7.25 hours, and that's keeping
>all the data. Increasing the data rate by an order of magnitude puts things
>in the realm of the managable.
>
>I've had the suggestion of buying a high speed DAC of some sort, I don't
>have the $5k spare to try that path though.
>
Simon,
what are you doing here? Sounds like one-time-pad crypto, maybe.
John
>I thought the answer here was going to be somewhat simpler (diode and some
>other bits connected to some PC interface method or something like that)
>
Actually, it could be this simple. Zener-amplifier-comparator into a
parallel port bit, or even a very simple zener circuit into a sound
card mike input.
John
John Woodgate
<j...@jmwa.demon.co.uk> wrote (in <3vDoNXAY...@jmwa.demon.co.uk>)
about 'Random number generator gizmo', on Wed, 10 Oct 2001:
>I read in sci.electronics.design that Simon Booth
><simon...@btclick.com> wrote (in <MFJw7.5992$U97.15853@NewsReader>)
>about 'Random number generator gizmo', on Tue, 9 Oct 2001:
>>I understand that, at least one upon a time if not now, ERNIE (the UK
>>premium bonds number picking machine) used some kind of (gonna make a prat
>>of myself here) leaky diode or something which produced truly random
>>numbers.
>
>Run two 12 V zener diodes at a few mA each. Couple the diode positive
>terminals to the two inputs of an op-amp arranged as a differential-
>input amplifier. This gets you good quality Gaussian white noise. Feed
>the op-amp output to an A/D.
I don't know why this post took so long to appear. You needn't take my
word for the truth of it, it was invented by Bruel and Kjaer a long time
ago and what they don't know about noise isn't necessary to know.
I've used it for an analogue video noise source and the noise came out
flat to well above 5 MHz on the spectrum analyser, using the old NE592
video amp.
Mike
"John Larkin" <jjla...@highlandSNIPTHIStechnology.com> wrote in message
John,
I ran some simulations today, fully expecting that I'd prove you wrong. That
wasn't the case though, and it didn't matter whether I XOR'd the noise into
the LFSR or just XOR'd the LFSR output with the noise.
I generated correlated noise by generating a sequence of normal random
variables, then filtering it with the function
y(k) = x(k) + alpha*y(k-1)
If alpha = 1, this is an integrator, but if we set alpha < 1, we get
correlation over a number of samples. The closer alpha is to 1, the longer
the correlation lasts (if it's greater than 1, of course, the system is
unstable). I set alpha = 0.9 or so.
Then, I XOR y(k) with the output of the LFSR, r(k) which uses a 1 + x^7 +
x^10 equation
z(k) = r(k) XOR y(k)
I looked at the autocorrelation and power spectrum of y and z. y clearly
showed lasting correlation effects, and a frequency dependent rolloff. z
showed no correlation effects, and no low frequency rolloff.
As I mentioned, I also tried XORing y(k) directly into the LFSR, but the
results were identical. y(k) clearly showed correlation effects, and z(k)
did not show any discernable effects.
The tests I ran weren't particularly exhaustive, but they certainly showed a
remarkable change in the noise characteristics.
After my tests today, it appears that my intuition was wrong (I should have
known... my intuition is almost always wrong when it comes to statistics),
and your suggestion seems to be a pretty good way to randomize the
correlation effects.
One thing I didn't test was the LFSR sequence length vs the correlation
length. I would speculate about that, but I'd be using my intuition, and
that's not getting me too far here...
-- Mike --
John Larkin
Mike,
I think (and I'm using *my* intuition here!) there will be subtle
differences in how the xor is done. If the zener data is xor'd with
the output of the shift reg, low frequency components in the zener
noise will very slightly 'reveal' the underlying PN sequence, which
could be fished out by massive analysis. If xor'd inside, the register
jumps states, which is 'noisier'. As a practical matter, probably
zilch.
Incidentally, the amplifier that follows the zener (its bandwidth,
rolloff, and noise) are very important here too. This amp can be a
major contributor to autocorrelation of the zener noise sequence.
But wars have been literally lost by people using their intuition
about things like this. The big mistake the Germans and Japanese made
was "if it's so confusing that *I* can't understand it, it must be
random".
John
Mike
"John Larkin" <jjla...@highlandSNIPTHIStechnology.com> wrote in message
John,
Well, I tried things both ways this evening, and regardless of the sequence
length, or amount of correlation, I'm unable to see any significant
statistical difference between the two methods. Maybe there is one, but like
you say, for practical purposes, it may not be significant.
Another thing has occurred to me, though. You mentioned problems with
popcorn noise a couple weeks ago. I've been looking at popcorn noise, mainly
because there's a relatively large contingent of folks who think that 1/f
noise in modern MOS devices may in fact be a sum of popcorn noise processes,
related to electron capture and emission (and related threshold voltage
modulation) at the oxide-channel interface. If that's the case, or if
something like that existed in the noise generator Simon chose, then
(intuitively, unfortunately), I could imagine that there may be a difference
in the results.
As an aside, if the flicker noise <-> popcorn noise thesis is correct, then
there may be nothing you can do about the popcorn noise, and it might be
related more to the crystal structure and the extremely small size of the
devices than it is to contamination. That would suggest that the problems
you reported might be present in parts from every vendor, and may be a
function of the process dimensions more than anything else. The fact that
some parts exhibit the problem and others don't might be just statistical
probability.
Good point about the Japanese and Germans. I remember once coming up with a
code that I thought was unbreakable, just because I didn't see how anyone
could possibly decode it. After learning a tiny bit about cryptography, I
realized that the only thing stopping someone from decoding it would be the
sheer stupidity of the code ("he can't possibly have done something that
simple-minded, can he?"). Ignorance can be a really powerful weapon for
shooting oneself in the foot.
-- Mike --
Tim
> diodes actually go into a noisy sawtooth oscillation mode at low
> currents, phasing into asymmetric noise, then pretty gaussian-looking
> noise as current increases. I suspect diodes grown specifically as RF
> noise diodes behave better at low currents... maybe tiny junctions
> keep up the current density or something. For a 12-volt, 1N759-type
> part, 1 mA seemed pretty safe.
Hey, what kind of (*common!*) diodes exhibit the noisy behavior rather
strongly, and does a 1N4742 (12V, right?) work okay?
Tim
--
"Yeah, and I'm not easily impressed. Whoa, a blue car!"
- Homer Simpson
Bob Camp
The first problem with using common zener diodes as noise sources is
that they may or may not be noisy at the current you have chosen to
drive them at. You can find 10:1 variation in zener noise as you vary
current and pick between the same diodes from the same manufacturer.
The second problem is that they may have a significant junction
capacitance. This will tend to limit the bandwidth of the noise that
comes out of them. If you are trying for some kind of gigabit per
second random number generator (as the original poster seems to be
trying for) the bandwidth of the noise source will have to be pretty
good.
The final problem has also been mentioned before, the PSD of the noise
probably will start to roll up at low frequencies. You can do some
stuff to take care of problems like this (shuffles like taking the
difference between readings) but they add to the complexity of what
you are doing.
It would be a lot easier to address all of this if we knew what the
objective was ....
Enjoy!
Bob Camp
"Tim" <tmor...@charter.net> wrote in message
news:tscqn9f...@corp.supernews.com...
Tim
> objective was ....
Just curious of how to make white noise. Say, 30kHz bandwidth.
So, is it forward biased or what?
Bill Sloman
> > It would be a lot easier to address all of this if we knew what the
> > objective was ....
>
> Just curious of how to make white noise. Say, 30kHz bandwidth.
>
> So, is it forward biased or what?
No, we've been talking about reverse biased avalanche diodes -
normally called zener diodes, though the zener mechanism, which isn't
all that noisy, isn't active in diodes that break down at reverse
voltages of 8V or higher.
---
Bill Sloman, Nijmegen
John Larkin
Mike,
popcorn and 1/f noise are reasons not to use the noise of an amplifier
as a randomizer. Zeners have a high enough wideband noise density that
they overwhelm (mostly) the noise of subsequent stages.
Neon lamps are nice noise sources, too.
Old (WW II generation) radar jammers used 931 photomultiplier tubes as
random pulse generators.
John
Tim
Is that in the same way as zener diodes?