A model-based diagnosis system for identifying faulty components in digital circuits

We describe the ideas and implementation of a model-based diagnosis system for digital circuits. Our work is based on Reiter's theory of diagnosis from first principles [14], incorporated with Hou's theory of measurements [17], to derive possible diagnoses in a fault diagnosis task. To determine the best order in which measurements are to be taken, a measurement selection strategy using the genetic algorithm (MSSGA) is proposed. A circuit description language for describing circuits hierarchically is given. An efficient propositional logic prover used for consistency checking based on the trie structure is developed [22]. An example run is given to illustrate the working of the system. Finally, a comparison with other systems is discussed, and possible extensions to our system are described.