If you want to start an argument at a Hackaday meeting, you have only to ask something like “How much does this weigh?” or “What time is it?” But if you really want to start a street brawl, you can always say, “Are these numbers random?” Making random numbers that are actually random is actually a tough nut to crack. Most of what we do is, technically, pseudo-random (but we’ll say random number and assume you know what we mean). One way to generate seemingly random sequences is to use a linear feedback shift register or LFSR. You can use LFSRs in software, but they are also very useful in hardware design and [Adam Taylor] takes us through his use of them on FPGAs in a recent post. Continue reading “Linear Feedback Shift Registers For FPGAs”→
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.
The core of the project is a 242-bit linear-feedback shift register (LFSR) constructed from (31) 74LS164’s. An XOR gate and inverter computes the next bit of the sequence by XNOR’ing two feedback bits taken from taps on the register, and this bit is then fed into bit zero. Depending on which feedback taps are chosen, the output sequence will repeat after some number of clock cycles, with special sets of feedback taps giving maximal lengths of 2N – 1, where N is the register length. We’ll just note here that 2242 is a BIG number.
The output of the LFSR is displayed on a 22×11 array of LEDs, with the resulting patterns reminiscent of retro supercomputers both real and fictional, such as the WOPR from the movie “War Games,” or the CM2 from Thinking Machines.
The clock for this massive shift register comes from – wait for it – a 555 timer. A potentiometer allows adjustment of the clock frequency from 0.5 to 20 Hz, and some extra gates from the XOR and inverter ICs serve as clock distribution buffers.
We especially love the construction on this one. Each connection is meticulously wire-wrapped point-to-point on the back of the board, a relic originally intended for an Intel SBC 80/10 system. This type of board comes with integrated DIP sockets on the front and wire-wrap pins on the back, making connections very convenient. That’s right, not a drop of solder was used on the board.
You can see 11 seconds of the pattern in the video after the break. We’re glad [Quinn] didn’t film the entire sequence, which would have taken some 22,410,541,156,499,040,202,730,815,585,272,939,064,275,544, 100,401,052,233,911,798,596 years (assuming a 5 Hz clock and using taps on bits 241 and 171 ).
What do you do, when you need a random number in your programming? The chances are that you reach for your environment’s function to do the job, usually something like rand() or similar. This returns the required number, and you go happily on your way.
A shift register configured as a pseudo-random number generator. [by KCAuXy4p CC0 1.0]Except of course the reality isn’t quite that simple, and as many of you will know it all comes down to the level of randomness that you require. The simplest way to generate a random number in software is through a pseudo-random number generator, or PRNG. If you prefer to think in hardware terms, the most elementary PRNG is a shift register with a feedback loop from two of its cells through an XOR gate. While it provides a steady stream of bits it suffers from the fatal flaw that the stream is an endlessly repeating sequence rather than truly random. A PRNG is random enough to provide a level of chance in a computer game, but that predictability would make it entirely unsuitable to be used in cryptographic security for a financial transaction.
There is a handy way to deal with the PRNG predictability problem, and it lies in ensuring that its random number generation starts at a random point. Imagine the shift register in the previous paragraph being initialised with a random number rather than a string of zeros. This random point is referred to as the seed, and if a PRNG algorithm can be started with a seed derived from a truly unpredictable source, then its output becomes no longer predictable.
Selecting Unpredictable Seeds
Computer systems that use a PRNG will therefore often have some form of seed() function alongside their rand() function. Sometimes this will take a number as an argument allowing the user to provide their own random number, at other times they will take a random number from some source of their own. The Sinclair 8-bit home computers for example took their seed from a count of the number of TV frames since switch-on.
The not-very-random result of a thousand analogRead() calls.
The Arduino Uno has a random() function that returns a random number from a PRNG, and as you might expect it also has a randomSeed() function to ensure that the PRNG is seeded with something that will underpin its randomness. All well and good, you might think, but sadly the Atmel processor on which it depends has no hardware entropy source from which to derive that seed. The user is left to search for a random number of their own, and sadly as we were alerted by a Twitter conversation between @scanlime and @cybergibbons, this is the point at which matters start to go awry. The documentation for randomSeed() suggests reading the random noise on an unused pin via analogRead(), and using that figure does not return anything like the required level of entropy. A very quick test using the Arduino Graph example yields a stream of readings from a pin, and aggregating several thousand of them into a spreadsheet shows an extremely narrow distribution. Clearly a better source is called for.
Noisy Hardware or a Jittery Clock
As a slightly old-school electronic engineer, my thoughts turn straight to a piece of hardware. Source a nice and noisy germanium diode, give it a couple of op-amps to amplify and filter the noise before feeding it to that Arduino pin. Maybe you were thinking about radioactive decay and Geiger counters at that point, or even bouncing balls. Unfortunately though, even if they scratch the urge to make an interesting piece of engineering, these pieces of hardware run the risk of becoming overcomplex and perhaps a bit messy.
The significantly more random result of a thousand Arduino Entropy Library calls.
The best of the suggestions in the Twitter thread brings us to the Arduino Entropy Library, which uses jitter in the microcontroller clock to generate truly random numbers that can be used as seeds. Lifting code from the library’s random number example gave us a continuous stream of numbers, and taking a thousand of them for the same spreadsheet treatment shows a much more even distribution. The library performs as it should, though it should be noted that it’s not a particularly fast way to generate a random number.
So should you ever need a truly random number in your Arduino sketch rather than one that appears random enough for some purposes, you now know that you can safely disregard the documentation for a random seed and use the entropy library instead. Of course this comes at the expense of adding an extra library to the overhead of your sketch, but if space is at a premium you still have the option of some form of hardware noise generator. Meanwhile perhaps it is time for the Arduino folks to re-appraise their documentation.
When [::vtol::] wants to generate random numbers he doesn’t simply type rand() into his Arduino IDE, no, he builds a piece of art. It all starts with a knob, presumably connected to a potentiometer, which sets a frequency. An Arduino UNO takes the reading and generates a tone for an upward-facing speaker. A tiny ball bounces on that speaker where it occasionally collides with a piezoelectric element. The intervals between collisions become our sufficiently random number.
The generated number travels up the Rube Goldberg-esque machine to an LCD mounted at the top where a word, corresponding to our generated number, is displayed. As long as the button is held, a tone will continue to sound and words will be generated so poetry pours forth.
If this take on beat poetry doesn’t suit you, the construction of the Ball-O-Bol has an aesthetic quality that’s eye-catching, whereas projects like his Tape-Head Robot That Listens to the Floor and 8-Bit Digital Photo Gun showed the electronic guts front and center with their own appeal.
It’s time to get those jack-o-lanterns twinkling for Halloween. If you don’t want to use candles or buy a jack-o-lantern light this Halloween you can do like [Johannes Bauer] and code your own pseudo-random flickering super bright LED. His wife wanted their pumpkin to be illuminated this year and he knew it would be easy to do with an Arduino, but that would be overkill for such a simple project. Plus, he doesn’t have an arduino. [Johannes] used very few components; 4 slightly depleted AA batteries, a super bright LED, 680 ohm resistor and a little custom code on an 8 pin ATtiny13. The circuit does work great for a pumpkin lantern but his video is more of a tutorial on coding linear congruential generator (LCG) for the 8 bit pseudo-random LED flickering.
The code is short and can be gleaned from the YouTube video. [Johannes] used avr-gcc to compile and has packaged his code and build scripts for download. The hex file can be flashed over to the chip using avrdude or AVR Studio. If you have any ATtiny13s lying around you should cobble this hack together just in time to emulate that real look of a pumpkin candle without the hassles and hazards of real flames.
If you want something with a lot more light that still has that candle like flicker then checkout “Flickering Pumpkin Lanterns” that used the signal from LED tea lights to power some 12 V lamps.
Follow along after the break to watch [Johannes Bauer’s] video.
