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

Today, let'due south go back to the Fibonacci class of a shift annals and examine 1 detail fix of coefficients, called TAPS in the code, to run into what sort of sequence it produces.

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

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

Even meliorate, I picked this particular set of coefficients in guild to guarantee that this shift annals has a maximum length. For a register with five internal bits within information technology, bits that tin never all exist equal to aught, this maximum length is ii^5-ane or 31. Hence, this register has an output sequence of 31 pseudorandom bits.

Finally, earlier nosotros get-go 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 annals. That figure is shown below in Fig two.

Fig two: The Generic Course of a Fibonacci LFSR Implementation
Generic Fibonacci LFSR form

The biggest deviation you may notice between these two figures is that the multiplies have been removed. Those taps that were multiplied with goose egg in this instance 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 improve, 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 higher up.

My hope today is that, by specifically stating what the coefficients of an example LFSR are, nosotros 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-phase LFSR works in text books (TAPS=3'b011). I wanted this presentation to be different plenty to generate something barely not-petty, and so this example produces a longer sequence. Experience free to allow 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

Allow's assume that our example starts with an INITIAL_FILL of one–just similar the implementation nosotros presented earlier. At each stride, the LFSR works by shifting every fleck to the right by 1, and and then calculating the top bit. In our case, that top chip is ready by the sum (XOR) of bits 0 and ii. You lot can run into the fix 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 country: the new meridian fleck is prepare by the sum (XOR) of 0 and i–resulting in 1.

Since at that place 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 fourth dimension there's a flake in position 2. The state after 00100 is 10010, since the sum of 1 (position ii) and 0 (position 0) is one and that goes into the top bit while the other $.25 shift down.

One country later, the annals equals 01001 and now there'southward a bit in position 0, so the state following has a ane in the MSB.

We can follow this logic down to 01101. At this state, instead of calculation 0+1 or one+0 and getting a 1 equally the issue, nosotros now have 1+one. Every bit you lot may recall, this addition is done over GF(2). It is equivalent to an exclusive or, and and then the new MSB is at present 0.

By this bespeak in time, you should just about have the hang of it. If non, experience gratuitous to work through usa shown on the left and see if you can generate each of them. You may also find that, later 31 states, the country returns to our initial state–hence our sequence is 31 bits long.

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

Even better, should you wish to arrange where in this sequence yous wish to commencement, all yous demand to do is modify the INITIAL_FILL. For that matter, if you lot sort the INITIAL_FILL values, y'all'll find that every value but zero gets used–so the register state just determines where you are within the sequence.

Now allow's turn our attention to wait at some randomness properties of this output sequence. Get-go, allow'due south count how many 1's this sequence produced: 16. That means that the sequence has (almost) a probability of one/2 for producing a one. How almost runs? How many runs of 11 or 00 does this sequence produce? eight and seven respectively. This is close to the probability of 1/iv that y'all'd desire. What about runs of iii? How many times do y'all find three i'due south in a row, or three 0's in a row? 4 and iii times respectively. This follows the blueprint, and nearly matches the probability of 1/viiith that we would expect.

Judging from these observations, the sequence certainly looks random. Indeed, it is random enough for nearly signal processing purposes. It'due south merely non random enough for cryptography–only I'1000 really not enough of a cryptographic skilful to annotate further on what it takes to create true cryptographically random numbers.

Conclusion

Hopefully running through this instance has helped to demystify LFSRs for you. Because they are so easy to implement, their logic maps and so nicely to just a couple of transistors, and because their results await 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 tin can get from my FPGA to handle at its fastest speed. To get there, I'thousand still going to need to create a LFSR implementation that can produce multiple output bits per clock. We'll take to come back to this topic once again, therefore, in guild to examine and explicate how to do this.