Hacky Random Number Generator / Cat Toy

For my entry to the Dangerous Prototypes 7400 Contest, I decided to make a true random number generator. In particular, I wanted a latching RNG — not merely a continuous stream of numbers, but a continuous stream which I could sample at intervals. The circuit would be made up of a minimal number of digital logic parts. And deliberately inducing noise into the digital circuit would involve breaking all the usual design rules, which is fun.

Design

This circuit generates true random numbers using just a 74HC595 shift register and a 74HC04 hex inverter.  Pulsing the contact switch updates the latch from the shift register and displays the 8 bits on an LED bar. Three NOT gates are used to make an oscillator with a triangular waveform that clocks the shift register. The overflow from the shift register is inverted (again with a triangular signal) and fed back in as data to the shift register. (This arrangement is known as a Johnson counter.) The slow rise times on these inputs to the shift register render the gates liable to random oscillation. Vulnerability to supply line fluctuations was maximized by omitting bypass capacitors.

Does it work?! Well, what you would expect from the counter a continuous marquee of 8 zeroes and 8 ones on the shift register, circulating endlessly. What you actually see in the video is considerably less predictable.

Application

I had in mind a servo that would continuously reorient itself in random directions, after a delay of random length. The addition of a 4538 precision monostable and an array of timing resistors enables a servo to rotate to one of 16 random orientations each time the storage register is clocked. The other 4 bits of the shift register govern a random wait timer implemented using the other monostable on the 4538. Whenever the wait comes to an end, a signal is sent to toggle the storage register clock and obtain a new 8 bit random number. The servo will begin to move to its new position. Meanwhile, another signal is sent to an inverter that clocks the monostable after a short delay, initiating the new wait.

What was the point of this random servo twirler? Why, to entertain cats the Afrotech way — only using 3 logic chips and a few passive components, instead of a $89 robotics development platform and a bunch of C code. (Apologies to www.afrotechmods.com for ripping off the video clip of Pikachu chasing the laser dot.)

Materials

Random Number Generator
74HC595 shift register
74HC04 hex inverter
2x 100 kΩ, 1x 1 MΩ, 1x 100 Ω resistors
3x 100 nF capacitor
10 segment LED bar

Cat Toy
4538 precision monostable
10 kΩ, 33 kΩ, 2x 68 kΩ, 100 kΩ, 130 kΩ, 2x 150 kΩ, 2x 330 kΩ, 680 kΩ resistors
22 nF, 100 nF, 47 uF capacitors
8x 1N4148 signal diodes
5 V hobby servo
laser pointer

Construction tips

This project is Easy - try it! A great resource for learning about how to use digital logic properly, and especially how to construct oscillators and monostables, is the Doctronics site.

Nitty Gritty Detail Stuff

The usual implementation of a RNG using digital logic, I reckon, would probably be something like a Fibonacci linear feedback shift register made from one or more 74HC164 8 bit shift registers, and a number of XOR gates. The pseudorandom data could be sampled using 74HC374 octal flip flops, or some other variety of latch.

These kind of pseudorandom number generators work fine for simple applications like flickering LEDs, but didn't satisfy me in a couple of respects. First, the same sequence is obtained every time the RNG is run, unless some other input is used to reseed it. Second, the sequence eventually repeats.

It is well known that the noise in digital circuits can be exploited to generate true random numbers. For example, oscillatory metastability can result from phase jitter in a ring of inverters or from violating the setup and hold conditions of a flip-flop. The approach I took exploited the phenomenon of multiple clocking of shift registers in response to slow rise times. Distortions in the leading or trailing edges of input signals render digital gates vulnerable to voltage fluctuations on the supply line. A TI application note on the Implications of Slow or Floating CMOS Inputs describes how unpredictable outputs can result:

With increased speed, logic devices have become more sensitive to slow input edge rates. A slow input edge rate, coupled with the noise generated on the power rails when the output switches, can cause excessive output errors or oscillations. [...]

These functional problems are due to voltage transients induced on the device’s power system as the output load current (IO) flows through the parasitic lead inductances during switching. Because the device’s internal power-supply nodes are used as voltage references throughout the integrated circuit, inductive voltage spikes affect the way signals appear to the internal gate structures. For example, as the voltage at the device’s ground node rises, the input signal appears to decrease in magnitude. This undesirable phenomenon can then erroneously change the output if a threshold violation occurs.

In the case of a slowly rising input edge, if the change in voltage at GND is large enough, the apparent signal at the device appears to be driven back through the threshold and the output starts to switch in the opposite direction. If worst-case conditions prevail (simultaneously switching all of the outputs with large transient load currents), the slow input edge is repeatedly driven back through the threshold, causing the output to oscillate.

I deliberately set out to introduce and capture this noise by recycling the same few bits through a shift register, via an inverter. The clock signals and inverter outputs had triangular rather than square wave outputs in order to violate the setup and hold time requirements of the shift register inputs. The shift register was sampled at long intervals relative to the clocking frequency so that there was ample opportunity for multiple clocking and oscillation in the outputs to randomize the sampled numbers. I deliberately omitted bypass capacitors to maximize susceptibility to supply line fluctuations.

It's worth pointing out the degree to which oscillation can be induced in the shift register is likely to depend on all sorts of factors such as VCC (which affects the noise margin of CMOS devices), the switching load on the circuit, capacitance and ripple on the supply line, and manufacturing tolerances of the individual chips.

I did not validate the RNG against the various test batteries that are available to test the randomness of the output. Just from eyeballing the output it is pretty clear that there is quite a lot of autocorrelation between successive bits in the data. I speculate that better randomness would be obtained by sampling individual bits at widely spaced intervals and by "burning in" the RNG by discarding the results from the initial period of operation. Various solutions exist to remove bias and "whiten" the frequency spectrum of hardware RNGs at the expense of greater circuit complexity, e.g. XOR'ing with the output of a pseudo RNG.

Linkbacks

Dangerous Prototypes