Problem reading random noise generator

[Grumpy_Mike]

If that's happening, why do they seem to be grouping at the top and bottom ends?

Because the signal is moving faster in the middle of the transition, just think of a sin wave the fastest movement is at the zero crossing poi nt. those are just the levels you will miss.

[BareMetal]

Don't forget that the noise will have a higher frequency in the noise that you can sample at. Therefor there will be a degree of avraging going on which will limit the readings at the top and bottom end. You need to add a low pass filter to your noise source to take it below the niquis rate.

I tried something similar a while ago and got very similar results...a disproportionate binfull of 0s and 255s in my case....

im sure its a sampling frequency/nyquist issue. in my case I was cleaning up the signal with an lm393...I had biased my zener +NPN amp to be abt 2.5 midpoint and fed that plus a pot.tweaked Vcc/2 to the 393.

even tho my scope is ancient and slow, I could see that if I shifted the vcc midpoint up or down slightly in the wide blur of random fuzz, even tho it was still sort of middle.ish my distribution would vary widely...i did actually get a fairly flat distribution at one point, but I could never repeat it. I concluded I was being thwarted by the slew rate of the 393, or some kind of "beat frequency" between a less than nyquist rate on the max 393 slew rate...

my knowledge and scope were well below required level at the time, so I took the easy solution..I gave up!

ps they probably still are, but at least I can send you some empathy, if not fix your entropy....

[el_supremo]

Just to reinforce what Coding Badly pointed out, I made a circuit based on that type of design using 2n2222 and I found that a supply of 5V and 9V didn't work well. It needed at least 12V.

[wanderson]

Avalanche noise circuits have several issues as random number generators.  The first, is that they exhibit a fair degree of bias, regardless with how you capture the noise (ADC or comparator). 

My experiments have indicated that two stages of 'whitening' are required to remove the bias from the readings.  I use a Von Neumann filter followed by either some form of linear feed back shift register (LFSR).  In general I have found that it requires at least a 4:1 whitening ratio to get a reasonably uniform RNG.  For LFSR, I have used either a simple XOR'ing of consecutive bytes (which worked for one example circuit with A2D) to a Jenkings one-at-a-time hash on my second implementation which required more whitening due to a different noise source (5V zener source, no 10-15V supply needed).

The second issue with avalanche noise random number generator circuits is that the balance of 1's to 0's will change over time.  If your code doesn't accomodate such changes your RNG will stop producing uniform RN when the bias exceeds your whitening technique's ability to cope.  As you can see from the pages below, I noticed LARGE changes in the circuits balance point as it aged.

If your interested in my experiments, which include the code I derived from Rob Sewards median calculation approach are available from

https://sites.google.com/site/astudyofentropy/project-definition/avalanche-noise
https://code.google.com/p/avr-hardware-random-number-generation/wiki/AvalancheNoise

[jremington]

The author of the HRNG link you posted claims to have gone to some effort to reach his goal, namely

trying to design a circuit that could produce a symmetrical, zero-average noise signal from a reverse biased p-n junction in avalanche breakdown

but it really isn't clear how he achieved and verified the output of the hardware other than with software. Your circuit has no provision for adjustments and can't produce a zero mean signal. Also, he used a digital input to generate "1"s and "0"s -- your use of the ADC throws in an additional complication. So you may be fighting an uphill battle.

I don't mean to be discouraging! These things are fun and challenging.

As an aside, it is interesting to listen to various different transistors in avalanche breakdown. You can do this by coupling the output transistor via a capacitor to the high gain phono input of an audio amplifier. There are a few different processes that lead to breakdown, and these manifest themselves as clicks, pops and hisses of different apparent pitches.

[BareMetal]

Just to reinforce what Coding Badly pointed out, I made a circuit based on that type of design using 2n2222 and I found that a supply of 5V and 9V didn't work well. It needed at least 12V.

