Projects Research & Design Hub

High-Speed Random Numbers

Written by Ed Nisley

Avalanche Noise for LEDs

Not content with a Geiger detector’s relatively slow random number generation, Ed turns to avalanche noise and explores some of the limitations found in typical circuits.

  • How to use avalanche noise from a reverse-biased semiconductor junction to generate random numbers

  • How to create the circuitry for generating avalanche noise

  • How to amplify the noise and understanding randomness loss

  • How to convert the noise signal samples into digital bits

  • 2N3904 transistor

  • Arduino Pro Mini microcontroller board

  • Microchip (formerly Atmel) ATmega328 microcontroller

  • Texas Instrumnets LM324 op amp

Generating truly random numbers by timing the pulses from a Geiger detector works well, as I described in my September 2015 column, but the ambient radiation level puts an upper limit on the generator’s speed, unless you live in a place where you really shouldn’t. For example, the background radiation on my workbench produces a dozen pulses per minute, enough to change one LED in the 8 × 8 matrix every 5 seconds. Should you want a “sparkly” display or, more seriously, need a large set of truly random numbers for experimental purposes, the generator must operate much faster. Rather than snuggle up to a lump of uranium, I decided to exploit another quantum source: the avalanche noise from a reverse-biased semiconductor junction.

A quick Web search will reveal many noise-based random number generators, many of which should work reasonably well. Rather than duplicate those, I thought it would be useful to start with a simple avalanche-noise source, then show how seemingly innocuous analog design decisions can severely compromise the results and produce non-random numbers that are completely useless for serious uses. As with my earlier Geiger detector, the noise you’ll meet here suffices for an LED desk ornament, but the discussion should also help you produce better circuitry for real applications.

GENERATING AVALANCHE NOISE
The gamma ray detector in my November 2015 column amplified the current pulse produced by gamma rays penetrating a Cold-War era ionization chamber. Even though each pulse involved just a few hundred electrons, the overall circuit behaved more-or-less as you would expect from our familiar circuit design equations and models. Those equations depend on the statistical behavior of macroscopic components carrying an uncountable number of charges, with the actions of individual particles dismissed as “noise” that’s of interest only when the desired signals become very small.

Q601, the 2N2907A PNP transistor in Figure 1, operates somewhat differently: it produces noise as electrons force their way through the normally impenetrable barrier of its reverse biased base-emitter junction. A transistor usually operates with a forward bias across that junction, with the base current controlling the current between the collector and emitter. In this circuit, I used only one junction and left the collector terminal open.

FIGURE 1 
The linear regulator provides enough voltage to drive 10 µA of DC current through the reverse-biased base-emitter junction of the 2N2907 transistor. The 2N3904 transistor and LM324 op-amp convert the tiny noise current into a logic-level voltage suitable for a microcontroller’s digital input. RV601 controls the DC bias current that determines the noise current amplitude. RV602 sets the DC level of the average noise voltage to produce approximately equal occurrences of 00 and 11 bit sequences.

The 2N2907A datasheet specifies a minimum breakdown voltage of V(BR)EBO = –5.0 V, with actual values around –8 V for several transistors in my parts box; the negative sign indicates the emitter is negative with respect to the base. Linear regulator U601 produces a DC voltage high enough to drive the junction into reverse breakdown, with the current limited by the series resistors and set near 10 µA by RV601.

That current represents an average of 62 × 1012 electrons/s passing through the junction, with small variations around the average producing shot noise. Statistical legerdemain well beyond the scope of this column shows the standard deviation for shot noise equals the square root of the average current: 8 × 106 electrons/s. That means the instantaneous current can vary by ±24 × 106 electron/s within 3 s of the average, which amounts to ±3.8 pA and is small enough to be ignored.

— ADVERTISMENT—

Advertise Here

However, some of those 62 × 1012 electrons collide with silicon atoms and knock more electrons loose that increase the instantaneous current flow. The additional electrons may, in turn, collide with atoms to dislodge even more electrons. The avalanche multiplication factor and, thus, the current variation, depend on the details of the junction’s construction, but the resulting avalanche noise usually dominates the shot noise.

Q602, a 2N3904 NPN transistor, amplifies the current from Q601 by its DC current gain, which the datasheet specifies as 70 < hFE < 300. I measured hFE = 200 in the circuit shown in Photo 1, but, because hFE depends on the specific transistor, junction temperature, and collector current, that value won’t apply to your circuit. The amplified current produces a voltage across R602, a 4.7 kΩ resistor, that consists of both a DC component from the average current and small variations due to the avalanching electrons.

