Linear-Feedback Shift Registers

A linear-feedback shift register cycles through a long pseudo-random sequence of states using only a shift register and XOR gates.

Randomness from a Shift Register

A linear-feedback shift register (LFSR) is a shift register whose next input bit is a XOR of certain of its own bits, called the taps. Each clock it shifts, feeding back this parity. Despite its simplicity, an LFSR cycles through a long, well-mixed sequence of states that looks random, making it a cheap pseudo-random generator in hardware.

Maximal-Length Sequences

With well-chosen tap positions, an n-bit LFSR visits every nonzero state exactly once before repeating, a cycle of length 2^n minus one (the all-zeros state is a fixed point and is excluded). Such a maximal-length sequence, or m-sequence, is determined by a primitive polynomial over GF(2); the tap positions correspond to that polynomial's terms.

# 8-bit Fibonacci LFSR, taps at 8,6,5,4 (poly x^8+x^6+x^5+x^4+1)
def lfsr_step(state):
    bit = ((state >> 7) ^ (state >> 5) ^ (state >> 4) ^ (state >> 3)) & 1
    return ((state << 1) | bit) & 0xFF

Fibonacci and Galois Forms

There are two equivalent arrangements. The Fibonacci form XORs the taps together and feeds the result into one end. The Galois form instead XORs the feedback bit into several positions along the register as it shifts, which is often faster in hardware because the XORs are not chained. Both produce the same class of sequences.

Uses

LFSRs are everywhere cheap pseudo-randomness or bit mixing is needed: generating test patterns in built-in self-test, computing CRC checksums (a CRC circuit is an LFSR driven by data), scrambling data to balance signal transitions on communication links, and spreading codes in some wireless systems. They are not cryptographically secure on their own, since observing enough output reveals the taps, but as compact, fast generators of well-distributed bits they are a staple of digital design.