A linear feedback shift register (LFSR) is a shift register whose input bit is a linear function of its previous state.

The only linear functions of single bits are xor and inverse-xor; thus it is a shift register whose input bit is driven by the exclusive-or (xor) of some bits of the overall shift register value.

The initial value of the LFSR is called the seed, and because the operation of the register is deterministic, the sequence of values produced by the register is completely determined by its current (or previous) state. Likewise, because the register has a finite number of possible states, it must eventually enter a repeating cycle. However, a LFSR with a well-chosen feedback function can produce a sequence of bits which appears random and which has a very long cycle.

Applications of LFSRs include generating pseudo-random numbers, pseudo-noise sequences, fast digital counters, and whitening sequences. Both hardware and software implementations of LFSRs are common.

How it works

The list of the bits positions that affect the next state is called the tap sequence. In the diagram below, the sequence is ^*.

• The outputs that influence the input are called taps (blue in the diagram below).
• A maximal LFSR produces an n-sequence (i.e. cycles through all possible states within the shift register except all zero bits), unless it contains all zeros, in which case it will never change.

The sequence of numbers generated by a LFSR can be considered a binary numeral system just as valid as Gray code or the natural binary code.

The tap sequence of an LFSR can be represented as a polynomial mod 2. This means that the coefficients of the polynomial must be 1's or 0's. This is called the feedback polynomial or characteristic polynomial. For example, if the taps are at the 16th, 14th, 13th and 11th bits (as below), the resulting LFSR polynomial is

The 'one' in the polynomial does not correspond to a tap. The powers of the terms represent the tapped bits, counting from the left.

• If (and only if) this polynomial is a primitive, then the LFSR is maximal
• The LFSR will only be maximal if the number of taps is even
• The tap values in a maximal LFSR will be relatively prime
• There can be more than one maximal tap sequence for a given LFSR length
• Once one maximal tap sequence has been found, another automatically follows. If the tap sequence, in an n-bit LFSR, is then the corresponding 'mirror' sequence is ^*" target="_blank" >has as its counterpart [32,29,30,31. Both give a maximal sequence.

The animation below is erroneous. In one stage of the cycle the values of the taps do not correspond to the values stored in bit positions 14 and 16. The values of the taps rather than the values in the bit positions are then used to calculate the code, thus propagating the error into the feedback. This occurs when the last 3 bits are 100.