LFSR (Linear Feedback Shift Register)

An LFSR is a handful of flip-flops and one XOR gate, and it produces a sequence that looks random and repeats exactly. That combination is why the same circuit appears in scrambling, in CRC, in test equipment and underneath every spreading code a cellular system uses. This page follows one four stage example from the circuit to the code that generates it.

What is an LFSR ?

LFSR is a shift register circuit in which two or more outputs from intermediate steps get linearly combined and feedback to input value. That's why it is called Linear Feedback Shift Register as illustrated below.

This circuit has following properties :

If the initial states is same, you will always get the same output sequence (meaning Output sequence is deterministic)
Output sequence tend to be like random sequence (Pseudo random)
After a certain number of iteration, you will get the states values which is same as the initial states. (The maximum interval can be calculated by (2^n - 1), where n is the number of shift register.)

Due to the properties listed above, LFSR is mainly used to generate PN sequence (Pseudo Noise sequence).

Four stage LFSR with taps from x(i-3) and x(i-4) combined by XOR and fed back to the input

Figure 1. A four stage LFSR with the acronym mapped onto the circuit. The chain of D registers is the shift register, the XOR is the feedback, and combining two taps with XOR is the linear part.

Look at where the two taps come from, because that choice is the whole design. This circuit takes x(i-3) and x(i-4), combines them with XOR, and returns the result to the input. Every property of the output sequence follows from that one decision.

The word linear is doing precise work here rather than decorating the name. XOR is addition in GF(2), so the feedback is a weighted sum of register contents with every weight either 0 or 1. Nothing in the loop multiplies two register values together and nothing applies a threshold.

Linearity has two consequences, and the page is worth reading with both in mind. It makes the sequence analysable, so the period and the statistics can be worked out on paper rather than measured. It also makes the sequence predictable from a short observation, which is why a bare LFSR must never be used as a cipher.

The taps are the design : the register chain is the same whatever you build. Which outputs you feed back decides the period, the statistics and everything else about the sequence.
Linear means addition in GF(2) and nothing more : XOR is the only operation in the loop, so the whole circuit is a linear recurrence over a two element field.
Deterministic, not random : the same initial state always gives the same sequence, which is exactly what a receiver needs if it has to reproduce the transmitter output.

How does the state sequence work ?

States transition of each iterations for the circuit in this example is shown below. From this table, you may notice all the properties listed above.

State transition table for the four stage LFSR, showing the initial state returning after 15 steps

Figure 2. The contents of all four registers on every clock, with the initial state 1 1 1 1 at the top and the same state returning at step 15. The X(i) column is the XOR output, computed from the two circled values.

Read one row at a time and the rule is short. X(i) is X(i-3) XOR X(i-4). On the next clock every value shifts one column to the right, and X(i) enters at the left. The arrows drawn across the first few rows trace exactly that movement.

The table is worth checking rather than trusting, and it is correct. Every row satisfies the XOR rule, and every row's X(i) reappears as the next row's X(i-1). Row 15 repeats row 0 exactly, so the period is 15.

Fifteen is 2⁴ - 1, which is the most a four stage register can reach, and one missing state explains the minus one. Suppose all four registers hold 0. The XOR of two zeros is 0, so the next state is all zeros again. The all-zero state maps to itself, so a running LFSR visits the other 15 states and never that one.

The word maximum in the property list above deserves attention. A four stage register can reach 15 and it does not have to. Choose different taps and the 15 non-zero states break into shorter cycles instead. The same four flip-flops might then give a period of 5, or 3, or two separate loops. The tap positions decide it, and the next section says how to tell.

One rule generates the whole table : compute the XOR, shift everything right, insert the result on the left. Fifteen rows of apparent complexity come from that single step repeated.
The all-zero state is why it is 2ⁿ - 1 rather than 2ⁿ : that state maps to itself, so it sits outside the cycle and can never be reached or left.
Maximum is not automatic : a bad tap choice gives shorter cycles with the same hardware. Reaching the full period is a property of the taps, not of the register length.

