OPENCORES.ORG

Hi Bill,

Hi-
     I read your discussion with interest. I am charged with generating 
random signals for testing seismometers in the frequency span 1mHz to 
50Hz.
Question 1:  Is it possible to simply lower the spectrum of the 
generated- noise by lowering the clock frequency?
Question 2:  What is the "diehard" test? I am searching for a method of 
testing random signals or the underlying numbers. I have read that a 
good archiving file compressor will give a qualitative measure of 
randomness based on the degree of compression achieved. Is this 
accurate?
     (A friend of mine wrote a program to win at one of the Las Vegas 
games, and based on his results drove to Vegas and lost his money. He 
discovered that the fly in the ointment was allowing his PC to generate 
the random numbers for the game simulation, without any checking.)
-Charles
NonDigital@g...

----- Original Message ----- 
From: Bogic Petrovic<boggy@e...> 
To: 
Date: Wed May  5 16:22:44 CEST 2004 
Subject: [oc] random integer - VHDL 

> Hi Bill, 
> 
> You are right. But, a common misconception is also to use analog 
> noise 
> generators expecting theoretical behavior. 
> XORing is processing method, and analog noise is, in this case, 
> very 
> good starting point for pseudo-random generator source. 
> All pseudo random generators have the same problem... how to 
choose 
> first "random" number and make "more random" 
> number? 
> Finally, analog noise and good processing method combination is 
> something else. 
> Best regards 
> -boggy 
> Bill Cox wrote: 
> > Hi. 
> > 
> > Bogic Petrovic wrote: 
> > 
> >> 
> >> Hi, 
> >> 
> >> I don't have idea how to make random generator in VHDL, 
> but all 
> >> method based on "random" voltage (thermal 
> measurement diode) 
> >> or "random" time (jitter), have same problem 
> vith non-random noise 
> >> based on poor filtered and regulated power supply, and 
> more 
> >> other sources in real environment. 
> >> This noise exist in all real applications, and 
> pseudo-random 
> >> generators is still best solution. 
> >> 
> >> 
> >> Best regards, 
> >> 
> > A common misconception is that non-random noise cannot be 
> removed from 
> > a partially random signal to produce a truely random signal. 
> I've 
> > proven this in hardware, and mathematically. 
> > 
> > All you have to do is xor a bunch of bits from the noise 
> source (such 
> > as a diode), and the longer you wait, the more random the 
> xor-ed sum 
> > will be. In fact, you don't want to throw away the upper bits 
> from 
> > the noise source. If there's any true randomness in them at 
> all, they 
> > can only help improve the randomness of the xor-ed sum. 
> > 
> > I generated an entire CD (600 megabytes) of random numbers 
> this way, 
> > and passed the DieHard tests. In fact, I had so much data, I 
> was able 
> > to run it 60 times. 
> > 
> > The method I used was to take zener diode noise, amplify it, 
> and run 
> > it through a 40MHz 8-bit A/D converter. I took the output and 
> xor-ed 
> > the bits into an 8-bit shifter register that rotated the bits 
> on every 
> > clock cycle. After about 80 samples, I'd read the data out. 
> With a 
> > scope, I could see that the noise source had significant noise 
> well 
> > into the range where my scope couldn't keep up anymore, so 
> there's a 
> > lot of true random data there. 
> > 
> > Here's my attempt to describe how xoring many semi-random bits 
> to 
> > generate one highly random bit works: 
> > 
> > Two semi-random bits b1 and b2 each contain small amounts of 
> > non-random noise which we can call d1 and d2. Note that d1 and 
> d2 can 
> > be correlated, and usually are. The notation P(expression) 
> means the 
> > probability that the expression will be 1. 
> > 
> > I define P(b1) and P(b2) as: 
> > 
> > P(b1) = 0.5 + d1 
> > P(b2) = 0.5 + d2 
> > 
> > To simplify calculations, let's use the maximum, d = max(d1, 
> d2) in 
> > the following. 
> > 
> > Xoring b1 and b2 together gives: 
> > 
> > P(b1 ^ b2) = P(b1 & !b2) + P(!b1 & b2) = P(b1)*P(!b2) 
> + P(!b1)*P(b2) 
> > = (0.5 + d)*(0.5 - d) + (0.5 - d)*(0.5 + d) 
> > = 0.25 - 0.5*d + 0.5*d - d*d + 0.25 + 0.5*d - 0.5*d - d*d 
> > = 0.5 - 2*d^2 
> > 
> > Squaring a small number makes it very small indeed. If d1 and 
> d2 are 
> > already < 0.01, then xoring b1 and b2 together results in a 
> random bit 
> > noise level < 0.0002. This leads to the following equation 
> for the 
> > amount of non-random noise defined as n(bits) given the number 
> of bits 
> > in the xor sum: 
> > 
> > n(1) = d 
> > n(2) = 2*n(1)^2 = 2*d^2 
> > n(4) = 2*n(2)^2 = 2*(2*d^2)^2 = 2^3*d^4 
> > n(8) = 2*n(4)^2 = 2*(2^3*d^4)^2 = 2^7*d^8 
> > ... 
> > n(i) = 2^(i-1)*d^i = .5*2^i*d^i = .5*(2*d)^i 
> > 
> > Here's how you can use this equation. Lets say you believe you 
> have 
> > non-random noise levels of no more than d. You want the noise 
> level 
> > to be less than N. We want to compute the number of bits 
> needed, i: 
> > 
> > N = n(i) = .5*(2*d)^i 
> > 2*N = (2*d)^i 
> > log(2*N) = i*log(2*d) 
> > i = log(2*N)/log(2*d) 
> > > So, for example, if you feel your non-randomness per bit 
> is less than > 10%, but you need less than 1 part per billion, 
> we compute the number > of bits needed in the xor-sum: > > 
> i = log(2*10^-9)/log(2*.1) = 12.5 > > In other words, just 
> xor together at least 13 bits, and you should be > in good 
> shape. > > I've still got copies of the random data I 
> generated, if there are > doubters out there who would like to 
> test it. > > Bill > > > 
> _______________________________________________ > 
> http://www.opencores.org/mailman/listinfo/cores > 
>