Really, Really Random Number Generator

The basic schematic is shown in Figure A, and an equivalent breadboard layout in Figure B. The transistor that creates the noise is at top-left, labeled number 1. Its emitter is reverse-biased using 18VDC passing through a 4.7K resistor. Normally you donʼt abuse a transistor in this way, but if the current is limited, no damage will occur, and random signals will be created by occasional electrons forcing their way through the silicon NP junction. Their behavior is absolutely unpredictable, being determined by quantum mechanics.

Another 2 transistors amplify the signals, and because this is a high-gain analog amplifier, you must use short wires to avoid picking up stray electromagnetic fields. Amputate the unused collector lead of the noise-making transistor, and place all the transistors and the adjacent capacitor as close to each other as possible. (The capacitor prevents switching spikes from the digital section of the circuit from contaminating the analog section.)

When installing the Zener diode, remember that its cathode stripe should point away from the negative bus, unlike a regular diode. The Zener shunts voltages above 4.7VDC to ground, so the remaining signals can pass into a 74HC14 chip containing 6 inverters, each of which has a Schmitt trigger input. The first inverter generates a digital output that alternates at unpredictable intervals between approximately 0V and 5V.

Figure C illustrates the steps in noise processing.

Connected with the last of the inverters in the 74HC14 you’ll find a 10K resistor and a 100pF capacitor. This RC network generates pulses to clock the digitized noise into a 74HC164 shift register. You can use the states in the registers (or a subset of them) to randomize game behavior. If you need more states, simply chain another shift register to the first. Youʼll find a lot more information about shift registers in Make: More Electronics.

You can use two 9V batteries in series to create the 18VDC required by the transistors. Tap just one battery for 9V and pass it through the LM7805 voltage regulator to get 5VDC for the logic chips.

I’m assuming that your breadboard has a break in each of its vertical buses, allowing you to supply 18V to the top of the circuit and 5V to the bottom, sharing a common ground. Be careful about this! Test your breadboard, and if its buses are unbroken, you’ll have to remove the purple jumpers in Figure B and run separate wires to deliver 5V to the power pins for the logic chips. Also, the blue LED requires a 5V positive supply.

To test the circuit, reduce the clock speed by using a 100K resistor and 1µF capacitor instead of the 10K resistor and 100pF capacitor shown. Substitute an LED and series resistor for each of the yellow circles in Figure A, and you’ll see a random series of high and low states flowing through.

So far, so good. But how do you know if the number of high states will be the same as the number of low states, over a long period of time? In other words, is the output evenly weighted?

You may feel that this isn’t important, but if (for instance) you use the circuit to power a yes-no decision maker, maybe you won’t be happy if it says “yes” more often than “no.” Also, for serious applications such as cryptography, an unevenly weighted random source can allow someone to break the code.

The red and blue LEDs in Figure B address this problem. When the circuit is running at full speed, adjust the trimmer till the LEDs seem to be of equal brightness. This should give you approximately the same number of high states as low states in the logic output.

But how approximate is “approximate”? What if you want the number of high states and low states to be exactly equal?

The great computer scientist John von Neumann came up with a way to achieve this very easily. If we have a stream of random 0s and 1s which is not evenly weighted, all we have to do is sample the states in non-overlapping pairs. Where 2 digits are the same, we ignore that pair and move on. Where 1 is followed by a 0, we create an output of 1. Where 0 is followed by a 1, we create an output of 0. Now, no matter how skewed the input is, the output will be evenly weighted. Figure D shows a hypothetical example.

Why does it work? Well, suppose we have a big bucket full of marbles, one-quarter of them black and three-quarters of them red. The odds of picking a red one at random will be ¾, while the odds of picking a black one will be ¼. What are the odds of picking a red one followed by a black one? Easy: ¾ × ¼ = 3/16. What are the odds of picking a black one followed by a red one? Equally easy: ¼ × ¾ = 3/16. Therefore if you pull out a red-and-black pair, the odds of the first one being red are the same as the odds of it being black. This remains true even when we donʼt know the ratio of red-to-black in the mix, so long as the mix remains consistent. The process is inefficient, because weʼll be discarding identical pairs of marbles 10/16 of the time. But the result works.

Figure E shows how a few logic chips can apply the von Neumann principle, guaranteeing scrupulous equality of high and low logic states. This circuit replaces the 2 logic chips and their associated components in the original circuit in Figure A. 

