How LFSRs Generate Pseudo-Random Binary Sequences

Linear Feedback Shift Registers (LFSRs) are foundational mechanisms in digital computing used to produce deterministic, statistically random binary sequences known as Pseudo-Random Binary Sequences (PRBS). This article examines the core architecture of LFSRs, the role of binary arithmetic and feedback polynomials in their operation, how they achieve maximal-length sequences with near-ideal randomness properties, and their widespread applications across cryptography, telecommunications, and digital circuit testing.

What is a Linear Feedback Shift Register?

An LFSR is a shift register whose input bit is driven by a linear function of its previous states. In digital electronics, a shift register consists of a cascade of flip-flops, each holding a single binary digit (\(0\) or \(1\)). With every clock cycle, the bits shift sequentially down the register by one position. The vacated position at the input is populated by a new bit computed via the feedback function.

Because the only linear operations over single bits in binary logic are XOR (exclusive OR) and XNOR (exclusive NOR), the feedback bit is calculated by XORing specific register stages known as “taps.”

Operation in the Binary System

The binary operation of an LFSR is governed by finite field arithmetic over Galois Field 2, or \(GF(2)\). In \(GF(2)\), addition corresponds to the bitwise XOR operation, and multiplication corresponds to bitwise AND.

1. State Initialization (Seed): The register is initialized with a non-zero binary vector known as the seed. An all-zero state must be avoided in XOR-based LFSRs because XORing zeros continuously produces zero, trapping the register in a permanent deadlock.
2. Shifting: Upon a clock pulse, the bit at stage \(n\) is output, the bit at stage \(n-1\) moves to stage \(n\), and this pattern continues across all stages.
3. Feedback Calculation: Predefined tap positions are XORed together to generate a single binary value, which feeds into the first register stage.

Mathematically, the configuration of taps is represented by a characteristic feedback polynomial:

\[P(x) = c_n x^n + c_{n-1} x^{n-1} + \dots + c_1 x + 1\]

where each coefficient \(c_i \in \{0, 1\}\) dictates whether the output of the \(i\)-th register stage contributes to the feedback calculation.

Producing Maximal-Length Sequences (m-sequences)

An \(n\)-bit register can represent a maximum of \(2^n\) unique states. Excluding the all-zero state, the longest possible sequence an LFSR can cycle through before repeating is \(2^n - 1\) states. A sequence achieving this maximum cycle is called a maximal-length sequence or m-sequence.

To generate an m-sequence, the feedback polynomial must be a primitive polynomial modulo 2. Primitive polynomials guarantee that the register traverses every possible non-zero binary combination before repeating, maximizing the period of the pseudo-random output.

Pseudo-Random Properties of LFSR Output

Although the sequence generated by an LFSR is completely deterministic, m-sequences exhibit statistical properties that closely mirror true random noise. These properties, formalized by Solomon Golomb, include:

• Balance Property: Over a full period of \(2^n - 1\), the number of binary ones exceeds the number of binary zeros by exactly one (there are \(2^{n-1}\) ones and \(2^{n-1} - 1\) zeros).
• Run Property: A “run” is a consecutive sequence of identical bits. Across a full period, half of all runs are of length 1, a quarter are of length 2, an eighth are of length 3, and so on, matching the expected probability distribution of independent coin flips.
• Ideal Autocorrelation: The discrete autocorrelation function of an m-sequence has a high peak at zero shift and a constant, minimal value for all non-zero shifts, meaning the sequence shows virtually no correlation with time-shifted versions of itself.

Key Applications

• Telecommunications and Spread Spectrum: LFSRs generate spreading codes in Code Division Multiple Access (CDMA), GPS signaling, and Wi-Fi standards. Gold codes and Kasami codes, constructed by combining the outputs of multiple LFSRs, minimize interference between simultaneous transmissions.
• Built-In Self-Test (BIST): In semiconductor manufacturing, LFSRs act as pseudo-random pattern generators to feed millions of test inputs into complex logic circuits, allowing rapid detection of manufacturing defects without external automated test equipment.
• Scramblers and Whitening Filters: In protocols like Ethernet, PCIe, and SATA, LFSRs scramble data to eliminate long runs of identical bits, preventing DC bias on transmission lines and aiding clock recovery.
• Stream Ciphers: LFSRs provide fast keystream generation in lightweight cryptographic algorithms (such as A5/1 used in GSM). However, because an LFSR’s linear structure can be fully deduced from a short segment of output using the Berlekamp-Massey algorithm, cryptographic designs combine multiple LFSRs with non-linear filter functions to ensure security.