Scan Chains and Automatic Test Pattern Generation

A manufactured die cannot be probed at its internal nodes. Its state lives in thousands of flip-flops, most of them buried behind several levels of logic, and the only external access is through the pins. Testing it means the design must be given a mode in which its internal state is observable and controllable from outside, and the standard mechanism for that is the scan chain.

A flip-flop with two jobs

An ordinary D flip-flop takes its next state from combinational logic. A scan flip-flop inserts a multiplexer in front of the D input, selected by a global scan-enable signal. When scan-enable is low, the cell behaves as before and the design functions normally. When it is high, the flop’s next state comes from the previous flop in a chain instead of from the logic, and the chain becomes a shift register.

The cost is one multiplexer per flop: area, a small delay on the functional path (a multiplexer in series with the input adds on the order of tens of picoseconds, which must be subtracted from the timing budget), and a routing overhead for the scan wires. The benefit is that an inaccessible internal node becomes reachable: shifting a pattern into the chain sets the state of every flop, and shifting it out after a clock pulse reads what every flop captured.

A full scan design connects all flops into one or a few chains. The number of chains is a trade between test time and routing. With a single chain of N flops, loading one pattern costs N clock cycles shifted at a slow scan frequency, and the same to unload. With C chains, each of length about N/C, the shift costs N/C cycles, so more chains buy test time almost linearly. The limit is pin count and the die area consumed by the scan routing, and in a multi-die package or a wafer-probe environment the pin count is the binding constraint.

// A scan cell: functional path when scan_enable is low, chain path when high.
module scan_dff (
    input  logic clk,
    input  logic scan_enable,
    input  logic d,          // from combinational logic
    input  logic si,         // from the previous cell in the chain
    output logic q,
    output logic so          // to the next cell; same net as q in most libraries
);
    logic muxed;
    always_comb muxed = scan_enable ? si : d;

    always_ff @(posedge clk)
        q <= muxed;

    assign so = q;
endmodule

Real libraries place the multiplexer inside the flop cell so that the added delay falls on the scan path rather than on the functional data path wherever the library permits a dedicated scan-input pin. The functional timing path from the logic to the flop then does not include the multiplexer, which preserves setup timing at the cost of a slightly larger cell.

Shift in, capture, shift out

A scan test proceeds in four phases per pattern. First, scan-enable is asserted and the pattern is shifted in, one bit per clock, until every flop holds its assigned value. Second, scan-enable is deasserted and one functional clock pulse is applied, so the combinational logic computes and the flops capture the result. Third, scan-enable is asserted again and the captured values are shifted out while the next pattern is shifted in, overlapped to save time. Fourth, the shifted-out vector is compared against the expected response.

The shift phase runs at a reduced clock frequency, because the scan chain is a long combinational path through the flop-to-flop scan wiring and is not timed for the functional frequency. The capture phase runs at the functional frequency or at a defined test frequency. This asymmetry is the reason scan test time is dominated by the shift: the capture is one cycle, while the shift is thousands.

The chain must be constructed so that shifting produces no race. Each flop’s scan input comes from the previous flop’s output through a dedicated route, and the clock arrives at all flops in a chain at nearly the same time. A chain that spans a clock domain boundary cannot be shifted with a single clock; the standard fix is a lock-up latch at the boundary, a level-sensitive latch that delays the scan data by a half cycle so the destination flop’s hold requirement is met even with skew between the two domains.

Chains do not always span the whole chip. A block reused as an embedded core has to be reachable from the chip’s own pins without its internal nets becoming part of the chip-level chain, and IEEE 1500 defines a wrapper for that boundary: a register around the core’s ports, a serial control path, and instructions that switch the wrapper between testing the core and passing the chip’s signals through it.

The stuck-at model and why it is the default

A test pattern is derived from a fault model, which is a hypothesis about how the circuit can fail. The simplest is the single stuck-at model: a node is permanently tied to logic zero or logic one. For a circuit with N nodes, there are 2N single stuck-at faults, and a test set is judged by the fraction of those faults it detects.

The model is chosen for a pragmatic reason: it is tractable and it correlates with real defects. A short to ground looks like a stuck-at-zero. An open in a wire that leaves the node floating may look like a stuck-at value depending on the leakage that dominates. The correlation is imperfect: a resistive short that survives at low voltage but fails at high, a bridge between two nodes that only matters when they carry opposite values, and a transistor that is too weak to meet timing all escape the model. The model’s defenders point to decades of empirical correlation between stuck-at coverage and shipped quality, which is why coverage targets in the high nineties are specified for that model while other models — transition, bridging, cell-aware — are added for the defects it misses.

