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.
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.
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.
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.
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.
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.
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.
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.
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.
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
PUBLISHED IN CIRCUIT CELLAR MAGAZINE • OCTOBER 2019 #351 – Get a PDF of the issue