LFSR-based "random" circuits

[tetsujin]

The question came up on SMA Nerd Herd about how to make a random-looking light effect. I didn't really know a good answer (and this is something that has bothered me in the past) but I found a good answer online so I thought I'd share it here, too.

"Fire" effect flasher circuit

This circuit uses three ICs - a timer, a shift register, and XOR gates - to create a pseudo-random bit sequence. This kind of random number generator is called a Linear Feedback Shift Register - and one of the great things about it is how easy it is to implement, whether you're using ICs or writing a program for a computer or microcontroller...

The way it works is you've got a shift register: this is a circuit which takes serial data and a clock in and stores the last 8 (or however many) serial bits and makes them available as pin outputs. So if you had a shift register set up like this:

Input line: 1 Output lines: 0 1 1 0 0 1 0 0

And then you clocked it, you'd wind up with this:

Output lines: 1 1 0 0 1 0 0 1

See, everything that was already stored got shifted up, and the new bit got clocked in at the end of the buffer. That's a shift register in a nutshell...

The way an LFSR works is it uses XOR gates to generate the shift register's input as a function of some of its outputs. The "fire" circuit I linked does this by tying four of the shift register outputs together, along with a fifth input that's always high, using XOR gates. The end result is that if there's an even number of those source bits "high", then the new bit will be high. If there's an odd number of them "high", then the new bit will be low.

So that much gets you an easy-to-implement "flicker" effect. If you know how to work with microcontrollers, this kind of sequence is also very easy to implement in assembly, and it can be used as a simple "random number" sequence.

Going back to the shift register I was showing before:

Output lines: 0 1 1 0 0 1 0 0

If the "taps" are on bits 7, 5, 4, and 2:

Output lines: 0 1 1 0 0 1 0 0

That's two out of four bits set - "even", so the next bit would be a one.

The main limitations of an LFSR are that it's entirely deterministic, it will loop through a sequence of states determined by the number of bits in the shift register and the location of the "taps" where the XOR gates are attached, and at some point will return to its initial state and restart the same sequence. For an 8-bit shift register, for instance, the there will be no more than 255 states in the loop. Still, it's very easy to implement in hardware or software, and for many applications it's probably "good enough" that people won't notice that it's not really random...

I've tested the 8-bit LFSR using a microcontroller and an LED - with the taps where I put them, it runs through about 220 states. I'm using the bit sequence to drive an LED, updating about 30 times a second. So the whole sequence should repeat every 7 seconds, roughly. In practice, I can't follow the pattern. It just looks "blinky". :)

[macfrank]

I think the main issue with the LFSR is that the 555 is producing a regular clock signal. National Semiconductor used to make a handy audio frequency noise generator IC that was easy to work with; they're next to impossible to find now.
You could amplify the popcorn noise in some diodes, or thermal & flicker noise in resistors, but that really adds complexity to the circuit.
One cool noise generator I saw used a simple AM radio circuit, tuned to a strong AM station to generate the random noise signal which is then amplified. It's in the audio range and truly random!

[tetsujin]

I think the main issue with the LFSR is that the 555 is producing a regular clock signal.

Well, the clock interval is consistent but the output changes - So even though it's just deciding, every clock interval, whether the LED is on or off, you get stretches of time between 1-7 clocks long where the LED stays on or stays off. At 30Hz I think the effect is pretty good. Could be better but I feel like it's a good starting point. I've seen some pretty awful "flicker" effects done in models with just digital logic circuits (4060's and such) - it made me weep, how obviously non-random those effects looked...

One cool noise generator I saw used a simple AM radio circuit, tuned to a strong AM station to generate the random noise signal which is then amplified. It's in the audio range and truly random!

Oh yeah, I think I remember hearing about that on here before... I imagine that'd work pretty nicely for certain things...

From my perspective, most of the applications where I'd be using random-something would be microcontroller-based. So for what I'm doing it's usually better to solve problems with more code rather than more circuitry. Still, I have given some thought to adding another source of randomness - maybe low bits from an unused A2D line...

[macfrank]

From my perspective, most of the applications where I'd be using random-something would be microcontroller-based. So for what I'm doing it's usually better to solve problems with more code rather than more circuitry. Still, I have given some thought to adding another source of randomness - maybe low bits from an unused A2D line...

That's what I've been looking for. You can amplify the tiny AM radio (it only needs a small cap, a coil of wire for the antenna and a diode - the cheaper and crappier the better) and run it through a comparator to generate 5V TTL (or 3.3V) square waves and use that directly to trigger a typical micro's internal counter.

[MillenniumFalsehood]

I'd like to know what advantages this has over a simple tea-light.

[Balok]

Awesome tetsujin! Something I can modify for pseudo-randomly lighting the windows in the 18" E. Thank you for posting! Shift register, hadn't considered it.

[Mr. Engineer]

Not sure if this is a good idea but to create more 'randomness', one could interface any EPROM (especially from old machines) and read from it. The data that comes out, is quite random methinks.

(But I don't have an EPROM reader, I just set a microcontroller to read some funny addresses on it once.)

[macfrank]

Not sure if this is a good idea but to create more 'randomness', one could interface any EPROM (especially from old machines) and read from it. The data that comes out, is quite random methinks.

But that would repeat the pattern every few K bytes (depending on the size of the EPROM) which may be petty noticeable if you cycle through it fast enough. An EPROM may have unused sections, so you'll hit a patch of 0xFF that is not random.

[tetsujin]

Not sure if this is a good idea but to create more 'randomness', one could interface any EPROM (especially from old machines) and read from it. The data that comes out, is quite random methinks.

I did something somewhat similar to get random number sequences on a PIC before - more precisely I ran a program on the PC to generate a sequence of random numbers, then stored them as a data table in the PIC's program ROM, and each time I needed a "random" number, I'd take the next one from the sequence. The quality of the sequence you get with a method like that is probably about the same as you'd get from an LFSR - but the LFSR takes up less memory on the microcontroller...

How easy it is for people to spot the recurring pattern depends in part on how you use it. I was using the random number sequence to influence behavior decisions, so it probably wasn't too noticeable. If I'd been driving the random numbers straight out to a LED, the pattern would have been much easier to spot, I think.