Transition faults address the timing class. A slow-to-rise or slow-to-fall fault at a node means the node reaches its value, but too late. Testing for it requires two patterns in sequence: one that initialises the node to the opposite value, and one that launches the transition and propagates it to an observable flop. The capture clock runs at the functional frequency, and the test passes only if the launched transition arrives in time. This is the closest that structural test gets to at-speed testing, and it requires the scan clock to be the functional clock, which is why at-speed scan needs a clocking architecture that can switch sources. The frequency the capture clock runs at is set by the sign-off corners, so a transition test is really a test against the slow corner of the corner set rather than against the design’s nominal timing.

What ATPG is searching for

Automatic test pattern generation takes a gate-level netlist with fault list and produces a set of input assignments that detect each fault. For a stuck-at fault, the tool needs two things: an assignment that activates the fault, meaning the node takes the opposite value from the stuck value, and a path from the node to an observable output along which the difference propagates, meaning every gate on the path is sensitised to that difference.

Both requirements are satisfiable by a search over the circuit’s structure. The classic algorithm works backward from the fault site to the inputs for the activation assignment, then forward to a primary output for a propagation path, and resolves conflicts by backtracking. Because the search is over a Boolean space, it is NP-complete in the general case, and the practical algorithms are heuristics that find a solution for most faults quickly and give up on the rest.

A fault the tool gives up on is not detected, and the test set has a gap. There are two responses. The first is to accept it: some faults are untestable by construction, for example a node tied to ground that can never take the value one, and those are removed from the fault list as undetectable. The second is to change the design so the fault becomes testable, which usually means adding observation points or control points, such as a test-only multiplexer that makes an internal node visible at a pin, or a bypass that gives a hard-to-control node a direct input.

There is a third category that matters more than either: faults that are testable but that the tool cannot find a pattern for within its effort limit. These are the ones that show up as an unexplained coverage shortfall, and the standard diagnosis is to run a more expensive search on exactly those faults — a longer backtrack limit, a different algorithm, or a targeted manual pattern.

from itertools import product

# Gate list in topological order: (output, op, operands)
GATES = [
    ('n1', 'and', ('a', 'b')),
    ('n2', 'not', ('c',)),
    ('z', 'or', ('n1', 'n2')),
]

def evaluate(inputs, force=None):
    values = dict(inputs)
    if force:
        values.update(force)
    for out, op, ops in GATES:
        if force and out in force:
            continue                     # a stuck node ignores its inputs
        if op == 'and':
            values[out] = int(all(values[o] for o in ops))
        elif op == 'or':
            values[out] = int(any(values[o] for o in ops))
        else:
            values[out] = 1 - values[ops[0]]
    return values

def find_test(target, stuck):
    for assignment in product((0, 1), repeat=3):
        inputs = dict(zip(('a', 'b', 'c'), assignment))
        if evaluate(inputs)['z'] != evaluate(inputs, {target: stuck})['z']:
            return inputs
    return None

print(find_test('n1', 0))   # {'a': 1, 'b': 1, 'c': 1}

The answer shows both obligations at once. Setting a and b to one activates the fault, so the good circuit has n1 at one and the faulty one has it at zero. Setting c to one forces n2 to zero, which is what lets the OR gate pass the difference through to z instead of masking it with a constant one from the other input. Had the tool chosen the other assignment that activates the fault, c equal to zero, the OR gate’s other input would have held z at one in both machines and the pattern would detect nothing.

The scan chain changes the problem in a useful way. With full scan, the sequential depth collapses to one: the circuit between flops is combinational, and the state at the capture clock is a function of the shifted-in state. The search is therefore over a combinational circuit per clock cycle, which is what makes coverage in the high nineties achievable at all. Without scan, the tool must reason about the reachable state space of a sequential machine, and coverage falls sharply.

Coverage numbers and their honesty

A coverage figure is a ratio, and the denominator is a choice. Fault coverage counts detected faults over all faults, including undetectable ones, which makes the number lower and incomparable between designs. Test coverage counts detected faults over detectable faults, which is the figure usually quoted and the one specified in a contract with a customer. The difference between the two can be several percentage points, and a design quoted at ninety-eight percent under one definition may be ninety-five under the other.

The figure is also a statement about the fault model, not about the silicon. A test set with high stuck-at coverage still misses a bridging defect between two nets that never carry opposite values in any pattern. Closing that gap requires additional models and additional patterns, and those patterns cost test time. Where the additional coverage stops being worth the test time is an economic question answered by the field return rate, and it is the same trade that Wafer Probe and the Economics of Test Coverage makes at the probe stage.

One further constraint shapes the vectors: power. During scan shift, flops toggle at a high rate and the captured patterns are unrelated to functional operation, so switching activity in the logic can exceed anything the design sees functionally. The resulting IR drop can cause a good die to fail a test, which is a yield loss rather than a test. The mitigations are to reduce shift frequency, to insert gating that holds some chains quiet, or to generate patterns with low toggling, and each of them costs test time or coverage.