Linear Feedback
Shift Register

A Linear Feedback Shift Register is a chain of D flip-flops where the input to the first stage is a XOR (linear) combination of selected output stages called taps. On every clock edge the register shifts right by one bit and the feedback creates the new bit.

With the right tap polynomial, an n-bit LFSR cycles through all 2ⁿ−1 non-zero states before repeating — producing a maximal-length (m-sequence). That near-random but fully deterministic bit stream powers everything from BIST pattern generation to CRC error detection to spread-spectrum modulation.

Two equivalent but structurally different architectures exist: Fibonacci (one XOR tree feeds bit 0, all taps read from register outputs) and Galois (XOR gates distributed inside the chain for higher speed). Both produce the same m-sequence length from the same polynomial.

The tap connections define a characteristic polynomial over GF(2). For an n-bit LFSR with taps at positions k₁, k₂, …:

A maximal-length sequence requires P(x) to be a primitive polynomial over GF(2) — one that cannot be factored and has order 2ⁿ−1.

Properties of an m-sequence (period L = 2ⁿ−1):

• Exactly 2ⁿ⁻¹ ones and 2ⁿ⁻¹−1 zeros per period (balance property)
• Run lengths follow a prescribed distribution (run property)
• Auto-correlation is −1/L for all non-zero shifts (shift-and-add property)
• XOR of the sequence with any shifted copy = another shift of the same sequence

For polynomial x⁴ + x + 1 (n=4, taps at positions 4 and 1):

In the Galois version the same polynomial inserts XOR gates after Q4 (bit 1) in the shift chain. The output bit fans to all tap points simultaneously — critical path is a single FF + XOR regardless of polynomial degree.

Primitive polynomials are pre-computed — you pick your register width and look up the tap table. Only the non-trivial taps are listed (xⁿ and x⁰=1 are always present).

Built-In Self-Test (BIST). A MISR (Multiple-Input Signature Register) is an LFSR that compresses test responses into a compact signature. Logic BIST drives the CUT with LFSR pseudo-random patterns, compresses outputs in a MISR, and compares the final signature against a golden value stored in ROM. No external ATE needed.

CRC Generation & Checking. Cyclic Redundancy Check is implemented with a Galois LFSR whose polynomial matches the CRC standard (e.g., CRC-32 = x³²+x²⁶+x²³+…+1 for Ethernet). The register processes one bit per clock; its final state is the CRC remainder. Receivers re-compute CRC and compare — a mismatch signals an error.

Spread Spectrum / CDMA. Direct-sequence spread spectrum XORs data with a chipping code from an LFSR. The wide bandwidth reduces interference and enables multiple users to share a channel (CDMA). GPS C/A code uses a 10-bit LFSR combination (Gold code).

SERDES Scrambler. High-speed serial links (PCIe, SATA, USB 3) scramble the data stream with an LFSR to avoid long runs of 0s or 1s that confuse CDR PLLs. The receiver uses the same polynomial to de-scramble.

Stream Cipher (A5/1). GSM voice encryption used three LFSRs (lengths 19, 22, 23) clocked irregularly and XORed together to produce a keystream. Broken due to short key and biased clocking, but historically important.

CRC treats the input data as a polynomial M(x) and computes M(x) · xⁿ mod G(x) where G(x) is the generator polynomial and n is the CRC width. In hardware this division is done serially by a Galois LFSR:

For each bit of the message, the LFSR output bit is XORed with the incoming bit. If the result is 1 the intermediate taps flip — this implements polynomial long division in one gate delay per tap. After all message bits are processed, the register holds the CRC remainder which is appended to the frame.

The receiver recomputes CRC over the received frame including the appended CRC bytes. A correct frame produces a known fixed remainder (syndrome = 0 for self-checking polynomials).

A synthesisable 8-bit Fibonacci LFSR with polynomial x⁸+x⁶+x⁵+x+1, taps at positions 8,6,5,1:

// 8-bit Fibonacci LFSR  (taps: 8,6,5,1  →  x⁸+x⁶+x⁵+x+1)
module lfsr_8bit (
  input  wire       clk,
  input  wire       rst_n,
  input  wire       en,
  output reg  [7:0] state,
  output wire       prbs_out
);

  wire feedback = state[7] ^ state[5] ^ state[4] ^ state[0];
  // Bit positions 7,5,4,0 are indices 0-based for taps 8,6,5,1

  always @(posedge clk or negedge rst_n) begin
    if (!rst_n)
      state <= 8'hFF;          // non-zero seed
    else if (en)
      state <= {state[6:0], feedback};
  end

  assign prbs_out = state[7];   // serial output bit

endmodule

Galois topology of the same polynomial — XOR gates inline, single-cycle critical path:

// 8-bit Galois LFSR  (same polynomial, faster critical path)
module lfsr_galois_8bit (
  input  wire       clk,
  input  wire       rst_n,
  output reg  [7:0] state
);

  wire [7:0] next;
  wire       out_bit = state[0];

  assign next[7] =           out_bit;   // MSB ← feedback
  assign next[6] = state[7]           ;
  assign next[5] = state[6] ^ out_bit; // tap 6
  assign next[4] = state[5] ^ out_bit; // tap 5
  assign next[3] = state[4]           ;
  assign next[2] = state[3]           ;
  assign next[1] = state[2]           ;
  assign next[0] = state[1] ^ out_bit; // tap 1

  always @(posedge clk or negedge rst_n) begin
    if (!rst_n) state <= 8'hFF;
    else        state <= next;
  end

endmodule

MISR (signature register for BIST) — same as Galois LFSR but each stage XORs in an external response bit:

// 8-bit MISR — Multiple Input Signature Register
module misr_8bit (
  input  wire       clk, rst_n,
  input  wire [7:0] response,   // CUT output bus
  output reg  [7:0] signature
);
  wire [7:0] next;
  wire       fb = signature[0];

  assign next[7] = fb ^ response[7];
  assign next[6] = signature[7] ^ response[6];
  assign next[5] = signature[6] ^ fb ^ response[5];
  assign next[4] = signature[5] ^ fb ^ response[4];
  assign next[3] = signature[4] ^ response[3];
  assign next[2] = signature[3] ^ response[2];
  assign next[1] = signature[2] ^ response[1];
  assign next[0] = signature[1] ^ fb ^ response[0];

  always @(posedge clk or negedge rst_n) begin
    if (!rst_n) signature <= 8'hFF;
    else        signature <= next;
  end
endmodule