LFSRs

An LFSR, or linear feedback shift register, is a shift register whose input bit is a linear function of its previous state, typically an XOR of selected bits. The register has n stages, each storing one bit. At each step the register shifts, and the new input bit is computed from a subset of the current bits, known as taps. The sequence of states and the output bit are determined by the length n and the chosen taps, which correspond to a feedback polynomial over the finite field GF(2).

Two common hardware realizations are the Fibonacci form and the Galois form. In the Fibonacci configuration, the new input bit is the XOR of the tapped bits, and the register shifts accordingly. In the Galois form, the taps influence multiple stages during the shift, producing the same linear recurrence but with a different circuit structure. Both forms implement the same mathematical process but differ in hardware layout.

For a nonzero initial state and a primitive (i.e., maximal-length) feedback polynomial, an LFSR can generate a sequence of length 2^n − 1 before repeating. More generally, the period divides 2^n − 1. The generated bit sequence is biased toward certain properties but is deterministic and reproducible, making LFSRs useful as pseudo-random generators and in applications such as scramblers, CRC calculations, error detection, and various digital communication tasks.

Because LFSR sequences are linear, they can be predicted if the internal state becomes known. Cryptographic use typically requires combining multiple LFSRs with nonlinear operations or irregular clocking to increase security.