Diagnostic reasoning in digital systems

Described is an efficient method for fault diagnosis in digital systems based on the technique of reasoning. The methodology operates on the observed erroneous behavior and the structure of the system. The behavior consists of the error(s) observed on the circuit's output lines and specific values on the circuit's input lines. The techniques described improve on previously published research on diagnostic reasoning in two ways. Previous work has stressed system independent techniques which could be used to diagnose any faulty system whose structure can be represented. By concentrating on the specific case of diagnosing faulty digital circuits, it is possible to simplify the representation of the structure of the system. This representation, in the form of an AND/OR fault tree, efficiently abstracts the structure of a faulty digital system. More importantly, a method for partitioning the digital system is introduced which can considerably reduce the runtime complexity of a diagnosis.