Also known as: LFSR, PRBS generator
A linear-feedback shift register (LFSR) is a shift register whose incoming bit is a linear (XOR) function of selected bits, called taps, producing a long, repeatable pseudo-random sequence from a small amount of state.1 With well-chosen taps an n-bit LFSR is the cheapest way to generate a maximal-length sequence, the backbone of scramblers, spread-spectrum codes, and the linear core of many stream ciphers.
How it works
An LFSR holds a few bits of state. On each clock the bits shift one position, the bit shifted out becomes the output, and a new input bit is computed by XORing the selected tap positions together. The choice of taps is described by a feedback polynomial over GF(2). When that polynomial is primitive of degree n, the register is maximal-length: it cycles through all 2ⁿ−1 non-zero states before repeating, producing an m-sequence whose statistics (balance, run-length distribution, and a sharp two-valued autocorrelation) closely mimic random noise. The all-zero state is a fixed point and must be avoided as a seed.
- Cheap — a handful of flip-flops and XOR gates; ideal for hardware and trivially reproduced in software.
- Deterministic — the same seed and taps always reproduce the same keystream, so a receiver can regenerate it exactly.
- Linear — and this is the catch below.
Variants
Two wiring conventions produce the same family of sequences: the Fibonacci form XORs several taps into a single feedback bit at the input (as drawn above), while the Galois form XORs the output bit into several stage positions as it shifts, which pipelines better in hardware because each XOR sits between two registers. To defeat the linearity weakness, stream ciphers combine LFSRs nonlinearly — with a nonlinear filter or combining function, or with clock-controlled/irregular stepping (as in the A5/1 GSM cipher). Two m-sequences of the same length can also be XORed at a chosen offset to form a Gold code, a family with low cross-correlation used for CDMA and GPS.
In practice — the linearity weakness
Because the feedback is pure XOR, the entire output is a linear function of the initial state. Observing only about 2n consecutive output bits is enough to solve for the taps and state: the Berlekamp–Massey algorithm finds the shortest LFSR that generates a given sequence in O(n²) time. This “linear complexity” is exactly why an LFSR alone is never a secure cipher — its state is recoverable — and why the algorithm is also a standard tool for reverse-engineering an unknown scrambler from a captured bit stream.
Relevance to SDR
LFSRs are everywhere in digital radio, but as scrambling rather than secrecy. Many trunked and digital-voice protocols scramble (whiten) their bit stream with a fixed LFSR sequence to remove long runs and DC bias; because the polynomial and seed are public, GopherTrunk simply regenerates the same m-sequence and XORs it back out — no key is involved. The same maximal-length sequences serve as PN spreading codes and sync/preamble patterns. That public, keyless use is the opposite of a stream cipher, whose keystream is secret and never reused.
The linearity of an LFSR also makes it a natural first hypothesis when reverse-engineering an unknown bit transform. In the clean-room talker-alias analysis (issue #773), an LFSR-style update was tested against captured data and ruled out — the observed mapping was nonlinear, pointing instead at a fixed substitution table rather than a linear feedback sequence.
Sources
-
Linear-feedback shift register — Wikipedia, for taps, feedback/primitive polynomials, maximal-length sequences, Fibonacci vs Galois forms, and the Berlekamp–Massey linearity weakness. ↩