| Home | Organizers | Proceedings Editors | Proceedings Contributors | Search | | ||
|
|
|||
|
||||
|
|
||||
| Title: | A GRAPH ALGORITHM FOR FINDING THE MINIMUM TEST SET OF A BDD-BASED CIRCUIT | |
| DOI No: | 10.1142/9781860948534_0060 | |
| Source: | INNOVATIVE APPLICATIONS OF INFORMATION TECHNOLOGY FOR THE DEVELOPING WORLD (pp 382-386) | |
| Author(s): | GOPAL PAUL
Dept. of Electronics, CEG, Anna University, Chennai – 600 025, India BHARGAB B. BHATTACHARYA Dept. of Comp. Sc. & Engg., Indian Institute of Technology, Kharagpur – 721 302, India AJIT PAL Dept. of Comp. Sc. & Engg., Indian Institute of Technology, Kharagpur – 721 302, India ANNAPURNA DAS Dept. of Electronics, CEG, Anna University, Chennai – 600 025, India |
|
| Abstract: | The Binary Decision Diagram (BDD) is a powerful vehicle for large-scale functional specification and circuit design. In this paper, we consider the open problem of generating in polynomial time, the exact minimum set (T) of test vectors for detecting all single stuck-at faults in such a BDD-based circuit. We show that, for a single-output circuit, |T| = 2k, where k is the minimum number of paths that cover all the edges of the BDD graph. The value of k, and consequently the test set T, can be readily determined by running the max-flow algorithm on a network derived from the BDD, followed by a simple graph traversal. This procedure not only generates the optimal test set in polynomial time, but also obviates the need of employing an ATPG (Automatic Test Pattern Generator) and a fault simulator. | |
| Full Text: | View full text in PDF format (290KB) | |
| TOC: | Back to Table of Contents | |
|
||