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
shift register
and examine one particular set of coefficients, called TAPS
in the
code,
to see what sort of sequence it produces.
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.
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
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/8
th
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.
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)