How does the circuit map to a polynomial ?

In many publication, you would see this circuit is represented as a polynomial. But you may find it difficult to correlate between the real circuit and the generator polynomial. Following illustration would help you understand the meaning of the generator polynomial.

Mapping from the LFSR circuit to the generator polynomial X to the fourth plus X plus 1

Figure 3. The same circuit read as a polynomial. Each register position becomes one power of X, a position with a tap contributes a coefficient of 1, and a position without one contributes 0.

The rule fits in a sentence. Number the positions from the output end, starting at zero. Write X raised to that number for each position. Give the term a coefficient of 1 where a tap exists and 0 where it does not. The grey bar in the picture does exactly that, reading 1X⁴, 0X³, 0X², 1X¹ and 1X⁰ from left to right.

Two notations sit at the top of the picture and both describe the same polynomial. The coefficient form [1 0 0 1 1] lists every coefficient, zeros included. The exponent form [4 1 0] lists only the powers that are actually present. The Matlab example at the end of this page uses the coefficient form, which is why the vector there has five entries for a four stage register.

The polynomial also answers the question the previous section left open. A degree n polynomial delivers the full period of 2ⁿ - 1 only when it is primitive over GF(2). X⁴ + X + 1 is primitive, which is why the table runs to 15 rows. A non-primitive polynomial of the same degree still produces a working circuit, and its states divide into shorter cycles instead.

The recurrence can be read straight off the polynomial too. Setting X⁴ + X + 1 to zero gives X⁴ = X + 1, and multiplying through by X^n-4 gives x(n) = x(n-3) XOR x(n-4). That is the tap arrangement drawn in Figure 1, recovered from the algebra rather than from the picture.

Position number becomes the power of X : count from the output end starting at zero, and a tap at that position sets the coefficient to 1.
[1 0 0 1 1] and [4 1 0] are the same polynomial : one lists all coefficients and the other lists only the non-zero powers. Tools differ in which they expect, so check before pasting a vector.
Primitive is the property that buys the full period : degree alone is not enough, and a published table of primitive polynomials is how a designer picks taps in practice.

Fibonacci and Galois arrangements

Every circuit on this page so far has been drawn the same way, with the taps gathered into one XOR that feeds the input. That is one of two standard arrangements, and hardware designers usually choose the other one.

The form used above is called Fibonacci. Taps are taken from several register outputs, XORed together, and the single result is returned to the input of the first register. Everything in the feedback path sits outside the register chain.

The alternative is called Galois, and it turns the dataflow around. One value leaves the last register and is fed back into the chain at several points, with an XOR sitting between two registers rather than outside them all. The drawing below puts the two side by side.

Figure 4. The same polynomial wired two ways. The Fibonacci form collects taps into one XOR outside the chain. The Galois form pushes the XOR inside the chain, which is what keeps its gate delay constant.

The difference matters in hardware rather than in mathematics. A Fibonacci register with many taps needs a wide XOR, and the gate delay through it grows as taps are added, which caps the clock rate. A Galois register never has more than one XOR between two registers, whatever the polynomial, so adding taps costs it nothing in speed.

Both arrangements realise the same characteristic polynomial, and both reach a period of 2ⁿ - 1 when that polynomial is primitive. They produce the same family of sequences. The exact bit ordering differs between them by convention, so swapping one form for the other means checking the ordering rather than assuming it.

Same polynomial, two topologies : Fibonacci puts the XOR outside the chain and Galois puts it inside, and the mathematics does not notice the difference.
Galois keeps its clock rate as taps are added : one XOR delay between registers whatever the polynomial, which is why fast hardware usually uses it.
The sequences match, the bit order may not : swapping forms is a wiring change and an ordering check, not a drop-in replacement.

Where are LFSRs used ?