PHOTO 1
Reverse bias applied to the base-emitter junction of the 2N2907A transistor on the left produces avalanche-mode current noise. The 2N3904 transistor and LM324 op-amp convert the feeble noise current into the logic voltage levels required by the Arduino Pro Mini in the background. Each set of nine random bits extracted from the noise determines the color of one RGB LED site in the 8 × 8 matrix.

The top trace in Photo 2 shows the AC-coupled voltage at Q602’s collector varying by slightly more than ±500 mV around its average. The current in R602 therefore varies by ±100 µA and, dividing by the transistor’s hFE = 200, the base current varies by ±500 nA around its average, far more than the shot noise.

PHOTO 2 
The amplified avalanche noise at the 2N3904 collector (top trace) obviously has a much higher bandwidth than the LM324 output in the lower trace. The horizontal cursors mark the microcontroller’s minimum VIH and maximum VIL levels. The AC-coupled upper trace is inverted to match the output phase.

You should pick the largest possible collector resistor to maximize the gain, while keeping the operating point a few volts above the emitter voltage and below the output of U601. The 4.7 kΩ value of R602 sets the transistor’s DC operating point at 6.3 V, with plenty of headroom for the AC signal.

The spectrum analyzer display in Photo 3 shows the noise spectrum at the collector remains essentially flat to 1 MHz. Beyond that, the noise is down 3 dB at 4 MHz, 10 dB at 10 MHz, and shows significant energy well beyond 50 MHz. The trace shows the average of 100 measurements at each frequency, making it much smoother than the usual spectrum analyzer display of pure noise. The large peak at 0 Hz comes from an aliased image of the analyzer’s local oscillator; as you’ll see later, setting the trace to begin at a nonzero frequency allows the IF filters to remove the image.

PHOTO 3 
The noise spectrum at the 2N3904 collector is flat well beyond 1 MHz. An image of the spectrum analyzer’s local oscillator produces the peak at 0 Hz and masks signal components below 50 kHz. The marker sits atop a 250 kHz signal produced by the 125 kHz SPI clock.

The diamond cursor at 250 kHz marks the second harmonic of the 125 kHz SPI clock that shifts data into the registers that drive the RGB LED matrix. When your random numbers must withstand cryptanalysis, similar small effects can compromise the results: careful attention to analog circuit layout, quite unlike what you see in Photo 1, can reduce those effects.

  • Pop quiz: How can a 125-kHz square-wave clock produce any second harmonic energy?

Capacitors C603 and C604 enhance the noise bandwidth by reducing the impedance of the AC path through the reverse-biased junction in Q601, so that the avalanche noise current doesn’t generate voltages in R603 and R605. Those two resistors set the DC resistance of the path, with the value of R605 multiplied by Q602’s DC current gain to about 200 kΩ. The difference between the bias voltage from U601 and the junction’s reverse-breakdown voltage drives DC current through the resistors.

The RGB LED matrix display circuitry appeared in the September 2015 column. I don’t have room for the full schematic here, but you can download it in Kicad format from the Circuit Cellar GoogleDrive page.

Now, to convert 1 VPP of beautiful analog noise into a useful digital signal.

— ADVERTISMENT—

Advertise Here

AMPLIFYING NOISE & LOSING RANDOMNESS
The Atmel ATmega328 datasheet cautions that digitizing signals with frequency components above the ADC’s sample-and-hold clock frequency, which has a maximum value of 200 kHz, will cause aliasing. I don’t know what effect the high-frequency components of the random signal in Photo 2 would have on the samples, but it’s yet another subtle effect to consider when you generate random numbers that matter.

The two horizontal cursors on the amplified signal in the lower trace of Photo 2 mark the ATmega328 digital input specifications for minimum VIH = 3 V and maximum VIL = 1.5 V. Input voltages above VIH always produce a logic 1 bit, voltages below VIL always produce a logic 0 bit, and voltages in between may produce either value: there’s no crisp threshold at the (VIH + VIL)/2 = 2.25 V level. As a result, AC-coupling the output of the 2N3904 directly to the microcontroller, with the DC level shifted to (VIH + VIL)/2, would produce logic transitions only at the highest peaks.

I used an LM324 op amp to boost the signal, make it compatible with the Arduino’s digital logic levels, and illustrate several problems that might otherwise go unmentioned. The lower trace in Photo 2 shows the output of U602A, a low pass filtered version of the input signal in the upper trace. The LM324 datasheet specifies a 1 MHz gain-bandwidth product, so an amplifier configured with a gain of 10 should be flat to about 100 kHz and drop off at 6 dB/octave = 20 dB/decade, which is obviously not the case.

