IEICE TRANSACTIONS on Fundamentals
MINT--An Exact Algorithm for Finding Minimum Test Set--
Summary :
In this paper, an exact algorithm for finding minimum test set which detects all testable stuck-at faults of a given combinational circit 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 covrering 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 complexith of minimum test set problen is much higher than that of ordinary test pattern generation problem, so that practical signifcance 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 minimumset covering problems.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E76-A No.10 pp.1652-1658
- Publication Date
- 1993/10/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Special Section PAPER (Special Section on VLSI Design and CAD Algorithms)
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Yusuke MATSUNAGA, "MINT--An Exact Algorithm for Finding Minimum Test Set--" in IEICE TRANSACTIONS on Fundamentals,
vol. E76-A, no. 10, pp. 1652-1658, October 1993, doi: .
Abstract: In this paper, an exact algorithm for finding minimum test set which detects all testable stuck-at faults of a given combinational circit 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 covrering 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 complexith of minimum test set problen is much higher than that of ordinary test pattern generation problem, so that practical signifcance 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 minimumset covering problems.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e76-a_10_1652/_p
Copy
@ARTICLE{e76-a_10_1652,
author={Yusuke MATSUNAGA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={MINT--An Exact Algorithm for Finding Minimum Test Set--},
year={1993},
volume={E76-A},
number={10},
pages={1652-1658},
abstract={In this paper, an exact algorithm for finding minimum test set which detects all testable stuck-at faults of a given combinational circit 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 covrering 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 complexith of minimum test set problen is much higher than that of ordinary test pattern generation problem, so that practical signifcance 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 minimumset covering problems.},
keywords={},
doi={},
ISSN={},
month={October},}
Copy
TY - JOUR
TI - MINT--An Exact Algorithm for Finding Minimum Test Set--
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1652
EP - 1658
AU - Yusuke MATSUNAGA
PY - 1993
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E76-A
IS - 10
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - October 1993
AB - In this paper, an exact algorithm for finding minimum test set which detects all testable stuck-at faults of a given combinational circit 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 covrering 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 complexith of minimum test set problen is much higher than that of ordinary test pattern generation problem, so that practical signifcance 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 minimumset covering problems.
ER -
English
