Projects Research & Design Hub

A Hardware Random Number Generator

Written by Dev Gualtieri

MCU-Based Solution

Men first walked on the Moon 50 years ago. On the same week as that historic event, Dev divided his time between watching the event on television and building a unique desktop novelty circuit, a random digit generator. This circuit used a Nixie tube for display and a handful of TTL integrated circuits to implement a linear feedback shift register. In this article, Dev updates his original design using the CMOS digital circuits available today and a 7-segment LED display. He also presents an improved version that uses a Microchip PIC MCU.

I’ve been interested in random numbers since high school, when I stumbled upon the famous RAND Corporation book of a million random numbers at a public library. This collection of random numbers was based on a study for the US Air Force, and the random numbers were generated using a physical noise source. This book wasn’t the first book of random numbers. That milestone goes to “Random Sampling Numbers,” created in 1927 by English statistician L.H.C. Tippett, who took random digits from British Census records to create 10,400 four-digit random numbers.

The physical noise source for the RAND study was described as a random frequency pulse generator. This noise source was likely based on Johnson-Nyquist noise—the voltage noise seen across any resistor above absolute zero. The random numbers derived from this noise source were whitened—that is, the data were manipulated to enhance randomness since the circuitry was presumed to be slightly biased against pure randomness, just like a loaded die will show some numbers more than others.

My first attempt at a random number generator used an electronic noise source different from the one used in the RAND study. In my circuit, I used a Zener diode as a noise source, and the amplified white noise from this source was used to modulate the frequency of an oscillator. I quickly found that the amplitude of low-frequency noise from this source was disappointingly low, so much so that my random numbers were not that random. At that point I decided instead to use a maximal length linear-feedback shift register—something easily built with the TTL logic chips of that era.

Shift registers operate by shuttling logical “1” or “0” bits at their input along a series of stages, just like students passing notes from desk to desk in a classroom. In a Fibonacci linear-feedback shift register—named after the famous 13th century mathematician, Fibonacci—this input bit is taken from a combination of bits from the stages of the shift register. Exclusive-Or (XOR) logic gates combine bits in a way that maximizes the randomness. For a maximal length 24-bit linear-feedback shift register, the feedback can be taken from cascaded XOR logic gates that tap the outputs of stages 7, 16, 22 and 24, as shown in Figure 1. There are other taps that work as well, and taps for both longer and shorter shift registers.

FIGURE 1 – A maximal length 24-bit linear-feedback shift register. Data bits can be extracted from any of the 24 stages, but randomness is only assured when the register is cycled through those bits. The sequence length is more than 16 million, so 4 million random decimal or hexadecimal digits can be extracted.

CIRCUITRY
The circuitry to implement a random digit generator using this approach, as shown in Figure 2, uses seven inexpensive integrated circuits. It has the advantage that no firmware is required. Three of the ICs are 4015 8-bit shift registers that are cascaded to create a 24-bit shift register. There’s a 4070 quad-XOR IC, two 555 timers for cycling the bits and refreshing the display, and a 4511 decoder-driver for a 7-segment LED display. In the circuit shown in Figure 2, IC1-IC3 are the cascaded 8-bit shift registers that comprise the 24-bit linear-feedback shift register. This shift register is tapped at stages 7, 16, 22 and 24 and has its input at IC1-pin7. The XOR chip at IC4 handles the feedback function, and the BCD (binary-coded decimal) digit is taken from IC1.

FIGURE 2 – Circuitry for the linear-feedback shift register random number generator. The shift register outputs hexadecimal digits, but the 4511-display driver only shows 0-9 and blanks hex digits A-F. The author’s original TTL circuit used a 7447-display driver that outputs arbitrary characters for inputs beyond 9. In that case, some additional logic chips were used to detect these states and blank the display.

IC6 and IC7 are 555 timers that cycle the shift register four times each second. The cycle pulses are generated by IC7, and they come in a short burst that’s triggered by IC6. IC6 generates a 50 ms pulse every second, and this signal is sent to the enable pin of IC7 to produce the pulse sequence shown in Figure 3. It’s important that there are at least four pulses generated per cycle. If there are fewer than four, successive digits will be correlated and randomness will be lost. There can be more than four, so you can decrease the value of the timing capacitor at IC7 to be cautious if you don’t have an oscilloscope to count the pulses.

— ADVERTISMENT—

Advertise Here

FIGURE 3 – Timing pulses generated by the two 555 timers. IC6 gates IC7 to generate four pulses to advance the linear-feedback shift register by a single BCD digit. This pulse train occurs at one second intervals, so there’s a new random number every second.

IC5 is a combined decoder-driver that presents the BCD data to the 7-segment LED display. This chip is blind to numbers outside the 0-9 range, so hexadecimal digits A-F are blanked when they occur. This means that random digits will sometimes be more than a second apart. Some additional chips would solve this problem, but I thought that this would unnecessarily complicate the circuit.

There are quite a few ICs in this design, so I designed the PCB so that it can be cut in half and folded into a right angle, as shown in Figure 4. I etch my own circuit boards, so they’re always designed with copper conductors on a single side with a few necessary jumpers. Logic circuitry typically needs some longer jumpers for signal connections, in this case from the taps on the shift registers to the XOR chip.

FIGURE 4 – The circuit board for the random number generator can be cut in half and folded to produce a more compact design. The USB power connector can be seen on the right, and the connector to the 7-segment display is on the left.

COMPLETED DEVICE
Although this circuit could be used to generate random PIN numbers for your various accounts, it’s essentially a desktop novelty—a computer person’s bobble head doll. To add to the novelty, I built mine into a semi-transparent plastic case and added two blue LEDs to light the interior. The LEDs needed light diffusers to better spread their light in the inside, and I made these from some plastic tubing and a blob of some translucent silicone adhesive. The completed device can be seen in Figure 5.

