Linear-feedback shift register

Likewise, because the register has a finite number of possible states, it must eventually enter a repeating cycle.

However, an LFSR with a well-chosen feedback function can produce a sequence of bits that appears random and has a very long cycle.

To obtain the pseudorandom output stream, read the rightmost bit after each state transition.

The arrangement of taps for feedback in an LFSR can be expressed in finite field arithmetic as a polynomial mod 2.

The LFSR is maximal-length if and only if the corresponding feedback polynomial is primitive over the Galois field GF(2).

[3][4] This means that the following conditions are necessary (but not sufficient): Tables of primitive polynomials from which maximum-length LFSRs can be constructed are given below and in the references.

An example in C is below: If a fast parity or popcount operation is available, the feedback bit can be computed more efficiently as the dot product of the register with the characteristic polynomial: If a rotation operation is available, the new state can be computed as This LFSR configuration is also known as standard, many-to-one or external XOR gates.

[5] In the Galois configuration, when the system is clocked, bits that are not taps are shifted one position to the right unchanged.

In this case, the exclusive-or component is generalized to addition modulo-q (note that XOR is addition modulo 2), and the feedback bit (output bit) is multiplied (modulo-q) by a q-ary value, which is constant for each specific tap point.

This approach lends itself to fast execution in software because these operations typically map efficiently into modern processor instructions.

Below is a C code example for a 16-bit maximal-period Xorshift LFSR using the 7,9,13 triplet from John Metcalf:[8] Binary LFSRs of both Fibonacci and Galois configurations can be expressed as linear functions using matrices in

[9] Using the companion matrix of the characteristic polynomial of the LFSR and denoting the seed as a column vector

steps is given by Matrix for the corresponding Galois form is : For a suitable initialisation, the top coefficient of the column vector : gives the term ak of the original sequence.

[10] The number of different primitive polynomials grows exponentially with shift-register length and can be calculated exactly using Euler's totient function[11] (sequence A011260 in the OEIS).

LFSRs can be implemented in hardware, and this makes them useful in applications that require very fast generation of a pseudo-random sequence, such as direct-sequence spread spectrum radio.

The table of primitive polynomials shows how LFSRs can be arranged in Fibonacci or Galois form to give maximal periods.

This LFSR can then be fed the intercepted stretch of output stream to recover the remaining plaintext.

Complete LFSR are commonly used as pattern generators for exhaustive testing, since they cover all possible inputs for an n-input circuit.

BIST is accomplished with a multiple-input signature register (MISR or MSR), which is a type of LFSR.

This allows the BIST system to optimise storage, since set-reset flip-flops can save the initial seed to generate the whole stream of bits from the LFSR.

To prevent short repeating sequences (e.g., runs of 0s or 1s) from forming spectral lines that may complicate symbol tracking at the receiver or interfere with other transmissions, the data bit sequence is combined with the output of a linear-feedback register before modulation and transmission.

When the LFSR runs at the same bit rate as the transmitted symbol stream, this technique is referred to as scrambling.

When the LFSR runs considerably faster than the symbol stream, the LFSR-generated bit sequence is called chipping code.

The chipping code is combined with the data using exclusive or before transmitting using binary phase-shift keying or a similar modulation method.

Neither scheme should be confused with encryption or encipherment; scrambling and spreading with LFSRs do not protect the information from eavesdropping.

They are instead used to produce equivalent streams that possess convenient engineering properties to allow robust and efficient modulation and demodulation.