Polynomial time solvable fault detection problems
- 4 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
A class of combinational circuits, called the (k,K)-circuits is presented, and a polynomial-time algorithm to detect any single or multiple stuckfault in such circuits is introduced. The (k,K)-circuits are a generalization of H. Fujiwara's (1988) K-bounded circuits. The fault detection problem is formulated as an energy minimization problem using the bidirectional neural net model proposed earlier. A minimizing point of the energy function corresponds to a test. A polynomial-time algorithm is presented here to solve the single and multiple fault-detection problem for the (k,K)-circuits by recursively eliminating variables in the energy function.Keywords
This publication has 6 references indexed in Scilit:
- Computational complexity of controllability/observability problems for combinational circuitsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Toward massively parallel automatic test generationIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1990
- Artificial neural networksIEEE Circuits and Devices Magazine, 1988
- Complexity of Finding Embeddings in a k-TreeSIAM Journal on Algebraic Discrete Methods, 1987
- Polynomially Complete Fault Detection ProblemsIEEE Transactions on Computers, 1975
- On simple characterizations of k-treesDiscrete Mathematics, 1974