Using functional representation in the reducing ATPG search

Abstract

Major advances in VLSI technology over the past ten years has made the problem of fault detection for circuits more difficult. As these circuits increase in size, the demand for a highly efficient Automatic Test Pattern Generation algorithm exists. The problem for most ATPG algorithms is in minimizing the vast redundant space in a highly reconvergent fanout circuit. All redundant stuck-at faults which occur, are due to this reconvergent fanout within a circuit. Reconvergent fanout introduces dependencies in the values which can be assigned to various nodes. The objective of deterministic ATPG is to simultaneously satisfy all dependencies in the logically modified circuit (modification due to the fault). It is the goal to more efficiently prove redundancy, so as to not waste valuable time searching for a test when one does not exist. This research uses partial functional calculation techniques in order to calculate whether or not it is possible to achieve a test, given a set of required values within the network. These functional calculations use Ordered Partial Decision Diagrams (OPDDS) which are an ordered set of partial expansion graphs, which represent the larger implicants of a function when there is too little memory for the entire representation. OPDD graphs help reduce the search space associated with generating a. test for stuck-at faults. By incorporating OPDD calculations into the ATPG algorithm, one is able to identify the redundancy quickly. When ATPG assigns a value to a node in the network, the function graph at that site is AND'ed with the function graphs representing all other value assignments in order to produce a single functional graph. This graph eliminates any input combinations which cannot simultaneously satisfy all assignments. The OPDD graph also aids in finding additional mandatory assignments which must occur that normal ATPG techniques did not find. By adding these additional assignments, the search space can be exponentially reduced before a decision needs to be made. This leads to proving the fault site either testable or untestable, more rapidly . These functional calculations are used in conjunction with an ATPG algorithm developed by S. Lin [181 for his master's thesis at Texas A&M University. The complete algorithm is performed on the ISCAS combinational benchmark circuits in order to evaluate its performance. These circuits were chosen so as to compare with other researchers, and were specifically selected due to their ability to defeat commercial and academic ATPG systems.