|dc.description.abstract||The objective of the research reported in this thesis is to develop new test generation algorithms using mathematical optimization techniques. These algorithms minimize test vector sets of a combinational logic circuit for fault detection and diagnosis, respectively.
The first algorithm generates a minimized fault detection test set. The test minimization Integer Linear Program (ILP) described in the literature guarantees an absolute minimal test set only when we start with the exhaustive set of test vectors. As it is impractical to work with exhaustive test sets for large circuits, the quality of the result will depend upon the starting test set. We use the concept of independent fault set (IFS) defined in the literature to find a non-exhaustive vector set from which the test minimization ILP will give an improved (often minimal) test set. An IFS is a set of faults such that no two faults in the set can be detected by the same vector. The largest IFS gives a lower bound on the size of the test set since at least one vector is needed to detect each fault in the IFS. This lower bound can be closely achieved by selecting tests from the test vectors derived for the faults in the IFS. Using the theory of primal-dual linear programs, we model the IFS
identification as the dual of the test minimization problem. A solution of the dual problem, whose existence is guaranteed by the duality theorem, gives us a conditionally independent fault set (CIFS). A CIFS is an IFS relative to a non-exhaustive vector set. Our CIFS is,
therefore, not absolute but is specific to the starting vector set. Successively adding more
vectors to test the faults in the identified CIFS and solving the dual problem, we bring the CIFS closer to its minimal size. In the process of reaching the absolute IFS we have accumulated a non-exhaustive set of vectors that can now be minimized by the test minimization ILP (now referred to as the primal problem) to get a minimal test set. Thus the newly proposed primal-dual solution to the minimal test generation problem is based on (1) identifying independent faults, (2) generating tests for them, and (3) minimizing the tests. The primal-dual method, when applied to the ISCAS85 benchmark circuits, produces better results compared to an earlier primal ILP-alone test minimization method . For the largest benchmark circuit c7552, the earlier minimization method (primal ILP) produced a
test set of 145 vectors in 151 CPU seconds, while our method (primal-dual ILP) produced a test set of 139 vectors in just 71 CPU seconds.
In the second part of this research, we address the minimization of a diagnostic test
set without reduction in diagnostic resolution. A full-response dictionary is considered for diagnosis. The full-response dictionary distinguishes between faults detected by exactly the same test vectors but at different outputs of the circuit. A new diagnostic ILP is formulated from a diagnostic table obtained by fault simulation without fault dropping. This ILP can become intractable for large circuits due to very large number of constraints that typically grows quadratically with the number of faults. We make the complexity manageable by two innovations. First, we define diagnostic independence relation for fault-pairs with no common test vector and also for faults-pairs detected by a common vector but at different outputs of the circuit. These fault-pairs require no constraint in the ILP, thus reducing the number of constraints. Second, we propose a two-phase ILP approach. An initial ILP phase, using an existing ILP procedure that requires a smaller set of constraints (linear in the number of faults), preselects a minimal detection test set from the given unoptimized vector set. Fault-pairs that are already distinguished by the preselected detection vectors then do not require distinguishing constraints in the diagnostic ILP of the final phase, which selects a minimal set of additional vectors for distinguishing between the remaining fault-pairs. The overall minimized diagnostic test set obtained by the two phase method
may be only slightly longer than a one-step diagnostic ILP optimization, but it has the
advantages of significantly reduced computation complexity and reduced test application time. The two-phase method, when applied to the ISCAS85 benchmark circuits, produces very compact diagnostic test sets. For the largest benchmark circuit c7552, an earlier
compaction method  has reported a test set of 198 vectors obtained in 33.8 seconds. Our method produced a test set of 128 vectors in 18.57 seconds.||en