Fault Collapsing in Digital Circuits Using Fast Fault Dominance and Equivalence Analysis with SSBDDs
The paper presents a new method and an algorithm for structural fault collapsing to reduce the search space for test generation, to speed up fault simulation and to make the fault diagnosis easier in digital circuits. The proposed method is based on hiera
- PDF / 2,489,976 Bytes
- 23 Pages / 439.37 x 666.142 pts Page_size
- 95 Downloads / 170 Views
Abstract. The paper presents a new method and an algorithm for structural fault collapsing to reduce the search space for test generation, to speed up fault simulation and to make the fault diagnosis easier in digital circuits. The proposed method is based on hierarchical topology analysis of the circuit description at two levels. First, the gate-level circuit will be converted into a macro-level network of Fan-out Free Regions (FFR) each of them represented as a special type of structural BDD. This conversion procedure represents as a side-effect the first step of fault collapsing, resulting in a compressed Structurally Synthesized BDD (SSBDD) model explicitly representing the collapsed set of representative fault sites. The paper presents an algorithm which implements a complementary step of further fault collapsing. This algorithm is carried out at the macro-level FFR-network by topological reasoning of equivalence and dominance relations between the nodes of the SSBDDs. The algorithm has linear complexity and is implemented as a continuous scalable fault eliminating procedure. We introduce higher and lower bounds for fault collapsing and provide statistics of distribution of fault collapsing results over a broad set of benchmark circuits. Experimental research has demonstrated considerably better results of structural fault collapsing in comparison with state-of-the-art. Keywords: Combinational circuits Fault collapsing Fault equivalence and dominance Binary decision diagrams Lower and higher bounds
1 Introduction Fault collapsing is a procedure which is applied to reduce the number of faults of a given circuit to be targeted for testing purposes. Using a reduced set of only representative faults instead of a full set of faults has the goal to minimize the efforts in many test related tasks like test pattern generation, fault simulation for test quality evaluation, fault diagnosis, circuit testability evaluation etc. The methods of fault collapsing are classified as structural and functional. Structural fault collapsing uses only the topology of the circuit whereas functional fault collapsing uses the circuit functional properties inherent in the circuit.
© IFIP International Federation for Information Processing 2016 Published by Springer International Publishing AG 2016. All Rights Reserved Y. Shin et al. (Eds.): VLSI-SoC 2015, IFIP AICT 483, pp. 23–45, 2016. DOI: 10.1007/978-3-319-46097-0_2
24
R. Ubar et al.
There are two classical ways used for structural fault collapsing: fault equivalence based and fault dominance based collapsing [1]. A fault fj is said to dominate a fault fi if every test that detects fi also detects fj. If fj dominates fi, only fi needs to be considered during test generation. When two faults dominate each other, they are called equivalent. If two faults are equivalent, only one of them needs to be considered during test gene-ration or fault diagnosis. Structural fault collapsing uses the topology of the circuit structure. For example, a stuck-at 0 fault (SAF y/0) at the outp
Data Loading...
