Logic Built-In Self-Test
PRPG · MISR · STUMPS · Aliasing

Why Built-In Self-Test?

External ATPG-based testing requires an ATE (Automatic Test Equipment) machine — a multi-million-dollar instrument that connects to the chip's test pins, applies patterns at speed, and compares responses. ATE is available during production test at the fab or test house, but once a chip is deployed in the field, ATE is no longer available. If the chip needs to be tested after deployment — for safety, reliability, or diagnostics — you need another approach.

Built-In Self-Test (BIST) solves this by embedding the test circuitry inside the chip itself:

• Pattern generator on-chip — no external ATE needed to supply test vectors
• Response compactor on-chip — no external comparator needed; the chip evaluates its own pass/fail
• Test control on-chip — a simple pin or JTAG instruction triggers the self-test autonomously

The result: the chip can test itself anywhere, anytime — at power-on, periodically in the field, or on demand via a service port. This enables several critical use cases:

For Logic BIST (LBIST), the circuit under test is the combinational logic and flip-flops of the digital core — the same logic tested by scan ATPG. LBIST uses the existing scan chain infrastructure (scan flip-flops, scan-in/scan-out) and adds a pattern generator (PRPG) and response compactor (MISR).

LFSR — Linear Feedback Shift Register

The Linear Feedback Shift Register (LFSR) is the fundamental hardware building block of LBIST. An N-bit LFSR is an N-bit shift register where one or more stages are XOR-fed back to the input, creating a pseudo-random binary sequence that cycles through 2^N − 1 unique states before repeating (state 0 is excluded in a standard LFSR; an all-zero state locks the register).

LFSR Structure and Primitive Polynomials

The feedback tap positions are determined by a primitive polynomial over GF(2) — a polynomial that generates a maximal-length sequence of 2^N − 1 states. Common primitive polynomials:

The key property: for a maximal-length LFSR, every non-zero N-bit pattern appears exactly once in the sequence. This gives excellent input space coverage with minimal hardware — just N flip-flops and a handful of XOR gates.

// 8-bit maximal-length LFSR
// Primitive polynomial: x^8 + x^6 + x^5 + x^4 + 1
// Feedback taps at bits 8, 6, 5, 4 (1-indexed from MSB)
module lfsr_8bit (
  input        clk, rst_n, en,
  output reg [7:0] q
);
  wire feedback = q[7];  // MSB feeds back

  always @(posedge clk or negedge rst_n) begin
    if (!rst_n)
      q <= 8'hFF;          // seed (must be non-zero)
    else if (en) begin
      q[7] <= q[6];
      q[6] <= q[5] ^ feedback;  // tap at x^6
      q[5] <= q[4] ^ feedback;  // tap at x^5
      q[4] <= q[3] ^ feedback;  // tap at x^4
      q[3] <= q[2];
      q[2] <= q[1];
      q[1] <= q[0];
      q[0] <= feedback;
    end
  end
endmodule
// Sequence length: 2^8 - 1 = 255 unique states

PRPG — Pseudo-Random Pattern Generator

In LBIST, the LFSR is used as a Pseudo-Random Pattern Generator (PRPG). Each clock cycle, the LFSR advances to its next state — a new pseudo-random N-bit word. These bit sequences drive the scan chain inputs, effectively loading pseudo-random test patterns into the circuit under test.

The PRPG operates as follows in the LBIST flow:

1. LBIST controller initialises the LFSR with a known seed (non-zero start state)
2. For each test pattern: the LFSR shifts N times to load N bits into the scan chain (where N = scan chain length)
3. One capture cycle applies the functional clock — the circuit responds and captures data into scan FFs
4. Scan chain outputs are collected by the MISR
5. Repeat for the required number of patterns (typically 10,000–50,000)

The number of patterns needed to achieve target coverage depends on the design's fault complexity. For a typical 1–10 million gate design, 10,000–50,000 patterns achieve approximately 85–92% stuck-at coverage — acceptable for field test, though lower than what external ATPG achieves.

MISR — Multiple Input Signature Register

The Multiple Input Signature Register (MISR) is the response compactor of LBIST — also called a space compactor. After each capture cycle, the scan chain outputs (potentially thousands of bits) are XOR-compacted into the MISR's running signature. The MISR accumulates the effect of all captured responses across all patterns into a single N-bit signature word.

The MISR is structurally similar to an LFSR, but it has multiple inputs (one per scan chain output) XOR-fed into specific stages. The result is a running hash of all captured response data:

// 16-bit MISR — space compactor for LBIST
// Primitive polynomial: x^16 + x^15 + x^13 + x^4 + 1
// 4 parallel scan chain outputs feed into MISR stages
module misr_16bit (
  input         clk, rst_n, capture_en,
  input  [3:0]  scan_out,    // one bit per scan chain
  output reg [15:0] signature
);
  wire fb = signature[15];

  always @(posedge clk or negedge rst_n) begin
    if (!rst_n)
      signature <= 16'hFFFF;
    else if (capture_en) begin
      // Shift with feedback taps (x^16 + x^15 + x^13 + x^4 + 1)
      signature[15] <= signature[14] ^ fb ^ scan_out[3];  // x^15 tap
      signature[14] <= signature[13];
      signature[13] <= signature[12] ^ fb ^ scan_out[2];  // x^13 tap
      signature[12] <= signature[11];
      signature[11] <= signature[10];
      signature[10] <= signature[9];
      signature[9]  <= signature[8];
      signature[8]  <= signature[7];
      signature[7]  <= signature[6];
      signature[6]  <= signature[5];
      signature[5]  <= signature[4];
      signature[4]  <= signature[3] ^ fb ^ scan_out[1];  // x^4 tap
      signature[3]  <= signature[2];
      signature[2]  <= signature[1];
      signature[1]  <= signature[0];
      signature[0]  <= fb ^ scan_out[0];                  // x^1 tap
    end
  end
