ATPG pattern generation

In short: ATPG generates the minimum set of input vectors that, applied through scan chains, forces every targetable manufacturing defect to produce an observable mismatch at a scan or primary output — closing coverage toward the 99%+ needed for a shippable test program.

Automatic Test Pattern Generation (ATPG) is the engine that turns a fault model into a concrete list of test vectors a tester applies to each die on the probe card. Done well, it is the difference between a test program that catches 99.4% of stuck-at defects and one that lets field escapes through at hundreds of DPPM. This article walks through the algorithms (D-algorithm, PODEM), how faults are targeted and dropped, how patterns are compacted, and how engineers drive coverage to closure on real blocks.

The fault model and the goal

ATPG works against a fault list, most commonly the single stuck-at (SA0/SA1) model, where each gate pin can be stuck at logic 0 or 1. A 2-input NAND contributes up to 6 faults (3 pins × 2 values, less collapsing). Fault collapsing merges equivalent and dominated faults — a 10-million-instance SoC block might collapse 40M raw faults down to ~18M, cutting runtime roughly in half. Modern flows add transition-delay and path-delay faults for at-speed test, plus bridging and cell-aware (defect-based) faults derived from the foundry's layout-extracted parasitics.

A single stuck-at test must do two things at once: activate the fault (drive the opposite value at the fault site) and propagate its effect to an observable point. Either half failing means the fault stays undetected.

D-algorithm: the structural foundation

Roth's D-algorithm (IBM, 1966) introduced the 5-valued algebra {0, 1, D, D̄, X}. The symbol D means "1 in the good circuit, 0 in the faulty circuit" (D̄ is the inverse). To test a line stuck-at-0, you justify a D at that line, then propagate the D forward along a sensitized path to an output by setting side-inputs to their non-controlling values (1 for AND/NAND, 0 for OR/NOR). Finally you justify every assignment backward to the primary/scan inputs. The D-frontier is the set of gates with a D on an input and X on the output — the search works by advancing this frontier to an output.

PODEM and why it scaled

D-algorithm assigns values on internal lines and can thrash through enormous internal search spaces. Goel's PODEM (Path-Oriented Decision Making, 1981) restricts decision points to primary inputs only and uses backtracing to pick which PI to set next. Because the decision tree branches only on PIs, the search space shrinks dramatically and backtracking is far cheaper. FAN (Fujiwara, 1983) added multiple-backtrace and headlines to go faster still. Every commercial tool — Synopsys TetraMAX/TestMAX ATPG, Siemens EDA Tessent, Cadence Modus — descends from these ideas, layered with learning, implication graphs, and SAT-based engines for hard-to-detect faults.

Fault targeting and simulation drop

ATPG does not derive a pattern for every fault one at a time — that would be hopeless at scale. The loop is: pick an undetected target fault, generate a pattern, then fault-simulate that pattern against the whole remaining fault list and drop every fault it happens to detect. A single well-chosen vector often detects thousands of faults incidentally. This "test-and-drop" synergy with fault simulation is what makes coverage climb steeply early and flatten late, where only the random-resistant faults remain.

Test coverage vs. fault coverage

Two metrics confuse newcomers. Fault coverage = detected / total faults. Test coverage = detected / (total − undetectable), excluding faults that are structurally untestable (ATPG-untestable, tied, blocked). Test coverage is the number sign-off cares about. A realistic target is 99%+ stuck-at test coverage and 90%+ transition coverage; the gap is where ABV, DFT fixes (adding observe points, test points), and defect-based (cell-aware) patterns earn their keep.

Pattern compaction

Raw ATPG can emit far more patterns than needed. Tester time is money — at ~$0.01–0.05 per device-second, halving the pattern count directly cuts cost of test. Two techniques dominate. Static compaction merges compatible patterns (where X-fill bits of one fill don't-cares of another) after generation. Dynamic compaction packs multiple fault targets into one pattern during generation, filling remaining X positions to detect additional faults. On-chip test compression (Synopsys DFTMAX, Siemens TestKompress/EDT) multiplies this further, decompressing a few scan-in channels into hundreds of internal chains and compacting responses through a MISR/XOR network — often 50–200× data-volume reduction.

Compaction and compression attack different costs: compaction reduces the number of patterns (test time); compression reduces the data per pattern (tester memory and I/O), typically by 50–200×.

Driving coverage to closure

When coverage stalls below target, the engineer's playbook is methodical: raise the abort limit so hard faults get more decision budget; switch to the SAT/learning engine for redundant-looking faults; audit scan constraints and X-sources (uninitialized RAM outputs, non-scan flops, analog boundaries) that block propagation; and feed AU/undetected reports back to the DFT team to insert control/observe test points. For at-speed, verify the launch-capture timing (LOC vs. LOS) and clock constraints — a surprising number of "low transition coverage" problems are really clocking or false-path issues, not ATPG weakness. Teams building rigorous DFT sign-off flows often pair in-house effort with specialist support such as Avecas VLSI design services for complex multi-core compression architectures.

The companion topics — scan chain insertion and fault grading — complete the picture: scan makes internal state controllable and observable, fault simulation measures what a pattern set actually catches, and ATPG manufactures the vectors in between.

Want to run TestMAX/Tessent ATPG on real netlists and close coverage hands-on? Explore our DFT track on the CourseTron courses page and build a tapeout-ready test program.

Frequently asked questions

What is the difference between the D-algorithm and PODEM?

The D-algorithm makes decisions on internal circuit lines and can explore a very large internal search space. PODEM restricts all decisions to primary (and scan) inputs and uses backtracing, which shrinks the search tree and makes backtracking far cheaper — so it scales to large designs where the D-algorithm struggles.

Why is test coverage usually higher than fault coverage?

Fault coverage divides detected faults by the total fault population, while test coverage excludes faults that are provably untestable in the given structure (tied, blocked, ATPG-untestable). Because the denominator is smaller for test coverage, it reports a higher, more meaningful number for sign-off.

What does pattern compaction actually save?

It reduces the number of test patterns, which directly cuts tester application time and therefore cost of test. Dynamic compaction packs several fault targets into each pattern during generation; static compaction merges compatible patterns afterward. Compression is complementary and reduces data volume per pattern.

Why do some faults remain undetected even at high effort?

They may be structurally redundant (no vector can both activate and propagate them), blocked by X-sources such as uninitialized memories or non-scan logic, or require DFT changes like added test points. These show up as ATPG-untestable or possibly-detected and often need design intervention rather than more ATPG runtime.