I disagree. my original circuit was stolen from a 12v design. I dropped it to 5v, changed the NPN bias to get 2.5 ish midpoint and enough gain to exceed the upper and lower hystersis points of the 393. it didnt work...until I realised that the key point is the current through the noise source is quite critical. i guess most mfrs try to reruce noise and though zeners are inherently noisy there is a point on their curve where they are most noisy. we are talking nanocurrents here, any help you can get to boost the starting point is a bonus...I rebiased the zener to get the exact datasheet current point for peak noise and it burst into life....

albeit with the nyquist sample rate problem, so im not cel3brating yet, just my 2c that 5v circuits can be made noisy with a bit of care,a datasheet and a calculator

[wanderson]

Just to reinforce what Coding Badly pointed out, I made a circuit based on that type of design using 2n2222 and I found that a supply of 5V and 9V didn't work well. It needed at least 12V.

I disagree. my original circuit was stolen from a 12v design. I dropped it to 5v, changed the NPN bias to get 2.5 ish midpoint and enough gain to exceed the upper and lower hystersis points of the 393. it didnt work...until I realised that the key point is the current through the noise source is quite critical. i guess most mfrs try to reruce noise and though zeners are inherently noisy there is a point on their curve where they are most noisy. we are talking nanocurrents here, any help you can get to boost the starting point is a bonus...I rebiased the zener to get the exact datasheet current point for peak noise and it burst into life....

albeit with the nyquist sample rate problem, so im not cel3brating yet, just my 2c that 5v circuits can be made noisy with a bit of care,a datasheet and a calculator