endmodule
// Gold signature pre-computed by fault-free simulation

Aliasing — The False-Pass Risk

Aliasing is the key risk in MISR-based response compaction. It occurs when a faulty circuit produces exactly the same MISR signature as the fault-free (good) circuit — the LBIST declares the faulty chip as passing. This is a test escape: a defective chip passes LBIST and ships to the customer.

Aliasing Probability Mathematics

For a well-designed N-bit MISR using a primitive polynomial, the aliasing probability per fault is:

The aliasing probability is independent of the number of test patterns — it depends only on the MISR width N. This is a fundamental property of the MISR algebraic structure. A 32-bit MISR gives aliasing probability ≈ 2.3 × 10⁻¹⁰ — meaning out of every billion faulty chips tested, at most ~0.23 chips escape undetected due to aliasing. For practical production volumes, this is negligible.

STUMPS Architecture

STUMPS (Self-Testing Using MISR and Parallel Shift register Sequences) is the industry-standard LBIST architecture, introduced by Bardell and McAnney at IBM in 1982 and still the dominant approach in modern LBIST tools (Siemens Tessent LBIST, Synopsys DFT Compiler BIST).

The STUMPS architecture has four key components:

1. LFSR / PRPG — generates pseudo-random bit sequences (the test patterns)
2. Phase Shifter — distributes and decorrelates LFSR outputs to scan chain inputs
3. Scan Chains — the existing DFT scan infrastructure (no change needed)
4. MISR / Space Compactor — compresses scan chain outputs into a running signature

Why the Phase Shifter Is Essential

The LFSR generates consecutive bits that are correlated — adjacent outputs of the LFSR shift register are just time-shifted versions of each other. If adjacent scan chain inputs receive correlated patterns, many faults that require uncorrelated stimuli on adjacent scan chains are undetectable — effectively invisible to the pseudo-random test.

The phase shifter is a network of XOR gates that mixes different LFSR stage outputs to create decorrelated patterns for each scan chain input. Each scan chain input receives an XOR combination of 2–4 LFSR stages — statistically independent of neighbouring chains. This restores the statistical independence that makes pseudo-random patterns effective for broad fault coverage.

LBIST Flow and Timing

The complete LBIST operational sequence, controlled by the on-chip LBIST controller:

1. Entry: Assert LBIST mode via test pin or JTAG BIST instruction. Normal functional operation halts. Scan enable (SE) is controlled by the LBIST controller, not external test equipment.
2. Seed load: Load the LFSR with its initial seed value (from a ROM or hardcoded constant). Load the MISR to all-ones initial state.
3. Pattern loop (repeat N_patterns times):
   • Shift phase: LFSR advances N cycles → N bits loaded into scan chain via phase shifter → scan chain is filled with one pseudo-random pattern
   • Capture phase: one functional clock cycle applied (SE=0) → circuit evaluates → scan FFs capture response
   • Compaction phase: scan chain outputs shifted into MISR (SE=1, MISR accumulates)
4. Signature compare: LBIST controller compares final MISR value against pre-computed gold signature stored in ROM. Assert PASS or FAIL output.
5. Exit: Deassert LBIST mode. Resume normal functional operation.

LBIST Test Time Estimation

LBIST vs External Scan ATPG: Comparison

Random-Pattern-Resistant Faults and Top-off Patterns

The theoretical coverage ceiling of PRPG-based LBIST is not 100%. Some faults are random-pattern-resistant (RPR) — they require very specific input combinations that are statistically unlikely to appear in a pseudo-random sequence.

What Makes a Fault RPR?

A fault is RPR when its detection requires all of the following simultaneously:

• A specific sensitisation condition on many primary inputs (e.g., all 32 inputs of a wide AND gate must be at specific values)
• A specific propagation condition through the combinational cloud
• Specific side-input values to keep other paths at non-controlling values

If the combined probability of all these conditions being met by a random pattern is less than 1/10,000, then even with 50,000 LBIST patterns, the expected number of detections is less than 5 — statistically unreliable.

Common RPR fault examples:

• Faults at the output of a wide fan-in AND/OR gate (need all other inputs non-controlling)
• Faults deep inside arithmetic units (adder carry chains) requiring specific carry propagation states
• Faults near the output of a parity tree (need specific XOR combination of many inputs)

Top-off Patterns: The Solution

Top-off patterns are a small set of deterministic ATPG patterns (typically 100–1,000 patterns) specifically generated to target the RPR faults identified after LBIST simulation. The ATPG tool runs a simulation to find which faults are not adequately covered by LBIST, then generates deterministic patterns for just those faults.

Top-off patterns are stored in a small ROM on-chip or applied via scan during LBIST using a stored pattern mode. The combined LBIST + top-off approach achieves near-ATPG coverage with much lower ATE cost:

Interview FAQ: LBIST