Linear feedback shift register

From Wikipedia, the free encyclopedia
  (Redirected from Linear feedback shift registers)
Jump to: navigation, search
"LFSR" redirects here. For the airport using that ICAO code, see Reims – Champagne Air Base.
A 4-bit Fibonacci LFSR with its state diagram. The XOR gate provides feedback to the register that shifts bits from left to right. The maximal sequence consists of every possible state except the "0000" state.


The most commonly used linear function of single bits is exclusive-or (XOR). Thus, an LFSR is most often a shift register whose input bit is driven by the XOR of some bits of the overall shift register value.



The mathematics of a cyclic redundancy check, used to provide a quick check against transmission errors, are closely related to those of an LFSR.

Fibonacci LFSRs[edit]

A 16-bit Fibonacci LFSR. The feedback tap numbers in white correspond to a primitive polynomial in the table so the register cycles through the maximum number of 65535 states excluding the all-zeroes state. The state shown, 0xACE1 (hexadecimal) will be followed by 0x5670.


  • As an alternative to the XOR based feedback in an LFSR, one can also use XNOR.[1] This function is an affine map, not strictly a linear map, but it results in an equivalent polynomial counter whose state of this counter is the complement of the state of an LFSR. A state with all ones is illegal when using an XNOR feedback, in the same way as a state with all zeroes is illegal when using XOR. This state is considered illegal because the counter would remain "locked-up" in this state.


The arrangement of taps for feedback in an LFSR can be expressed in finite field arithmetic 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 reciprocal characteristic polynomial. For example, if the taps are at the 16th, 14th, 13th and 11th bits (as shown), the feedback polynomial is


The 'one' in the polynomial does not correspond to a tap – it corresponds to the input to the first bit (i.e. x0, which is equivalent to 1). The powers of the terms represent the tapped bits, counting from the left. The first and last bits are always connected as an input and output tap respectively.

The LFSR is maximal-length if and only if the corresponding feedback polynomial is primitive. This means that the following conditions are necessary (but not sufficient):

  • The number of taps should be even.
  • The set of taps – taken all together, not pairwise (i.e. as pairs of elements) – must be relatively prime. In other words, there must be no divisor other than 1 common to all taps.



Some example C code is below:

# include <stdint.h>
int main(void)
    uint16_t start_state = 0xACE1u;  /* Any nonzero start start will work. */
    uint16_t lfsr = start_state;
    unsigned bit;
    unsigned period = 0;
        /* taps: 16 14 13 11; feedback polynomial: x^16 + x^14 + x^13 + x^11 + 1 */
    } while (lfsr != start_state);
    return 0;

This LFSR configuration is also known as standard, many-to-one or external XOR gates. The alternative Galois configuration is described in the next section.

Galois LFSRs[edit]


A 16-bit Galois LFSR. The register numbers in white correspond to the same primitive polynomial as the Fibonacci example but are counted in reverse to the shifting direction. This register also cycles through the maximal number of 65535 states excluding the all-zeroes state. The state ACE1 hex shown will be followed by E270 hex.

To generate the same output stream, the order of the taps is the counterpart (see above) of the order for the conventional LFSR, otherwise the stream will be in reverse. Note that the internal state of the LFSR is not necessarily the same. The Galois register shown has the same output stream as the Fibonacci register in the first section. A time offset exists between the streams, so a different startpoint will be needed to get the same output each cycle.


Below is a C code example for the 16 bit maximal period Galois LFSR example in the figure:

# include <stdint.h>
int main(void)
    uint16_t lfsr = start_state;
    unsigned period = 0;
        lfsr >>= 1;               /* Shift register */
                                   * to taps, 0 elsewhere. */
    } while (lfsr != start_state);
    return 0;

Non-binary Galois LFSR[edit]


Some polynomials for maximal LFSRs[edit]

The following table lists maximal-length polynomials for shift-register lengths up to 19. Note that more than one maximal-length polynomial may exist for any given shift-register length. A list of alternative maximal-length polynomials for shift-register lengths 4-32 (beyond which it becomes unfeasible to store or transfer them) can be found here:

Bits Feedback polynomial Period
n 2^n - 1
2 x^2 + x + 1 3
3 x^3 + x^2 + 1 7
4 x^4 + x^3 + 1 15
5 x^{ 5 }+x^{ 3 }+1 31
6 x^{ 6 }+x^{ 5 }+1 63
7 x^{ 7 }+x^{ 6 }+1 127
9 x^{ 9 }+x^{ 5 }+1 511
10 x^{ 10 }+x^{ 7 }+1 1023
11 x^{ 11 }+x^{ 9 }+1 2047
15 x^{ 15 }+x^{ 14 }+1 32767
17 x^{ 17 }+x^{ 14 }+1 131071
18 x^{ 18 }+x^{ 11 }+1 262143
20-168 [1]
2-786,1024,2048,4096 [2]