The spectrum in Photo 4 drops by 20 dB at 100 kHz and doesn’t resemble the expected single pole response. The problem lies with the LM324’s slow 0.5 V/µs large-signal slew rate: it simply can’t keep up with an input that calls for repeated full-scale output changes within a few microseconds and produces strongly non-linear distortion. An op amp with a larger GBW and higher slew rate would produce a more accurate output, perhaps at the cost of an antialiasing filtering in front of the ADC.

PHOTO 4 
The output of U602A, configured with a voltage gain of 10, falls off well below the 100 kHz predicted by the gain-bandwidth product. The LM324 has a 0.5 V/µs large-signal slew rate that limits the overall response for full-scale outputs.

As a result, the signal will definitely produce a logic 0 only for the few negative-going peaks from 50 to 80 µs into the trace and might return a logic 0 for voltages above the lower cursor. The peak at 170 µs just barely crosses the VIH line, so that would produce a logic 1 bit, again with possible 1 bits for samples below the upper cursor. The negative-going peaks from 240 µs onward may or may not produce logic 0 bits and there’s no way to tell without careful measurements.

The tandem pair of op-amps provides an overall gain of 33 that may be needed for weaker noise sources. If your circuit requires less gain, changing the feedback resistor in the first op amp to 330 kΩ may avoid the slew rate limitation and improve the frequency response: measure carefully and analyze the results.

Photo 2 also points out another LM324 limitation: the flat tops around 200 µs correspond to its maximum output voltage of 3.8 V with a 5 V supply. The datasheet says the minimum VOH will be two volts below the supply, so the 3.8 V level depends on a very light output load. In short, this circuit will work, as long as the output exceeds the minimum VIH of the logic input, but carefully perusing the datasheets can help eliminate unpleasant surprises.

The circuitry behind each ATmega328 input pin has a buffer to prevent latchup for signals between the VIH and VIL limits, then passes the signal through a pair of latches acting as a synchronizer to reduce the chance of metastable behavior. Microcontrollers tend to have that type of armor, but if you’re using bare CMOS gates or a delicate microprocessor intended for pure digital applications, spend some Quality Time with the hardware manual to prevent bad assumptions from wrecking your project.

Obviously, the op amp bandwidth and ADC response to high frequency signals limit the bit rate to something far below the raw noise bandwidth. However, the signal still maintains its essential randomness and can produce random bits in digital logic, if not with the speed you’d expect from the raw avalanche noise source bandwidth.

Homework: The ATmega328 includes a built-in analog comparator with reasonable specs and a crisp threshold. Feed the AC-coupled and level-shifted noise into that comparator, modify the bit collection routine to take advantage of the higher bandwidth, then verify that the resulting bits actually have the expected bandwidth.

CONVERTING SAMPLES INTO BITS
Given the relatively low bandwidth of the amplified random signal, reading its digital value twice in quick succession (as measured in ATmega328 instruction times) would almost always produce two identical bits. In order to introduce a fixed delay between the bits to reduce the sampling frequency, I took advantage of the SPI hardware that controls the LED matrix. As before, the MOSI (Master Out, Serial In) SPI drives the shift registers holding the control signals for the LED matrix, with the SCK (Serial Clock) SPI pin shifting the bits into the registers.

The previously unused MISO (Master In, Serial Out) pin now connects directly to the output of U602B in Figure 1, without passing through a shift register or any other hardware. The pin simply accepts whatever voltage appears on it at the time of the rising SCK edge and shifts the resulting bit into the input buffer. The end result consists of eight consecutive noise samples at a 125 kHz = 8 µs/sample rate.

The upper trace in Photo 5 shows the SPI clock signal, with each block of 32 clock pulses corresponding to a single row of the LED matrix. The SPI hardware operates in LSB-first mode, so the first clock pulse shifts the least-significant bit out of the MOSI pin and into the MISO pin. The vertical cursors mark the clocks shifting the LSB in the first and last bytes of the SPI data stream.

PHOTO 5 
Sampling the amplified noise with the SPI serial data input allows reasonably precise timing without any additional overhead. The horizontal cursors mark the voltage thresholds for digital 0 and 1 data. The vertical cursors mark the two SPI bits used as input to the von Neumann extractor. 

The UpdateLEDs() function in Listing 1 sends four bytes of data to the LED shift register drivers, just as it did in the Geiger-based display, but it now also collects four bytes of noise samples from the SendRecSPI() function that handles the SPI hardware interface. Successive bits will be highly correlated, because the noise signal bandwidth is much lower than the sampling frequency, but fixing that was a simple matter of software: pick two widely separated bits.

