An example LFSR
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
and examine one particular set of coefficients, called
TAPS in the
to see what sort of sequence it produces.
In particular, let’s look at a 5-stage
TAPS register given by
00101. You can see a picture of the
logic required to implement this
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
Even better, I picked this particular set of coefficients in order to
guarantee that this shift
register has a
For a register
with five internal bits within it, bits that can never all be equal to zero,
this maximum length
31. Hence, this
has an output sequence of
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.
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
works. Further, as an aside, I’ve seen a lot of examples of how a 3-stage
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
Working through the states
Let’s assume that our example starts with an
INITIAL_FILL of one–just like
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
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
10000 state: the new top bit is set by the sum
Since there are no ones in bit positions
2 for a couple of clock
periods, the shift
just shifts to the right uneventfully until it gets to
time there’s a bit in position
The state after
10010, since the sum of
1 (position 2) and
(position 0) is one and that goes into the top bit while the other bits
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
1+0 and getting a one as the result, we now have
1+1. As you
recall, this addition is done
over GF(2). It is equivalent
to an exclusive or, and so the
new MSB is now
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
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
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
00 does this sequence produce?
7 respectively. This is close to the probability of
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?
3 times respectively.
This follows the pattern, and nearly matches the probability of
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.
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.
Even as Sodom and Gomorrha, and the cities about them in like manner, giving themselves over to fornication, and going after strange flesh, are set forth for an example, suffering the vengeance of eternal fire. (Jude 1:7)