The 555 timer drives a ring counter which applies power to each of its pins sequentially. The even-numbered pins are not used, to allow settling time between each output and the next. Pins 1 and 3 are processed through an XOR gate to clock in a couple of random bits of random noise from the transistors in the noise-generating circuit to the first shift register, which holds the data temporarily.

Another XOR gate has a high output if the 2 samples are different, and this clocks the first of the 2 samples into the second shift register, when prompted by pin 5 of the ring counter. After that, pin 7 of the counter restarts the sequence. The second shift register supplies your evenly weighted random digital output.

I used 4-bit shift registers because you can get 2 of them in a 74HC4015 chip, and I wanted to minimize the chip count. If you need more than 4 random bits, substitute an 8-bit shift register for the output. Iʼll leave it to you to figure out the placement of components in an actual circuit.

The goal is now fulfilled. You have a digital source that is really, really random, and can be applied to hundreds of games. Hook it up to an Arduino or Raspberry Pi and let the fun begin.

If you like, you can hook this circuit up to an Arduino or Raspberry Pi to start using the random output in your computer programs.

In fact, the 74HC164 can be skipped if you do this — just read bits right off the first digitizing gate of the 74HC14, and stack them up into bytes (or whatever you need) after the bits are onboard.

No coupling capacitor should be necessary, but for the Pi, you’ll need to shift the 5V signal to the Pi’s 3.3V inputs. There are a number of ways to do this, but a really safe one is to use an optocoupler. Drive the internal LED with the 5V signal from the 74HC14 and hook the phototransistor side of the optocoupler between ground and the GPIO pin. When the 74HC14 goes high, the GPIO pin gets grounded, and when

the 74HC14 goes low, the optocoupler shuts off and the GPIO pin gets routed to +3.3V via the Pi’s internal pull-up resistor.

To learn more about optocouplers, see Ask Make: Using an Optocoupler and the Encyclopedia of Electronic Components Volume 2, pp. 33-37, item #9781449334185 at the Maker Shed.

My von Neumann circuit wasn’t very elegant, because it wastes some chip functionality. Aaron came up with a more sophisticated circuit that uses just 4 positive-edge-triggered D-type flip-flops. It’s more difficult to understand, but worth the effort.

This kind of flip-flop does nothing until it senses the rising edge of a signal on its clock pin. At that moment, it samples the state on its D input and copies it to its output, customarily identified as Q. It copies the opposite state of the D input to its inverse output, properly known as not-Q, which is often written with a bar character above the Q, and may be referred to as Q-bar. Then the chip waits for the next clock signal, while maintaining the states of its outputs.

Now suppose that instead of a fluctuating D input, we wire the not-Q output back to the D input. This is shown in Figure F, where I’m assuming arbitrarily that we begin with a low clock input, a high Q output, and a low not-Q output tied back to the D input.

Step 2 in Figure F shows the rising edge of a clock signal arriving, but the chip hasn’t had time to respond yet.

In Step 3, the rising edge is over, having caused the flip-flop to copy the previous low state of the D input to the Q output. This means not-Q is now high, and is piped back to the D input, so that it becomes high, too.

In Step 4, another rising edge of a clock signal comes in. The chip hasn’t had time to respond yet — but by the time the rising edge has passed, the outputs will be reversed back to the way they were in Step 1, and the sequence will repeat.

Compare the sequence of inputs with the sequence of outputs. The outputs changed only once between high and low, while the inputs changed twice during the same period. The output frequency is half the input frequency. The flip-flop divides it by 2.

To do von Neumann processing, we want to sample noise data in pairs, so a divide-by-2 device can be useful. Figures G, H, and I show a simplified schematic running through a total of 9 steps. Arbitrarily, I’m beginning with all the Q outputs low and the clock low.

In Step 2, the rising edge of a new clock signal comes in but has not been processed yet.

In Step 3, the Q output from flip-flop A has gone high and becomes a clock input for flip-flop B, which has not had time to respond yet. The inverter at the bottom also provides a click input for flip-flop D, but its active-low Clear input is being held low, so flip-flop D does not respond.

In Step 4, flip-flop B responds to the clock signal by sampling the noise input at D and copying it to its Q output. I’ve used a purple line, as we don’t know whether the noise is high or low, because it’s random. This is passed along to the XOR gate.