FIGURE 5 – The random number generator based on a 24-bit linear-feedback shift register. The device is built into a semi-transparent plastic box that has the internal circuitry lighted by two blue LEDs. The USB power connector is at the right, and the ribbon cable connection to the 7-segment LED display can be seen at the left.

The device was designed to be powered by a small USB wall outlet transformer, since its current requirement of 135 mA at 5 V is supposedly outside the 100 mA limit of a USB-2.0 computer connector. Since I supposed that computers had internal current-limiting circuitry to prevent damage, I took the chance and plugged into an older desktop computer, and it worked fine. The circuit also worked with the USB-2.0 connection on another home computer. The USB-3.0 specification calls for a 150 mA maximum current draw per connector, so these are presumed safe.

There’s a notable Dilbert cartoon, published on October 25, 2001, in which our geek protagonist, Dilbert, is touring the “Land of the Accounting Trolls.” He’s introduced to their random number generator, a troll who repeatedly says, “nine.” Dilbert questions whether this is truly random, and his troll tour guide says, “That’s the problem with randomness. You can never be sure.” Luckily, there are statistical tests for randomness, the most famous being Diehard, devised by American mathematician and computer scientist George Marsaglia.

While Diehard would be overkill in assessing how well this 24-bit linear-feedback shift register performs, I did check its performance by a computer simulation for a run of 32,000 hexadecimal digits to check the frequency at which each digit appears, as well as the likelihood that particular digits would more likely follow others. The output was reasonably uniform with expected deviations appropriate to the sample size as can be seen in Figure 6.

FIGURE 6 – Deviation from uniformity for digits from a simulation of the 24-bit linear-feedback shift register. 32,000 digits were analyzed, so the expected frequency of each digit is about 2,000. Statistically, these deviations are what would be expected from the sample size.

LIFE IS EASIER WITH MCUS
While the above circuit has the advantage that no firmware is required, I programmed the same linear-feedback shift register into a Microchip Technology PIC microcontroller (MCU) and gave the device a few options. Since it’s possible to program the PIC into a sleep mode that consumes very little current, this second random number generator is battery powered, and it operates by a push button switch. Not only does the device display random digits, but it also simulates dice throws and it will answer a yes/no question.

The simplicity of the circuit is shown in Figure 7. The PIC 16F630 MCU has a sufficient number of I/O pins to drive the 7-segment LED display, detect the push button and mode switches, and provide in-circuit serial programming. A center-off toggle switch selects one of three modes: a mode that gives a sequence of six random numbers, another that gives two random numbers from 1-6, and another that randomly gives a “Y” for yes or an “N” for no. The last mode is ideal for making difficult management decisions.

FIGURE 7 – Circuitry for the linear-feedback shift register random number generator as simulated by a PIC MCU. Using an MCU allows several modes of operation. The mode switch resistors are powered by the connection at RC5 so they don’t draw power when the PIC is in sleep mode.

I built the entire circuit—including battery holder, circuit board, switches and 7-segment display—into a container I built from a piece of PVC pipe purchased at a home goods store. I used a PVC end-cap as a removable base to allow access for battery replacement. The current-draw of the device is so small that the batteries will last nearly their shelf life with occasional use. A photo of the device is shown as Figure 8.

— ADVERTISMENT—

Advertise Here

FIGURE 8 – Battery-powered random number generator based on a PIC MCU. A push of the button gives either six random digits, two rolls of six-sided dice, or a yes/no answer, depending on the selected mode. For this version, a simulated 24-bit linear-feedback shift register is used with taps at stages 1, 3, 4 and 24 and the BCD data is taken from stages 21-24. The compiler has a built-in random number generator that can be used instead of the simulated linear-feedback shift register.

Unlike the first random number generator, the MCU version requires a firmware program that I wrote using the PICBasic Professional compiler (ME Labs, melabs.com). Because I use Linux exclusively, I run an older version of this compiler and its associated programmer on a very old Windows operating system installed as a virtual machine. On the Circuit Cellar code and files download webpage, you can find a compiled hex file to program a PIC MCU without needing a compiler. It would be easy enough to rewrite the source code in C so other compilers can be used, including the free MPLAB C18 compiler from Microchip, manufacturer of the PIC MCUs.

RESOURCES
A Million Random Digits with 100,000 Normal Deviates, RAND Corporation, The Free Press (1955), available at https://www.rand.org/pubs/monograph_reports/MR1418.html

George W. Brown, “History of RAND’s random digits—Summary,” in A.S. Householder, G.E. Forsythe, and H.H. Germond, eds., Monte Carlo Method, National Bureau of Standards Applied Mathematics Series, vol. 12 (Washington, D.C.: U.S. Government Printing Office, 1951), p. 31 ff, available at  https://www.rand.org/content/dam/rand/pubs/papers/2008/P113.pdf

ME Labs | www.melabs.com
Microchip Technology | www.microchip.com

PUBLISHED IN CIRCUIT CELLAR MAGAZINE • OCTOBER 2019 #351 – Get a PDF of the issue


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

 
 
Note: We’ve made the October 2017 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.

Become a Sponsor
Website | + posts

Dev Gualtieri received his PhD. in Solid State Science and Technology from Syracuse University in 1974. He had a 30-year career in research and technology at a major aerospace company and is now retired. Dr. Gualtieri writes a science and technology blog at www.tikalon.com/blog/blog.php. He is the author of three science fiction novels, and books about science and mathematics. See www.tikalonpress.com for details.