Some time ago, we examined Linear Feedback Shift Registers (LFSR)s and particularly how to create the logic necessary to implement two different forms of an LFSR: a Fibonacci and a Galois form.

Today, let’s go back to the Fibonacci form of a shift register and examine one particular set of coefficients, called TAPS in the code, to see what sort of sequence it produces.

Fig 1: An example 5-stage LFSR
An example five stage LFSR

In particular, let’s look at a 5-stage LFSR with the TAPS register given by 00101. You can see a picture of the logic required to implement this shift register in Fig 1. In this figure, you can see how the output, together with the value of the register two stages earlier, both get added (XOR‘d) together to produce the new MSB of the shift register.

Even better, I picked this particular set of coefficients in order to guarantee that this shift register has a maximum length. For a register with five internal bits within it, bits that can never all be equal to zero, this maximum length is 2^5-1 or 31. Hence, this register has an output sequence of 31 pseudorandom bits.

Finally, before we start working through the numbers, I’d like to note that Fig 1 looks very similar to the figure we presented earlier when we described how to build a generic shift register. That figure is shown below in Fig 2.

Fig 2: The Generic Form of a Fibonacci LFSR Implementation
Generic Fibonacci LFSR form

The biggest difference you may notice between these two figures is that the multiplies have been removed. Those taps that were multiplied with zero in this example have been removed. Those taps that were multiplied by one have been replaced by a simple wire. That’s how multiplication is defined, and how it actually takes place within GF(2). Even better, all of this multiplication logic takes place as the LFSR logic is being synthesized–so that what is actually implemented ends up being identical to Fig 1 above.

My hope today is that, by specifically stating what the coefficients of an example LFSR are, we might be able to examine and understand how an LFSR works. Further, as an aside, I’ve seen a lot of examples of how a 3-stage LFSR works in text books (TAPS=3'b011). I wanted this presentation to be different enough to generate something barely non-trivial, and so this example produces a longer sequence. Feel free to let me know if you found this easier to understand.

Working through the states

Fig 3: Example LFSR States
States associated with our example 5-bit LFSR

Let’s assume that our example starts with an INITIAL_FILL of one–just like the implementation we presented earlier. At each step, the LFSR works by shifting every bit to the right by one, and then calculating the top bit. In our case, that top bit is set by the sum (XOR) of bits 0 and 2. You can see the set of states that this produces in Fig 3 on the left.

If you follow this formula, you’ll see that the 00001 state is followed by the 10000 state: the new top bit is set by the sum (XOR) of 0 and 1–resulting in 1.

Since there are no ones in bit positions 0 or 2 for a couple of clock periods, the shift register just shifts to the right uneventfully until it gets to 00100–the next time there’s a bit in position 2. The state after 00100 is 10010, since the sum of 1 (position 2) and 0 (position 0) is one and that goes into the top bit while the other bits shift down.

One state later, the register equals 01001 and now there’s a bit in position 0, so the state following has a 1 in the MSB.

We can follow this logic down to 01101. At this state, instead of adding 0+1 or 1+0 and getting a one as the result, we now have 1+1. As you may recall, this addition is done over GF(2). It is equivalent to an exclusive or, and so the new MSB is now 0.

By this point in time, you should just about have the hang of it. If not, feel free to work through the states shown on the left and see if you can generate each of them. You may also notice that, after 31 states, the state returns to our initial state–hence our sequence is 31 bits long.

As you transition through all of these states, remember that the LSB is the output of this pseudorandom number generator. Hence, you should be able to read down the column on the far right of Fig 3 on our left and read out the pseudorandom numbers that are being produced.

Even better, should you wish to adjust where in this sequence you wish to start, all you need to do is change the INITIAL_FILL. For that matter, if you sort the INITIAL_FILL values, you’ll find that every value but zero gets used–so the register state just determines where you are within the sequence.

Now let’s turn our attention to look at some randomness properties of this output sequence. First, let’s count how many 1’s this sequence produced: 16. That means that the sequence has (almost) a probability of 1/2 for producing a one. How about runs? How many runs of 11 or 00 does this sequence produce? 8 and 7 respectively. This is close to the probability of 1/4 that you’d want. What about runs of three? How many times do you find three 1’s in a row, or three 0’s in a row? 4 and 3 times respectively. This follows the pattern, and nearly matches the probability of 1/8th that we would expect.

Judging from these observations, the sequence certainly looks random. Indeed, it is random enough for most signal processing purposes. It’s just not random enough for cryptography–but I’m really not enough of a cryptographic expert to comment further on what it takes to create true cryptographically random numbers.

Conclusion

Hopefully running through this example has helped to demystify LFSRs for you. Because they are so easy to implement, their logic maps so nicely to just a couple of transistors, and because their results look random, they have a very important part to play in Digital Signal Processing (DSP).

My intent, however, is to create a module that can output these pseudorandom values at 950Mbps–or whatever I can get from my FPGA to handle at its fastest speed. To get there, I’m still going to need to create a LFSR implementation that can produce multiple output bits per clock. We’ll have to come back to this topic again, therefore, in order to examine and explain how to do this.