LFSR

An LFSR, or linear-feedback shift register, is a shift register whose input bit is a linear function of its previous state, typically the XOR of a subset of its bits. Over the binary field GF(2), the state update consists of shifting the register and inserting at one end the XOR of tapped bits. LFSRs produce sequences that appear random and are widely used for deterministic pseudo-random number generation, cryptography, and error-detecting codes such as CRC.

Two common realizations are the Fibonacci (or standard) LFSR and the Galois (or modular) LFSR. In a Fibonacci LFSR, the new input bit is the XOR of bits in the tapped positions, and all bits shift by one position. In a Galois LFSR, the state bits are shifted and the feedback bit is XORed into selected stages along the way, often reducing gate count in hardware.

Each LFSR can be associated with a characteristic polynomial over GF(2), whose taps correspond to nonzero coefficients. When the polynomial is primitive, the register has maximal period of 2^n − 1 with a nonzero initial state. If the initial state is all zeros, the sequence stays zero. The choice of taps thus determines both period and statistical properties.

Common uses include generating streams of pseudo-random bits for simulations or cryptographic stream ciphers, whitening, and producing CRC checksums. While LFSRs are efficient, their linearity makes them vulnerable to state reconstruction from outputs unless combined with nonlinear filters or irregular clocking; care is needed for cryptographic use.