The page says above that an LFSR is mainly used to generate a PN sequence, and that is true and incomplete. The same circuit does several different jobs across a system, and there is one job it must never be given on its own.

Scrambling is the most visible use. A transmitter XORs the data with the PN sequence and the receiver XORs with the same sequence, which cancels it. Both ends run identical registers from an agreed initial state, and that agreement is what a specification has to pin down. LTE and NR build their scrambling sequence from two 31 stage registers combined into a Gold code.

CRC is the same circuit doing arithmetic. A CRC generator is an LFSR with the message fed in alongside the feedback, and the remainder is whatever is left in the registers when the message ends. The Error Detection/Correction page works that division through by hand, and the shift register is how it is done in silicon.

Chip test is a third use and the least known outside that field. An LFSR on the chip generates pseudo-random test vectors, the logic under test responds, and a second LFSR compresses the whole run of responses into a short signature. A single wrong bit anywhere changes the signature, so a long test reduces to comparing a few bytes.

Now the job an LFSR must never be given alone. Linearity makes the sequence predictable. Observe 2n consecutive output bits from an n stage register, and the Berlekamp-Massey algorithm recovers both the taps and the state. A 64 stage register is broken by 128 observed bits, which is a trivial amount of data. A bare LFSR is a sequence generator and not a cipher, and stream ciphers built on LFSRs add a nonlinear stage for exactly this reason.

Scrambling works because both ends can reproduce the sequence : determinism is the feature here, not a limitation. A truly random sequence would be useless, because the receiver could not regenerate it.
A CRC generator is an LFSR : the polynomial division on the Error Detection/Correction page and the shift register here are the same operation seen from two directions.
2n output bits reveal everything : Berlekamp-Massey recovers the taps and the state from twice the register length, so linearity that helps the analyst also helps the attacker.
Never use a bare LFSR as a cipher : it needs a nonlinear stage on top, and a design that leaves one out is broken rather than weak.

< LFSR with Matlab Communication Toolbox >

The code below builds the same four stage register the rest of this page uses, so every number in it can be checked against the figures above. Read the parameters rather than copying them, because each one names something this page has already defined.

You can implement LFSR with Matlab Communication Toolbox as shown below. This example is for the circuit described above.

g = [1 0 0 1 1];

init = [1 1 1 1];

curr = [1 1 1 1];

mask = [0 0 0 1];

NoOfOutBits = 15;

h = commsrc.pn('GenPoly', g, ...

'InitialStates', init, ...

'CurrentStates', curr, ...

'Mask', mask, ...

'NumBitsOut', NoOfOutBits)

If you genearte the output sequence using following function,

h.generate()'

you will get the following output.

1 1 1 1 0 0 0 1 0 0 1 1 0 1 0

Compare this result with x(i-4) column in the table shown above.

Every parameter in that call names something already on this page. GenPoly takes g = [1 0 0 1 1], which is the coefficient form from Figure 3. InitialStates and CurrentStates are both [1 1 1 1], which is the initial state at the top of Figure 2. Mask picks which register the output is taken from, and [0 0 0 1] selects the last one. NumBitsOut asks for 15 bits, which is exactly one full period.

The comparison the page asks for is correct. The printed sequence begins 1 1 1 1 0 0 0 1 0 0. Those are the first ten entries of the X(i-4) column in Figure 2, read down from state 0. Run the generator, then step through the table by hand. Both give the same answer.

One practical note before you paste this into a recent Matlab. The commsrc.pn object is the older interface. Newer versions of the toolbox provide comm.PNSequence for the same purpose, so the call may need adapting.

Every argument maps to something in the figures : the polynomial, the initial state and the output length all appear earlier on this page. The code restates them rather than adding anything.
Ask for exactly one period : 15 bits from a four stage register covers the full cycle, and anything longer simply repeats.
The output is one column of the state table : Mask selects which register to observe, so changing it shifts the sequence rather than producing a different one.