Listing 1
The SendRecSPI function loads an outgoing byte into the SPDR output register, then waits for the hardware to transfer all eight bits before reading the SPDR input register. The UpdateLEDs function sends four bytes of LED data to the shift registers and combines four bytes of random noise into a single 32 bit return value.

byte SendRecSPI(byte DataByte) {    // send one byte, get another in exchange
    SPDR = DataByte;
    WaitSPIF();
    return SPDR;                    // SPIF will be cleared
}

unsigned long UpdateLEDs(byte i) { 
unsigned long NoiseData = 0ul; 

    NoiseData |=  (unsigned long) SendRecSPI(~LEDs[i].ColB);  // low-active 
    NoiseData |= ((unsigned long) SendRecSPI(~LEDs[i].ColG)) << 8; 
    NoiseData |= ((unsigned long) SendRecSPI(~LEDs[i].ColR)) << 16; 
    NoiseData |= ((unsigned long) SendRecSPI(~LEDs[i].Row))  << 24; 

    analogWrite(PIN_DIMMING,LEDS_OFF);    // turn off LED to quench current 
    PulsePin(PIN_LATCH);                  // show new shift reg contents
    analogWrite(PIN_DIMMING,LEDS_ON); 

    return NoiseData; 
}

The noise signal in the lower trace of Photo 5 produced a 0 at the first vertical cursor and a 1 at the second. The ExtractRandomBit() function in Listing 2 extracts those bits using two masks and processes them with the von Neumann extractor algorithm. If that produces a valid random bit, the code shifts it into an accumulator and increments a counter.

— ADVERTISMENT—

Advertise Here

Listing 2 
The von Neumann extractor uses two bits of the 32 bits sampled from the noise source to produce, at most, a single bit of random data. If all four states are 
equally likely, the hardware will generate a one random bit at every other call and one random byte for every 16 calls: one random byte consumes at least 512 noise data bits.

#define VNMASK_A 0x00000001
#define VNMASK_B 0x01000000

enum sample_t {VN_00,VN_01,VN_10,VN_11};

typedef struct {
    byte BitCount;    // number of bits accumulated so far
    unsigned Bits;    // random bits filled from LSB upward
    int Bias;         // tallies 00 and 11 sequences
   unsigned SampleCount[4]; // number of samples in each bin
} random_t;

random_t RandomData;

byte ExtractRandomBit(unsigned long RawSample) {

byte RetVal;

    switch (RawSample & (VNMASK_A | VNMASK_B)) {
    case 0:                           // 00 - discard
        RetVal = VN_00;
        RandomData.Bias--;
        break;
    case VNMASK_A:                    // 10 - true
        RetVal = VN_10;
        RandomData.BitCount++;
        RandomData.Bits = (RandomData.Bits << 1) | 1;
        break;
    case VNMASK_B:                    // 01 - false
        RetVal = VN_01;
        RandomData.BitCount++;
        RandomData.Bits  = RandomData.Bits << 1;
        break;
    case (VNMASK_A | VNMASK_B):       // 11 - discard
        RetVal = VN_11;
        RandomData.Bias++;
        break;
    }
    
    RandomData.Bias = constrain(RandomData.Bias,-9999,9999);
    RandomData.SampleCount[RetVal]++;
    RandomData.SampleCount[RetVal] =
          constrain(RandomData.SampleCount[RetVal],0,63999);

    return RetVal;
}

If the noise signal produced completely random transitions on the digital input, each of the four possible sequences of two samples should occur about the same number of times during any interval. Trimpot RV602 sets the signal’s DC level at the op amp outputs, so that the extractor should encounter nearly equal numbers of 00 and 11 sample sequences. With those two in balance, an unbiased generator would produce equal numbers of 01 and 10 sequences.

The middle trace in Photo 6 pulses high when the code refreshes the top row of LEDs in the matrix, which happens every 2.6 ms. The top trace pulses whenever the von Neumann extractor finds a 00 or 11 sequence, an event that should happen in half of the calls, as shown. The cursors mark the same voltages and times on the amplified noise in the bottom trace as in Photo 5.

PHOTO 6 
The middle trace pulses high at the start of each LED matrix refresh. Pulses in the top trace mark 00 and 11 sample sequences, which occur in about half of the rows. Adjusting the DC bias of the noise signal affects the balance beween 00 and 11 sequences.

The main loop displays longer-term trends by printing the contents of the counters every 10 s, as shown in Listing 3. Each pass through the main loop refreshes one display row, collects two noise samples, and calls the random bit extractor, a process that takes about 330 µs, so the diagnostic counters accumulate 30,000 counts in 10 s.

Listing 3
The diagnostic counters track the overall DC offset and tally the number of each sequence of two bits in the samples. A fair generator would have equal numbers 
of each sequence, but this one produces slightly too many 0 bits.