Output-stream properties[edit]

  • Ones and zeroes occur in 'runs'. The output stream 0110100, for example consists of five runs of lengths 1,2,1,1,2, in order. In one period of a maximal LFSR, 2n −1 runs occur (for example, a six bit LFSR will have 32 runs). Exactly half of these runs will be one bit long, a quarter will be two bits long, up to a single run of zeroes n − 1 bits long, and a single run of ones n bits long. This distribution almost equals the statistical expectation value for a truly random sequence. However, the probability of finding exactly this distribution in a sample of a truly random sequence is rather low[vague].
  • LFSR output streams are deterministic. If you know the present state as well as the positions of the XOR gates in the LFSR, you can predict the next state.[3] This is not possible with truly random events. With minimal-length LFSRs, it is much easier to compute the next state, as there are only an easily limited number of them for each length.[clarification needed]



Uses as counters[edit]


Uses in cryptography[edit]




The linear feedback shift register has a strong relationship to linear congruential generators.[7]

Uses in circuit testing[edit]

LFSRs are used in circuit testing, for test-pattern generation (for exhaustive testing, pseudo-random testing or pseudo-exhaustive testing) and for signature analysis.

Test-pattern generation[edit]

Complete LFSR are commonly used as pattern generators for exhaustive testing, since they cover all possible inputs for an n input circuit. Maximum length LFSRs and weighted LFSRs are widely used as pseudo-random test pattern generators for pseudo-random test applications.

Signature analysis[edit]

In built-in self-test (BIST) techniques, storing all the circuit outputs on chip is not possible, but the circuit output can be compressed to form a signature which later will be compared to the golden signature (of the good circuit) to detect faults. Since this compression is lossy, there is always a probability that a faulty output also generates the same signature as the golden signature and the faults can not be detected. This condition is called error masking or aliasing. This is accomplished by using a multiple-input signature register (MISR or MSR) which is a type of LFSR. A standard LFSR has a single XOR or XNOR gate where the input of the gate is connected to several "taps" and the output is connected to the input of the first flip-flop. A MISR has the same structure, however, the input to every flip-flop is fed through an XOR/XNOR gate. For example, a four bit MISR has a four-bit parallel output and a four-bit parallel input. The input of the first flip-flop is XOR/XNORd with parallel input bit zero and the "taps." Every other flip-flop input is XOR/XNORd with the preceding flip-flop output and the corresponding parallel input bit. Consequently, the next state of the MISR is dependent on the last several states opposed to just the current state. Therefore, a MISR will always generate the same golden signature given that input sequence is the same every time.

Uses in digital broadcasting and communications[edit]


Main article: scrambler



Digital broadcasting systems that use linear feedback registers:

Other digital communications systems using LFSRs:

Other uses[edit]

The German time signal DCF77, in addition to amplitude keying, employs phase-shift keying driven by a 9-stage LFSR to increase the accuracy of received time and the robustness of the data stream in the presence of noise.[9]


LFSRs are also used in Communications System Jamming systems in which they are used to generate pseudo random noise to raise the noise floor of a target communication system.

See also[edit]


  1. ^ Linear Feedback Shift Registers in Virtex Devices
  2. ^ Beker, Henry; Piper, Fred (1982). Cipher Systems: The Protection of Communications. Wiley-Interscience. p. 212. 
  3. ^
  4. ^
  5. ^ Barkam, Elad; Biham, Eli; Keller, Nathan (2008), "Instant Ciphertext-Only Cryptanalysis of GSM Encrypted Communication", Journal of Cryptology 21 (3): 392–429 
  6. ^ Lu, Yi; Willi Meier; Serge Vaudenay (2005). "The Conditional Correlation Attack: A Practical Attack on Bluetooth Encryption". Crypto 2005 (Santa Barbara, California, USA) 3621: 97–117. doi:10.1007/11535218_7. 
  7. ^ RFC 4086 section 6.1.3 "Traditional Pseudo-random Sequences"
  8. ^ Section 9.5 of the SATA Specification, revision 2.6
  9. ^ Hetzel, P. (16 March 1988). "Time dissemination via the LF transmitter DCF77 using a pseudo-random phase-shift keying of the carrier". 2nd European Frequency and Time Forum. Neuchâtel. pp. 351–364. Retrieved 11 October 2011. 

External links[edit]