Exploiting dynamic computation in diagnosis of bridging faults
Yiming Gong · 1996
Sufficient empirical evidence now exists to conclude that to achieve high defect coverage, failure modes that don't result in single stuck-at behavior must be considered. One such failure mode, which is quite common, can be modeled by the bridging fault model. The number of bridging faults to be considered is very large. The challenge is to develop new paradigms for analyzing such faults. In this dissertation we consider the generic problem of diagnosing bridging faults. In particular we have developed paradigms that exploit for two important bridging fault diagnosis related problems--diagnostic test and fault location. Diagnostic test has a complexity of NP-Complete. Heuristic must be used. Traditional approach to diagnostic test targets a set of faults and generates test vectors which distinguishes each pair of faults in the set of faults. We called this approach approach because the test sets are precomputed for the set of faults. The main drawback of this approach is that when the number of targeting faults is large, which is the case for bridging faults, or the size of the circuit to be diagnosed increases, the computation time and space required become very large. Thus, this approach is suitable for moderate sized circuits. On the other hand, it is often the case that many of the faulty chips have the same faulty response, and many of the targeted faults never occur. Including these faults only increases the computation time and space. In this dissertation we propose adaptive diagnostic test generation and iterative diagnostic test generation paradigms which do away with the static approach and compute diagnostic test set dynamically. The new paradigms combine the diagnostic test with diagnosis process and therefore they are new diagnosis paradigms as well. Fast algorithms for locating bridging faults have also been developed. Results, for the Wired models and the Voting model, respectively, are presented. The novel features of these algorithms are (i) unlike previous algorithms they do not use full fault dictionary for bridging faults but use only portions of the stuck-at fault dictionary which are computed dynamically; (ii) they enumerate bridging faults implicitly using a compact data structure; (iii) heuristics, based on stuck-at fault simulation only, are used. The net result is a time and space efficient algorithm. Our experimental results on bridging faults show that dynamic computation is a very promising way for analyzing large number of faults and large sized circuits. Algorithms presented in this dissertation are very effective and efficient for diagnosing bridging faults.