Diagnosing Circuits With State: An Inherently Underconstrained Problem

Walter Hamscher, Randall DavisAAAI 1984

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.

Waveforms showing the relationship between clock signals, data inputs, and state outputs (Q0, Q1) over time, highlighting the temporal complexity of stateful circuits.

Overcoming the Underconstrained Problem

To address the underconstrained nature of stateful circuits, the authors propose a multi-faceted approach:

  1. 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.
  2. 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$.
  3. 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.
  4. 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.

The mapping between a high-level functional block (TBR) and its internal implementation, including flip-flops and logic gates, which is essential for hierarchic refinement.

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

BibTeX
@inproceedings{hamscher1984diagnosing,
  author = {Walter Hamscher and Randall Davis},
  title = {{Diagnosing Circuits With State: An Inherently Underconstrained Problem}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1984},
}
Figure