Bias:   -18 of 13692 -  6855  7732  8623  6837
Bias:  -293 of 13847 -  7070  7795  8402  6777
Bias:   -23 of 13581 -  6802  7960  8505  6779
Bias:   -31 of 13759 -  6895  7988  8300  6864
Bias:  -271 of 13733 -  7002  7907  8406  6731
Bias:  -151 of 13727 -  6939  7939  8380  6788
Bias:  -166 of 13712 -  6939  8066  8265  6773
Bias:  -237 of 13601 -  6919  8018  8427  6682
Bias:    -3 of 13749 -  6876  7977  8321  6873
Bias:  -122 of 13696 -  6909  7981  8366  6787
Bias:   -77 of 13605 -  6841  7870  8572  6764
Bias:   -67 of 13553 -  6810  8029  8461  6743
Bias:  -237 of 13623 -  6930  7884  8540  6693

The Bias value represents the difference between the number of 11 and 00 sequences, with negative values corresponding to a too-low RV602 threshold setting. For example, the Bias of –293 in the second line of Listing 3 means that the extractor found 293 more 00 sequences than 11 sequences, indicating that the threshold is slightly too high. Obviously, you should adjust the threshold based on the long-term average, not any individual value.

Some spreadsheet tinkering showed the extractor encountered more 01 sequences than 10 sequences and more of those than of the 00 and 11 sequences. You can compensate for a biased generator with mathematical trickery, as long as it produces uncorrelated successive bit samples, but that requires more extensive testing than seemed appropriate for a sparkly desk toy.

Homework: Accumulate enough samples to examine the noise correlation. Hint: storing the values on an SD card will be faster than sending them through the serial port, but SD cards require use of the MISO pin.

CONTACT RELEASE
In the spirit of “Video or it didn’t happen!,” the video “8 × 8 LED Array with Avalanche Noise Amplifier” below will show you a minute of the RGB LED matrix in operation.

The hardest thing to learn about analog electronics is that everything matters: op-amps aren’t all alike, layout can determine how well a circuit operates, everything functions as a (badly calibrated) thermometer, analog voltages aren’t digital, and vital details hide in the fine print of datasheets. As you’ve seen with this simple noise circuit, you must pay attention to every stage along the way in order to get the output signals you expect.

May your noise be good! 

RESOURCES
J. S. Denker, “Turbid: A High-Entropy Random Generator,” 2005, www.av8n.com/turbid/paper/turbid.htm. 
E. Nisley, “Gamma Ray Ionization Amplifier,” Circuit Cellar 304, 2015.
———, “Random LED Dots,” Circuit Cellar 302, 2015.
———, “8 × 8 LED Array with Avalanche Noise Amplifier,” https://youtu.be/yd1zzsctW_U.
Maxim Integrated, “Building a Low-Cost White-Noise Generator,” Application Note 3469, 2005, www.maximintegrated.com/en/app-notes/index.mvp/id/3469.
Wikipedia, “Avalanche Breakdown,” https://en.wikipedia.org/wiki/Avalanche_breakdown.
———, “Shot Noise,” https://en.wikipedia.org/wiki/Shot_noise.
———, “von Neumann Extractor,” https://en.wikipedia.org/wiki/Randomness_extractor#Von_Neumann_extractor.

SOURCES
Arduino Pro Mini microcontroller board
Arduino | www.arduino.cc
ATmega328 Microcontroller
Microchip Technology (formerly Atmel) | www.atmel.com
LM324 Op-amp
Texas Instruments | www.ti.com

PUBLISHED IN CIRCUIT CELLAR MAGAZINE • JANUARY 2016 #306 Get a PDF of the issue

Keep up-to-date with our FREE Weekly Newsletter!

Don't miss out on upcoming issues of Circuit Cellar.


Note: We’ve made the May 2020 issue of Circuit Cellar available as a free sample issue. In it, you’ll find a rich variety of the kinds of articles and information that exemplify a typical issue of the current magazine.

Would you like to write for Circuit Cellar? We are always accepting articles/posts from the technical community. Get in touch with us and let's discuss your ideas.

EE and Author at Poughkeepsie, NY | + posts

Ed Nisley is an EE and author in Poughkeepsie, NY. Contact him at ed.nisley@pobox.com with “Circuit Cellar” in the subject line to avoid spam filters.

Sponsor this Article

Supporting Companies

Upcoming Events


Copyright © KCK Media Corp.
All Rights Reserved

Copyright © 2021 KCK Media Corp.

High-Speed Random Numbers

by Ed Nisley time to read: 15 min