Diagnosing circuits with state: an inherently underconstrained problem

Abstract

“Hard problems ” can be hard because they are computationally intractable. or because they are underconstrained. Here we describe candidate generation for digital devrces with state, a fault localization problem that is intractable when the devices are described at low levels of abstraction, and is underconstrained when described at higher levels of abstraction. Previous v;ork [l] has shown that a fault in a combinatorial digital circuit can be localized using a constraint-based representation of structure and behavior. ln this paper we (1) extend this represerltation to model a circuit with state by choosrng a time granularity and vocabulary of signals appropriate to that circuit; (2) demonstrate that the same candidate generation procedure that works for combinatorial circuits becomes indiscriminate when applied to a state circuit modeled in that extended