The Simplest Of Pseudo Random Number Generators

A truly random number is something that is surprisingly difficult to generate. A typical approach is to generate the required element of chance from a natural and unpredictable source, such as radioactive decay or thermal noise. By contrast it is extremely easy to generate numbers that look random but in fact follow a predictable sequence. A shift register with feedback through an XOR of its output and one of its stages will produce a continuous stream of pseudo-random bits that repeat after a set period.

[KK99] has created the simplest possible pseudo-random binary sequence generator, using a three-bit shift register. It’s realised on a pleasingly retro piece of perfboard, with a CD4047 as clock generator and a 74HC164 shift register doing the work. Unusually the XOR gate is made from discrete transistors, 2N3053s in bulky TO39 packages, and for a particularly old-fashioned look a vintage HP LED display shows the currently generated number. A relatively useless pseudo-random sequence with a period of seven bits is the result, but the point of this circuit is to educate rather than its utility. You can see it in operation in the video below the break.

We had a demonstration of the dangers of using a pseudo-random sequence back in 2016. The German military cipher nicknamed “Tunny” by British codebreakers relied upon a mechanical sequence generator, and the tale of its being cracked led to the development of Colossus, the first stored-program electronic computer.

12 thoughts on “The Simplest Of Pseudo Random Number Generators

  1. This reminded me of what Uno Attack might use. The game uses a pseudo-random sequence that you can memorize. If you turn off the game and back on the sequence is the same.

    1. This would cost too much for a toy. You /might/ be able to talk them into an extra transistor or two, but even that will probably get stripped out along the way.

      Most toys have basically no source of entropy for an RNG seed… The best I’ve managed is a handful of bits from the power-on state of the RAM, but even that is surprisingly consistent on a given device. On all of my projects that have any amount of NVRAM of any sort, I work around this by storing half of the RNG’s state to the NVRAM occasionally, and using the few bits of RAM for the other half on startup. But most toys don’t have any NVRAM, either.

      1. Just have an extra pin on the microcontroller connected to a floating PCB trace. That works especially well if it’s an analog pin. Or read the voltage of a pin connected to a LED which would change slightly depending on the ambient light level.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.