TY - JOUR

T1 - MINT-An exact algorithm for finding minimum test set

AU - Matsunaga, Yusuke

PY - 1993/10

Y1 - 1993/10

N2 - In this paper, an exact algorithm for finding minimum test set which detects all testable stuck-at faults of a given combinational circuit is presented. So far several heuristic algorithms for this problem are proposed, but no efficient exact algorithms are known. To solve this exactly, minimum test set problem is formalized as a minimum set covering problem, and then implicit manipulation technique using binary decision diagrams(BDDs) is applied. The algorithm presented in the paper has two contributions. One is utilization of maximal compatible fault set, which can drastically reduce the number of candidates for minimum test set. A new BDD based algorithm for extracting all maximal compatible fault sets is shown. The other is a new implicit manipulation technique handling with huge covering matrix. Actually, the algorithm using this technique can handle minimum set covering problem with over ten thousand columns in a few minutes. Experiments using ISCAS benchmark circuits show that the algorithm is quite efficient for small (100-300 gates) circuits. A computational complexity of minimum test set problem is much higher than that of ordinary test pattern generation problem, so that practical significance of this method is not high. But the algorithm is still useful for evaluation of other heuristic algorithms, furthermore, this implicit manipulation technique can also be applied to other minimum set covering problems.

AB - In this paper, an exact algorithm for finding minimum test set which detects all testable stuck-at faults of a given combinational circuit is presented. So far several heuristic algorithms for this problem are proposed, but no efficient exact algorithms are known. To solve this exactly, minimum test set problem is formalized as a minimum set covering problem, and then implicit manipulation technique using binary decision diagrams(BDDs) is applied. The algorithm presented in the paper has two contributions. One is utilization of maximal compatible fault set, which can drastically reduce the number of candidates for minimum test set. A new BDD based algorithm for extracting all maximal compatible fault sets is shown. The other is a new implicit manipulation technique handling with huge covering matrix. Actually, the algorithm using this technique can handle minimum set covering problem with over ten thousand columns in a few minutes. Experiments using ISCAS benchmark circuits show that the algorithm is quite efficient for small (100-300 gates) circuits. A computational complexity of minimum test set problem is much higher than that of ordinary test pattern generation problem, so that practical significance of this method is not high. But the algorithm is still useful for evaluation of other heuristic algorithms, furthermore, this implicit manipulation technique can also be applied to other minimum set covering problems.

UR - http://www.scopus.com/inward/record.url?scp=0027682430&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0027682430&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:0027682430

SN - 0916-8508

VL - E76-A

SP - 1652

EP - 1658

JO - IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

JF - IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

IS - 10

ER -