How Shift Registers Generate Pseudorandom Noise

This article explains how shift-register generators, specifically Linear Feedback Shift Registers (LFSRs), use feedback taps and binary arithmetic to produce deterministic, pseudorandom noise (PRN) sequences. It breaks down the mechanical operation of bit shifting, the role of modulo-2 addition at selected tap positions, the importance of primitive polynomials in achieving maximal sequence length, and the statistical properties that allow these simple hardware structures to emulate true random noise.

The Basic Architecture of a Shift Register

A shift register consists of a cascade of binary storage elements, known as flip-flops or stages, where each stage holds a single binary digit (\(0\) or \(1\)). An \(n\)-stage register can represent \(2^n\) unique binary states. At every clock pulse, the binary value in each stage shifts to the adjacent stage to the right, and the value in the final stage is output.

Without feedback, a shift register empties after \(n\) clock cycles. To generate a continuous stream of data, the system feeds a newly computed bit back into the first stage of the register at every clock tick.

The Role of Feedback Taps and Modulo-2 Arithmetic

Feedback taps are designated connection points drawn from specific stages of the shift register. The binary values present at these tapped stages are combined using linear operations—specifically exclusive-OR (\(\text{XOR}\)) logic, which is the equivalent of modulo-2 addition in the binary number system.

The feedback operation follows strict binary rules: * \(0 \oplus 0 = 0\) * \(0 \oplus 1 = 1\) * \(1 \oplus 0 = 1\) * \(1 \oplus 1 = 0\)

On each clock transition: 1. The bits at the tapped positions are sampled. 2. The \(\text{XOR}\) sum of these tapped bits is calculated. 3. The contents of all stages shift one position to the right. 4. The calculated \(\text{XOR}\) result is shifted into the leftmost (first) stage. 5. The bit emerging from the rightmost stage becomes the next bit in the output pseudorandom sequence.

Maximal Length Sequences and Primitive Polynomials

Because an \(n\)-bit register has a finite number of states, the sequence of output bits must eventually repeat. The all-zero state is a trap state in standard \(\text{XOR}\) configurations because \(0 \oplus 0 = 0\), which prevents the register from ever leaving the zero state. Consequently, the maximum possible non-repeating cycle length for an \(n\)-stage LFSR is \(2^n - 1\).

Sequences that achieve this maximum period are called maximal-length sequences or m-sequences. An LFSR achieves an m-sequence only when the tap positions correspond to the coefficients of a primitive polynomial over the Galois field \(\text{GF}(2)\). For example, a 4-stage register with taps at stages 4 and 3 corresponds to the primitive polynomial \(x^4 + x^3 + 1\), producing a repeating pattern of \(2^4 - 1 = 15\) bits before cycling.

Pseudorandom Characteristics of the Output

Although generated deterministically, m-sequences exhibit statistical properties resembling white noise, fulfilling Golomb’s randomness postulates:

  1. Balance Property: In every full period, the number of ones exceeds the number of zeros by exactly one (containing \(2^{n-1}\) ones and \(2^{n-1} - 1\) zeros).
  2. Run Property: A “run” is a consecutive sequence of identical bits. Half the runs have length 1, one-quarter have length 2, one-eighth have length 3, and so forth, matching the distribution of true coin tosses.
  3. Autocorrelation Property: The sequence has an impulse-like periodic autocorrelation function. When correlated with a phase-shifted version of itself, the correlation is high only at zero shift and uniformly low at all other shifts.

These noise-like qualities, combined with minimal hardware overhead, make shift-register-generated pseudorandom noise fundamental to spread-spectrum communications, GPS signal modulation, cryptography, and built-in self-test (BIST) circuits.