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”
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.
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.
seems a lot of work when you could use a 8266 or esp32 and get real random numbers…
And how much would that ESP8266 cost in a mass market product compared to whatever they are using now?
…Did you miss the “cost” part? We get our processors for less than a nickel.
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.
95% of toy-grade microcontrollers have no ADC(And the ones which do cost extra), and schmitt-trigger inputs don’t work for picking up noise.
There’s got to be something.
Even if you just time the duration of user input that starts it? That’s what I used to do on 10f508s
a 3904 NPN used as an avalanche diode… pretty freaking cheap.
Yes, but then you need an inverter for the higher voltage needed for avalanche.
Still worth it if you something reasonably random.
LFSR is the least random.
My iPod Classic used to have only a few “random” options of playlist if I put it to shuffle all songs. I hated that.
Gee am I missing something? I don’t see any mention of an LFSR (Linear Feedback Shift Register) anywhere here or in the Author’s HaD.io post. Is this NOT an LFSR in some way? There’s a lot that goes into a good LFSR and finding the “maximal” feedback polynomial(s) [coefficient taps] is a computational pain in the byte:
Please be kind and respectful to help make the comments section excellent. (Comment Policy)