Avalanche noise is generally an order of magnitude lower for 5V and below sources (typically zeners') when compared to 12V+ sources, even when current is adjusted for.  Further the reverse bias transistor used in the OP example doesn't enter the breakdown zone until about 8-9V, though I have found a few examples of the 2N3904 (the transistor typically specified) that entered breakdown at lower voltages, the mean tends to be around 9V, with noise peaking near 12V.

The 'best' current for maximum noise varies with the device; however, the ones I have tested have generally been 5-50 uA.

Further, there have been several people who have tested a variety of such transistors, and the 2N3904 tend to produce the most noise.

[wanderson]

The author of the HRNG link you posted claims to have gone to some effort to reach his goal, namely

trying to design a circuit that could produce a symmetrical, zero-average noise signal from a reverse biased p-n junction in avalanche breakdown

but it really isn't clear how he achieved and verified the output of the hardware other than with software. Your circuit has no provision for adjustments and can't produce a zero mean signal. Also, he used a digital input to generate "1"s and "0"s -- your use of the ADC throws in an additional complication. So you may be fighting an uphill battle.

The original author of the circuit the OP is using believed that a relatively even balance between 0's and 1's produce a non-biased output (it doesn't), but they didn't appear to actually test that asuumption since they used 'whitening' techniques from the start:

This time there is no need to minimize bias inherent in the operation of the generator, if all went well we should get a probability of 1s and 0s very close to 50%. Of course I'm going to assume that the bit-stream still contain bias and correlation, so a de-skewing technique for reducing bias and correlation will be used anyway.
On the software side I have basically used the same code I had written for the Chua random generator: at the beginning GPIO4 is configured as input, then one bit is read (and its value is optionally printed), next we wait for a delay and repeat. This delay has been set to 500?s, producing a 2000bit/s stream.

[jremington]

Yes, I see. He ran a simple program to read two independently generated output streams from the HRNG and produce a third stream, as outlined by the following (from http://holdenc.altervista.org/chua/ )

John von Neumann invented a simple algorithm to fix simple bias, and reduce correlation. It considers successive pairs of consecutive, non-overlapping bits from the input stream, taking one of three actions: when two successive bits are equal, they are discarded; a sequence of 1,0 becomes a 1; and a sequence of 0,1 becomes a 0. It thus represents a falling edge with a 1, and a rising edge with a 0. This eliminates simple bias, and is easy to implement. This technique works no matter how the bits have been generated. It cannot assure randomness in its output, however. What it can do is transform a biased random bit stream into an unbiased one. However, significant numbers of bits are discarded. Thanks to the hardware bias reduction, we can affirm that the probability of 1 is p ~ 1/2, and in this case the discard of input pairs is minimum, giving us an output stream that is 1/4 the length of the input on average.

[acegard]

Wow, it's obvious that I don't have nearly as good of a grasp of this as I thought I did! I'm going to spend the morning reading all the responses and sources and come back when I can post an informed, coherent reply!
Thank you guys for your great, informative responses.

Avalanche noise is generally an order of magnitude lower for 5V and below sources (typically zeners') when compared to 12V+ sources, even when current is adjusted for.  Further the reverse bias transistor used in the OP example doesn't enter the breakdown zone until about 8-9V, though I have found a few examples of the 2N3904 (the transistor typically specified) that entered breakdown at lower voltages, the mean tends to be around 9V, with noise peaking near 12V.

The 'best' current for maximum noise varies with the device; however, the ones I have tested have generally been 5-50 uA.

Further, there have been several people who have tested a variety of such transistors, and the 2N3904 tend to produce the most noise.

I am limited to a voltage source of 9V for the final project, unfortunately, so I chose the 2N2222 as opposed to the 2N3904 because, even though it might not produced as much noise, it looks like it's easier to push into breakdown at lower voltages according to the example I cited in the OP. If I'm off base here, let me know.

I disagree. my original circuit was stolen from a 12v design. I dropped it to 5v, changed the NPN bias to get 2.5 ish midpoint and enough gain to exceed the upper and lower hystersis points of the 393. it didnt work...until I realised that the key point is the current through the noise source is quite critical. i guess most mfrs try to reruce noise and though zeners are inherently noisy there is a point on their curve where they are most noisy. we are talking nanocurrents here, any help you can get to boost the starting point is a bonus...I rebiased the zener to get the exact datasheet current point for peak noise and it burst into life....

albeit with the nyquist sample rate problem, so im not cel3brating yet, just my 2c that 5v circuits can be made noisy with a bit of care,a datasheet and a calculator

So you're using a Zener diode to generate avalanche noise as opposed to transistor breakdown? Does your circuit look something like this, getting the noise from the zener and then using the two transistors to amplify that?

[wanderson]

So you're using a Zener diode to generate avalanche noise as opposed to transistor breakdown? Does your circuit look something like this, getting the noise from the zener and then using the two transistors to amplify that?

The reverse biased transistor used in the original circuit you cited, as well as my original circuit, not to mention the typical circuit floating around the web for 30+ years is behaving in the exact same manner as a zener diode.  This app note might help you:

http://www.maximintegrated.com/en/app-notes/index.mvp/id/3469

I have also made some suggested changes to your circuit.  First, since you are using a capacitor to isolate the noise voltage/current from the op-amp (ac-coupling) you can use a single sided rail to rail op amp supplied by 5V to perform your later amplification and buffering.  I use the MCP629x family but any similar opamp should work.  BTW, you may want to try a larger capacitor, say 0.1 - 0.22 uF

I also didn't show it, but adding a buffer (similar to what you have on the first op amp following the transistor) to your voltage divider would be beneficial, particularly if you keep the resistors your using to connect the divider to the + input of the op amps. 

I

[Coding Badly]

I am limited to a voltage source of 9V for the final project...

9V battery?

[BareMetal]

Wow, it's obvious that I don't have nearly as good of a grasp of this as I thought I did! I'm going to spend the morning reading all the responses and sources and come back when I can post an informed, coherent reply!
Thank you guys for your great, informative responses.

Avalanche noise is generally an order of magnitude lower for 5V and below sources (typically zeners') when compared to 12V+ sources, even when current is adjusted for.  Further the reverse bias transistor used in the OP example doesn't enter the breakdown zone until about 8-9V, though I have found a few examples of the 2N3904 (the transistor typically specified) that entered breakdown at lower voltages, the mean tends to be around 9V, with noise peaking near 12V.

The 'best' current for maximum noise varies with the device; however, the ones I have tested have generally been 5-50 uA.

Further, there have been several people who have tested a variety of such transistors, and the 2N3904 tend to produce the most noise.

I am limited to a voltage source of 9V for the final project, unfortunately, so I chose the 2N2222 as opposed to the 2N3904 because, even though it might not produced as much noise, it looks like it's easier to push into breakdown at lower voltages according to the example I cited in the OP. If I'm off base here, let me know.

I disagree. my original circuit was stolen from a 12v design. I dropped it to 5v, changed the NPN bias to get 2.5 ish midpoint and enough gain to exceed the upper and lower hystersis points of the 393. it didnt work...until I realised that the key point is the current through the noise source is quite critical. i guess most mfrs try to reruce noise and though zeners are inherently noisy there is a point on their curve where they are most noisy. we are talking nanocurrents here, any help you can get to boost the starting point is a bonus...I rebiased the zener to get the exact datasheet current point for peak noise and it burst into life....

albeit with the nyquist sample rate problem, so im not cel3brating yet, just my 2c that 5v circuits can be made noisy with a bit of care,a datasheet and a calculator

So you're using a Zener diode to generate avalanche noise as opposed to transistor breakdown? Does your circuit look something like this, getting the noise from the zener and then using the two transistors to amplify that?

yep, but with lm393 replacing 2nd xistor stage, op pulled up to give what I hoped was a random stream of digits, which I could count 8 off at a time to give me a series of random 8bit numbers, or so I naively thought....but hey im a,relative newbie to amps n volts, so I forgave myself. it seemd like a good idea. it taught me how to bias a transistor, at least...so it was worthwhile for my hobby needs. my main aim in all this is to learn learn learn not make millions designing a better microwidget.

the "zener" was a ZXRE4041 OR 1004 cant remember which and the peak noise current was something like 7 or 8 uA I think, which is bang in line with what the other far more knowledgeable posters have said. I shall drop out now in the presence of such greatness, my 2c has been spent! these blokes know whst they are on about, im just a nosey amateur.

[wanderson]

yep, but with lm393 replacing 2nd xistor stage, op pulled up to give what I hoped was a random stream of digits, which I could count 8 off at a time to give me a series of random 8bit numbers, or so I naively thought....but hey im a,relative newbie to amps n volts, so I forgave myself. it seemd like a good idea. it taught me how to bias a transistor, at least...so it was worthwhile for my hobby needs. my main aim in all this is to learn learn learn not make millions designing a better microwidget.

the "zener" was a ZXRE4041 OR 1004 cant remember which and the peak noise current was something like 7 or 8 uA I think, which is bang in line with what the other far more knowledgeable posters have said. I shall drop out now in the presence of such greatness, my 2c has been spent! these blokes know whst they are on about, im just a nosey amateur.

Sounds like you use this circuit as a basis; https://mywebspace.wisc.edu/lnmaurer/web/minirng/minirng.html  Which uses a ZXRE1004 voltage reference (kindof a zener) as the noise source.  The key to that circuit is the use of a high slew rate single sided rail to rail op amp.  The author used a OPA2340 (or a MCP6282), I don't think a LM393 would be up to the job.  I implemented the circuit with the original OPA2340 as well as my go to MCP629x series, and both worked great.  Even though the circuit produced a good balance of 1's and 0's (near 50/50) it still required a fair bit of whitening to produce a uniform distribution.  Attached are two graphs.  The first shows the distribution with no whitening, the second shows a two tiered whitening approach; Von Neumann followed by a Jenkins one at a time hash. 

Here are the ent results for the first test; followed by the results for the second

Code: [Select]


Entropy = 7.655314 bits per byte.

Optimum compression would reduce the size
of this 22124796 byte file by 4 percent.

Chi square distribution for 22124796 samples is 12926784.31, and randomly
would exceed this value less than 0.01 percent of the times.

Arithmetic mean value of data bytes is 126.1181 (127.5 = random).
Monte Carlo value for Pi is 3.375643870 (error 7.45 percent).
Serial correlation coefficient is -0.000318 (totally uncorrelated = 0.0).


Code: [Select]


Entropy = 7.999928 bits per byte.

Optimum compression would reduce the size
of this 2679092 byte file by 0 percent.

Chi square distribution for 2679092 samples is 266.62, and randomly
would exceed this value 29.59 percent of the times.

Arithmetic mean value of data bytes is 127.5069 (127.5 = random).
Monte Carlo value for Pi is 3.143365844 (error 0.06 percent).
Serial correlation coefficient is -0.000298 (totally uncorrelated = 0.0).


Which just goes to show how nescessary whitening is for any TRNG.

Here is Arduino functions to implement the two whitening algorithms I used:

Code: [Select]

uint8_t pool[POOL_SIZE];
uint8_t pool_position;

uint32_t jenkins_one_at_a_time_hash(uint8_t *key, size_t len)
{
    uint32_t hash, i;
    for(hash = i = 0; i < len; ++i)
    {
        hash += key[i];
        hash += (hash << 10);
        hash ^= (hash >> 6);
    }
    hash += (hash << 3);
    hash ^= (hash >> 11);
    hash += (hash << 15);
    return hash;
}

// This routine takes the bit stream from the first phase of bias removal and then
// adds a second stage of bias removal by xor'ng two consequetive bytes. 
// Depending upon the current operating mode, will dictate how the resulting byte
// is processed
void buildNum(byte input)
{
  static uint8_t tmp = 0;
  static int num_counter = 0;
  uint32_t out;

  if (input == 1)
  {
    tmp = (tmp << 1) | 0x01;
  } else {
    tmp = (tmp << 1);
  }
  num_counter++;
  num_counter %= 8;
  if(num_counter == 0)
  {
    pool_position++;
    pool[pool_position - 1] = tmp;
    if (pool_position == POOL_SIZE)
    {
      // Ok, we have filled the pool up.  Time to hash the values for an output
      out = jenkins_one_at_a_time_hash(pool, POOL_SIZE);
      Serial.println(out);
      pool_position = 0;
      tmp = 0; 
    }
  }
}

// This routine implements the von Neumann algorithm for removing bias from a bit stream
void vonNeumann(byte input)
{
  static int count = 1;
  static boolean previous = 0;
  static boolean flip_flop = 0;
 
  flip_flop = !flip_flop;

  if(flip_flop)
  {
    if(input == 1 && previous == 0)
    {
      buildNum(0);
    } else if (input == 0 && previous == 1) {
      buildNum(1);
    }
  }
  previous = input;
}


I feed the bits to the VonNeumann function which starts the whitening process.  The BuildNum function takes the preliminary whitened output from the VonNeumann function and builds a queue of 16-bytes, which are then fed to the Jenkins hash function, which produces a 32-bit (uint32_t) value which is then output as the random number.  It was these processed numbers which produced the second set of results above.  The last is an image of the circuit I breadboarded for testing this ZXRE1004 noise source.

[BareMetal]

yes, I think, you are right, I only had 393 somimtried to use my limited knowledge to make at least something to work, even if far from perfect. i also couldnt find his valuemfor v+, hence my cheapmhack and recalculation to 5v. with your expert advice I may get the right op amp and try again. as i said before, I did get some sort of output, and at one sweet spot which I coild never replicate, my rudimentary processing sketch produced a pretty good looking distribution.

the one big thing I learned from this "failure" is that there is apparently random (at least to a novice) and then there is Random.

I also only have A level maths from 40years ago, so figuring out just how random my random was is beyond me. I am in awe of folk that can do maths or play the piano...

your excellent contribution has reignited my curiosity...I might well rebuild and report back, but dont hold your breath!