This article is about Linear Feedback Shift Registers, commonly referred to as LFSRs.
An LFSR is like a black box into which you feed a number, and the generated output is some linear function of the input (typically created by some combination of shifting, and ExclusiveOR, of the bits).
They are deterministic; the same input will always give the same output. They have lots of cool uses, but first let’s take a look at how they work. The particular kind of LFSR I’m going to model today is called a Galois LFSR, named after the French mathematician Évariste Galois (who tragically perished after being shot in a duel at the young age of just 20).
The diagram below shows a binary representation of a 16bit Galois LFSR. The basic premise of the LFSR is that all the bits of the input are shifted right one position. Some bits are shifted, unchanged; however, some bits potentially change by the application of XOR operations. The bits that could change are called taps, and these taps provide one input into a twoinput XOR gate. The other input to the gate is provided by the LSB of the input stream that will get shifted off the end with the operation.
An exclusiveOR gate (XOR), is a very common component in electronics. The easiest way to think about it is with the phrase ”One or the other, but not both”. It has many interesting uses in electronics and computer science (particularly as applying the XOR function twice in a row with the same value returns a number to its original state). A truthtable, and symbol, for a twoinput gate is show here.

Because of the way these gates are applied, if there is no tap, each bit is shifted along unchanged. If there is a tap, and the LSB of the number is set, these tapped bits are inverted before being shifted over. If the LSB is not set, the tapped bits are shifted unchanged.
Here is a fragment of pseudo code showing an LFSR function:
if (n & 1) { n = (n >> 1) XOR t; }
else { n = (n >> 1); }
It really is pretty simple. If the LSB is set (n & 1) then shift over one position >> and XOR with the tap mask. Otherwise just shift it over.
The result of these shifts is that, for a given input, a new output is generated (providing the input is not zero; if all the bits on the input are zero, the output will also be zero).
The new output can be fed back in to generate a new output, and so on.
For a given input, eventually the number returns back to the starting number in a loop (each output is determinsitic from the input). Below is an example of a four bit LFSR, seeded with the number 1 (the left most box in the animation below).
In this example, the tap mask is set to 1010, and applying the LFSR transitions it to 10, then 5, 8, 4, 2, and back to 1
After a cycle of six, the input returns to 1 and some combinations are unvisited.
There are certain “magic” tap masks that create an optimal cycle in which every bit combination is visited in the cycle. For a 4bit register, one of these masks is 1001. No matter what the input (providing it is not zero), the LFSR will cycle around through all 15 numbers 115 and return to the starting point. Below is an animation of this happening.
This cycle is: 1, 9, 13, 15, 14, 7, 10, 5, 11, 12, 6, 3, 8, 4, 2
(There are only two bit patterns that generate perfect 4bit LFSRs, the other is 1100).
Perfect LFSRs are incredibly useful, as they provide a pseudorandom shuffling of all the numbers. Every combination of bits will have been passed through, and all that is needed is just a couple of lowlevel instructions (and better still if you are implementing in hardware; all you need is a couple of logic gates, and the next number can be generated on the next clock tick).
You can be sure that every number will be seen without having to keep a track of what has been seen already, and you don’t need to keep an array in memory for the order to visit things.
The bits come out in pseudorandom order; they are not totally random (after all they are mathematically determined based on the input), but they are sufficiently mixed up so that, to the casual eye, they are random. As they are in a cycle, each number appears once so they are perfect for generating white noise.
If you were writing test cases and wanted to expose your code to all possible inputs, but not in sequential order, you could use a perfect cycle LFSR. If you wanted to ensure you’d cycled through them all (a perfect Hamilton cycle), even if you used a clever trick like a De Bruijn Sequence, you’d still need extra memory, but not with an LFSR approach.
Probably one of the most contemporary uses of LFSR is in the Fizzle Fade, famously popular in the Castle Wolfenstein game. Here the idea was to gradually fill the screen with blood as the player died, in some random order. Each pixel only wanted to be visited once, but the expense of shuffling would have been a waste of memory and processing time (Even if done correctly, the FisherYates way).
If you attempted to do it using a purely random approach, there's no easy way to remove already visited pixels from the next selection.
An LFSR solution is perfect for this. Early game consoles were short on memory and these pseudorandom techniques were also used to generate 'random' configurations for rooms/dungeons and maps.
LFSR have use in cryptography, as an obfuscation technique. I'm hesitant to say securely, because, being mathematically determinstic, they are easy to crack, but they are useful for adding "entropy" to otherwise obvious blocks of contiguous data to obfuscate them, or to garble or obscure transmissions that, otherwise, in the clear would be obvious to the human eye/ear. XORing a stream of data with an LFSR, before transmission, would really mess it up to the casual observer, and it's trivial to remove it again by repeating the XOR operation (providing you know the tap mask and starting value), and the logic (or electronics) to perform this operation is very, very simple.
Finally, again at a hardware level, it is possible to use an LFSR as a simple "clock signal" generator. In certain appplications it might not be important that the clock is incremented in binary. The electronic logic to produce an increasing binary clock signal is complex, involving many gates. As we've seen the logic to produce the next LFSR value, in contrast, is really simple. If the application simply requires a deterministic, distinct, clock signal generator, then an LFSR might fit the bill nicely.
Below is an interaction that will allow you to experiment with 8bit LFSR.
Instructions:
Click on the next button to advance the LFSR to the next value.
The top boxes show the input (click on any box to manually change it).
The lower boxes show the configuration of the taps.
An "X" indicates that XOR will be applied.
These can also be manually toggled by clicking on them.
The connections button toggles the display of showing which values affect the next.
When in color mode, the colors represent will be passed to each cell on the 'next' cycle.
To the right is show the current value, the next, and the previous value.
The randomize button simply sets the inputs and tap positions to random values
The show bits adds an overlay to easy interpretation of the binary numbers.
If you want to try them out, here are the 16 perfect LFSR tap positions for 8bit numbers.
10001110  10010101  10010110  10100110 
10101111  10110001  10110010  10110100 
10111000  11000011  11000110  11010100 
11100001  11100111  11110011  11111010 
Maximum length LFSR (perfect LFSR taps) are known up to 32 bits. Here is an excellent source to find more details.
Bits  # Perfect Solutions 

4  2 
5  6 
6  6 
7  18 
8  16 
9  48 
10  60 
11  176 
12  144 
13  630 
14  756 
15  1,800 
16  2,048 
17  7,710 
18  7,776 
19  27,594 
20  24,000 
21  84,672 
22  120,032 
23  356,960 
24  276,480 
25  1,296,000 
26  1,719,900 
27  4,202,496 
28  4,741,632 
29  18,407,808 
30  17,820,000 
31  69,273,666 
32  67,108,864 
You can find a complete list of all the articles here.^{} Click here to receive email alerts on new articles.