Abstract
Diagnosing faults in digital circuits with state (memory) is fundamentally more challenging than diagnosing combinatorial circuits. This paper explores why stateful systems are inherently underconstrained and presents a methodology using temporal hierarchies, single-stepping, and hierarchic refinement to effectively pinpoint faulty components.
Introduction
In the early 1980s, model-based diagnosis (MBD) revolutionized the way we identify faults in combinatorial circuits. By using techniques like constraint suspension—where a component's mathematical constraints are temporarily ignored to check for system consistency—researchers could efficiently isolate faulty gates. However, these methods falter when applied to circuits with "state," such as registers and counters. In stateful systems, a single fault propagates over time, creating a sequence of errors that makes the diagnostic problem inherently underconstrained.
The Challenge of Stateful Diagnosis
When a circuit possesses memory, its output at any given time depends not only on current inputs but also on its history. If a component fails, it doesn't just produce a single incorrect value; it creates an "information gap" across multiple time slices. Without intermediate visibility, a diagnostic engine might find that almost any component in the system could have produced the observed error, leading to an "indiscriminate" list of candidates.
Overcoming the Underconstrained Problem
To address the underconstrained nature of stateful circuits, the authors propose a multi-faceted approach:
- Temporal Hierarchies: Modeling behavior at different time granularities (e.g., clock cycles vs. gate delays) allows the system to focus on functionally significant state changes while ignoring transient transitions.
- Constraint Replication: The circuit is "unrolled" over time, representing it as a series of snapshots where the state at time $t$ informs the state at $t+1$.
- Single-Stepping: By observing register contents at every clock cycle, the diagnostic problem is broken down into a series of simpler, combinatorial-like subproblems, significantly increasing internal visibility.
- Hierarchic Refinement: When high-level diagnosis remains ambiguous, the system "zooms in" on candidate modules to examine their internal gate-level structure.
Hierarchic Refinement in Practice
Hierarchic refinement is a powerful tool for narrowing down candidates. By moving from a functional block description to a structural gate-level description, the diagnostic engine can rule out components that were previously indistinguishable.
Case Study: The Sequential Multiplier
The authors demonstrated their approach using a 4-bit sequential multiplier. In a scenario with low visibility (observing only the final output), the system was indiscriminate, identifying nearly all major components as potential culprits. However, by employing single-stepping to observe the accumulator at each cycle and then applying hierarchic refinement to look inside the registers and drivers, they successfully isolated the fault to a specific bit-slice or gate.
Conclusion
Diagnosing stateful circuits requires more than just structural knowledge; it requires a deep integration of temporal modeling and hierarchical decomposition. While increasing visibility through single-stepping and deep structural analysis comes with a computational cost, it is a necessary trade-off to resolve the underconstrained nature of memory-dependent systems. Future work remains in optimizing the mapping between temporal layers and managing the complexity of "unrolling" large-scale circuits.
Summary updated