In Step 5, a new clock signal comes in but has not been processed yet.

In Step 6, we see the results of the new clock signal, generating clock inputs for flip-flops C and D. Flip-flop D is no longer constrained by an active-low Clear input, so now it will respond.

In Step 7, flip-flop C responds by copying another noise sample to the second XOR input, and flip-flop D copies the XOR output (whatever it may be) to the clock input of a shift register. A high state of the input buffer will clock the input into the register.

In Step 8, the rising edge of a new clock signal comes in but has not been processed yet.

In Step 9, the result of the signal is to tell flip-flop B to take another new noise sample, and the process continues all over again (note that Step 9 is actually the same as Step 3).

Complicated? Yes, but very concise! Perhaps you’re thinking, “I could never design a circuit like that.” If so, you have company, because that’s exactly what I thought when I saw it. On the other hand, Aaron is a few years ahead of us in his experience doing this kind of thing.

Figure J shows a further enhancement of the circuit, including a counter and a shift register that can be accessed via a data bus.

The Q output of flip-flop D, which goes high whenever the von Neumann circuit has identified a 1 or 0 bit to clock into the shift register, is also connected to the clock input of a 74HC193 counter to count those bits. When the 8th bit arrives, the Q3 output of the counter chip goes high, causing several things to happen:

First, the byte is copied from the 74HC595’s shift register to its storage register. The 74HC595 contains 2 registers, which allows it to store a value that hasn’t been read yet while simultaneously shifting the next value in. This asynchronous capability can be used to increase transfer rates. This circuit does not take advantage of that capability, but that’s why it’s there.

Second, the Byte Available line goes high, signaling to an external circuit that a byte may be read from the 74HC595 chip.

Third, the entire circuit stops. Q3 is also tied to the input of an XOR gate, the other input of which is normally high. With both inputs high, the output of the XOR (labeled “Accumulate Bytes” in the schematic) goes low. This causes the input of the diode D2 to be pulled high, which jams the clock generator circuit by keeping C3 charged, halting clock pulses and preventing the waiting byte from being overwritten.

The circuit waits in that state for something to lower the ~Read Byte line. A typical application would connect the Byte Available line to a polled input or an interrupt on a host microcontroller or a system like a Raspberry Pi or Arduino. When the host system saw the Byte Available line go high, it would respond by lowering and raising the ~Read Byte line to read the byte.

You’ve probably noticed that, like the counter chip’s Q3, the ~Read Byte line is connected to several inputs. When it is toggled, several things happen:

First, the 74HC595 chip outputs the contents of its storage register onto pins Q0–Q7. Normally, it keeps those pins in a high impedence state, which is a fancy way of saying that it’s electrically disconnected. It doesn’t actually connect them until pin 13 ~OE (which stands for Output Enable) is pulled low. This allows it to share an 8-bit data bus with numerous devices, where only one device will be outputting at a time. A popular chip for connecting things to and reading from a shared data bus is the 74HC374. When using it to read data from a shared bus, the same ~Read Byte line can be tied to its clock input. Lowering the ~Read Byte line causes something to gate data to its inputs, and the rising edge causes it to clock that data in.

The next thing that happens is that the counter chip is loaded with zeroes, which in turn drops Q3 and clears the Byte Available line. This constitutes a hardware handshake. A signal from one thing indicates data available and a signal from another thing reads that data and clears the first signal.

Finally, when ~Read Byte is raised, the inputs to the Accumulate Bytes XOR are different once again. The clock is unjammed and begins to work on stocking the shift register with another byte.

If there isn’t anything connected to the circuit to pull ~Read Byte low, it’ll be a boring circuit to watch because it will halt as soon as it has a byte. However, you can cause it to run continuously by connecting the spare inverter between the Byte Available line and the ~Read Byte line. That will cause the ~Read Byte line to be dropped as soon as Byte Available goes high, effectively making the circuit read from itself as fast as it can. If you connect LEDs and current-limiting resistors to the 74HC595’s outputs, don’t forget to also disconnect its pin 13 and tie it to ground to make it output to the LEDs continuously. If you slow the sampling down to about 60Hz with a 10K resistor and a 1µF capacitor in the clock circuit, you should see approximately one byte per second, depending on the noise balance.

Learn electronics with Charles Platt’s Make: Electronics books and our companion parts packs from the Maker Shed.