Name
Abstract | ||
|---|---|---|
This paper presents a new approach for diagnosing shorts in interconnects in which the adjacencies between nets are known. This structural approach exploits different graph coloring techniques to generate a test set with no aliasing and confounding, i.e., full diagnosis (detection and location) is accomplished. Initially, a simple coloring approach based on a greedy condition of the adjacency graph is proposed for fault detection. Then, the conditions for aliasing and confounding are analyzed with respect to the sizes of the possible shorts. These results are used to generate new colors using a process called color mixing. Color mixing guarantees that additional tests, required in order to avoid aliasing/confounding, will use appropriate codes. The characteristics of unbalanced/balanced codes for encoding the colors in the vector-generation process of interconnect diagnosis are discussed and are proved to yield full diagnosis using a novel method. An algorithm for full diagnosis is then presented; this algorithm has an execution complexity of O(max{N2, N×D3}) where N is the number of nets and D is the maximum degree of the nodes in the adjacency graph. Simulation results show that the proposed approach requires a smaller number of test vectors than previous approaches. |
Year | DOI | Venue |
|---|---|---|
1998 | 10.1145/290833.290848 | ACM Trans. Design Autom. Electr. Syst. |
Keywords | Field | DocType |
adjacency graph,diagnosis,different graph,structural approach,structural diagnosis,new approach,graph coloring,simple coloring approach,fault detection,interconnect,full diagnosis,syndrome,additional test,balanced code,previous approach,maximum degree | Adjacency list,Computer science,Fault detection and isolation,Parallel computing,Algorithm,Aliasing,Degree (graph theory),Greedy coloring,Color mixing,Test set,Graph coloring | Journal |
Volume | Issue | Citations |
3 | 2 | 2 |
PageRank | References | Authors |
0.38 | 16 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| X. T. Chen | 1 | 61 | 6.63 |
| F. J. Meyer | 2 | 2 | 0.38 |
| F. Lombardi | 3 | 232 | 24.13 |