Understanding Linear Feedback Shift Registers – The Easy Way

Written by Dan Healy for UCSC’s CMPE125 class.

This tutorial will teach you how to use LFSRs, why other tutorials on the subject are so confusing, and how you can go about understanding the underlying mathematics if you really want to know.

First, a glossary.

**Linear Feedback Shift
Register (LFSR)**:

An
*n*-bit shift register which
pseudo-randomly scrolls between 2^{n}-1 values, but does it *very quickly* because there is minimal
combinational logic involved. Once it
reaches its final state, it will traverse the sequence exactly as before. It has many applications you should already
be familiar with if you’re reading this.

**Primitive polynomial**:

(very basically) A
polynomial of degree *n* that has the form:
1 + … + x^{n}, where (…) are zero or more terms with a coefficient of
1. x^{n} and 1 are always
present. For each degree, there can be
many different primitive polynomials. These
polynomials also must satisfy other mathematical conditions, if you’re really
interested see http://mathworld.wolfram.com/PrimitivePolynomial.html
or google it. One important property to
note is that their reciprocals also form primitive polynomials (that is, they
come in pairs). Example: 1 + x^{3} + x^{4} is Degree 4, its
reciprocal is 1 + x + x^{4} (10011 and 11001), and both are
primitive.

**Taps**:

Lines that run from the output of one register within the LFSR into XOR gates that determine input to another register within the LFSR. These are chosen based on the primitive polynomial.

**Type 1 **or** External LFSRs**:

One way of implementing LFSRs; all XOR gates are fed sequentially into one another and end up as the input to the least (or most, either is correct) significant bit of the LFSR. Simply put, the XORs are external from the shift register.

**Type 2 **or** Internal LFSRs**:

Another LFSR implementation; XOR gates feed into different registers within the LFSR, and are not sequential. Simply put, the XORs are inside the shift register.

Other tutorials on this subject are confusing because they only address one type of implementation, don’t explain how they got the taps, or they show the implementation of an LFSR and then in a table show the taps corresponding to a different primitive polynomial of the same degree. Keep all of this in mind if you look elsewhere.

Consider a simple
3-bit LFSR. The only primitive
polynomials for degree 3 are 1 + x^{2} + x^{3} and 1 + x + x^{3}
(they are reciprocals of each other, 1011 and 1101). Since we have two primitive polynomials, and
we have two different implementation strategies, we therefore have four unique
ways of implementing the LFSR. In fact,
each of these implementations can differ according to which register is the
most significant bit (either way will have 2^{n}-1 states, but with
different sequences).

**A** and **B** illustrate a **Type 1 / External LFSR.**

**C** and **D** illustrate a **Type 2 /
Internal LFSR**.

**A** and **C** illustrate the implementation of 1 +
x^{2} + x^{3}

**B** and **D** illustrate the implementation of 1 +
x + x^{3}

Since x^{n} and 1 are
always present in primitive polynomials, you can think of them as being used as
the output of the shift register and the input of the shift register,
respectively.

For an *n*-bit LFSR, you need to discover a
primitive polynomial associated with it to implement it. Tap tables on the internet will list taps as
such:

N = 3, Taps at 0, 1, 3 (*this
corresponds to 1 + x + x ^{3}*)

This tutorial uses the 0 and 3 as taps because they correspond to the powers of x in the primitive polynomial. Sometimes Tap tables will omit the 0 and 3, since they must be present. Other times, they may use 0 to mean the output of the least significant register (so for N = 3, their taps would be listed as "0, 2" instead of "1, 3"). They usually only list the taps associated with one primitive polynomial, but more than one exists. All of this explains why different tap tables will sometimes show you different numbers!

Here’s another pair of examples, for
n = 8 and using the primitive polynomial 1 + x^{2} + x^{3} + x^{4}
+ x^{8}:

Internal:

External:

**Warning!** The images above
show the Reset line used incorrectly. The registers
should be seeded to a non-zero value; all-zeroes is called the lock-up state and will not
change. Therefore, at least one register must be
*preset*. Your choice in seed value determines the
order of states, and ultimately the value at the 2^{n}-1 state.
Note that it is also possible to design LFSRs to have an all-ones lock-up state instead,
but this will not be discussed here for brevity.
Special thanks to all those who have pointed out this omission.

Good luck!

Images blatantly stolen from http://www.ee.ualberta.ca/~elliott/ee552/studentAppNotes/1999f/Drivers_Ed/lfsr.html and http://www.edacafe.com/books/ASIC/Book/CH14/CH14.7.php