Fault Diagnosis and Logic Debugging
Alexander D. S. Smith, Andreas G. Veneris, Moayad Fahim Ali, Anastasios Viglas · 2005
Recent advances in Boolean satisfiability have made it an attractive engine for solving many digital very-large-scale- integration design problems. Although useful in many stages of the design cycle, fault diagnosis and logic debugging have not been addressed within a satisfiability-based framework. This work proposes a novel Boolean satisfiability-based method for multiple-fault diagnosis and multiple-design-error diagnosis in combinational and sequential circuits. A number of heuristics are presented that keep the method memory and run-time efficient. An extensive suite of experiments on large circuits corrupted with different types of faults and errors confirm its robustness and practicality. They also suggest that satisfiability captures signif- icant characteristics of the problem of diagnosis and encourage novel research in satisfiability-based diagnosis as a complementary process to design verification.