Hierarchical diagnosis of multiple faults

Abstract

Due to large search spaces, diagnosis of combinational circuits is often practical for finding only single and double faults. In principle, system models can be compiled into a tractable representation (such as DNNF) on which faults of arbitrary cardinality can be found efficiently. For large circuits, however, compilation can become a bottleneck due to the large number of variables necessary to model the health of individual gates. We propose a novel method that greatly reduces this number, allowing the compilation, as well as the diagnosis, to scale to larger circuits. The basic idea is to identify regions of a circuit, called cones, that are dominated by single gates, and model the health of each cone with a single health variable. When a cone is found to be possibly faulty, we diagnose it by again identifying the cones inside it, and so on, until we reach a base case. We show that results combined from these hierarchical sessions are sound and complete with respect to minimum-cardinality diagnoses. We implement this method on top of the diagnoser developed by Huang and Darwiche in 2005, and present evidence that it significantly improves the efficiency and scalability of diagnosis on the ISCAS-85 circuits.