Using Structural and Functional Information in Diagnostic Design

Walter HamscherAAAI 1983

Abstract

Traditional automated hardware testing often struggles with diagnostic resolution, identifying that a fault exists but failing to pinpoint its exact location. This paper introduces a system that automates the design of hardware diagnostics by modeling devices as high-level "information paths." By combining structural knowledge with functional rules, the system generates test sequences that achieve high resolution while maintaining computational efficiency.

Introduction

In the early 1980s, automated test generation primarily relied on low-level "gate-level" representations. While algorithms like the D-algorithm were effective at achieving fault coverage, they were often computationally expensive and lacked the diagnostic resolution required to identify specific failing components. Human engineers, conversely, reason about hardware through functional blocks like multiplexers and registers. This research addresses the gap between low-level automated testing and high-level human reasoning by proposing a system that automatically designs efficient and specific diagnostic plans.

The Information Path Model

The core of the proposed system is the Information Path Model, which abstracts hardware into three primitive functional devices:

  1. Gates: These transmit data only when a specific control signal is active.
  2. Junctions: These serve as points where multiple information paths merge.
  3. Selectors: These route a signal to one of several potential outputs based on an address input.
The three primitive functional devices used in the Information Path Model: Gate, Selector, and Junction.

By moving away from individual gates and wires toward these abstractions, the system can reason about device behavior in a way that naturally facilitates better diagnostic resolution.

Diagnostic Design Methodology

The diagnostic design process is divided into three distinct phases:

1. Inquiry Design

The system generates "inquiries"—specific questions such as "Does path X transmit value Y correctly?" It utilizes a library of 39 rules (categorized as Behavior, Sensitization, Goal, and Condition rules) to propagate values through the device. This process is analogous to path sensitization but operates at a higher level of abstraction.

2. Inquiry Improvement

Using the Single Point of Failure Assumption (SPFA), the system combines multiple inquiries to minimize the number of suspected components (conditions) each test relies on. For instance, if two different tests fail and share only one common component, that component is identified as the likely source of the fault.

3. Test Ordering

Tests are ordered such that those relying on the fewest components are executed first. This strategy allows the system to "exonerate" healthy parts of the circuit early in the process, systematically narrowing the search for the fault.

An example of a circuit modeled using the Information Path primitives, showing the interaction between selectors (S), gates (G), and junctions (J).

Evaluation and Results

The methodology was evaluated using a 4x2 Multiplexer circuit. The system, implemented in Franz Lisp on a VAX-11/780, demonstrated several key capabilities:

  • Human-like Planning: The system organized diagnostics into logical phases—testing the output first, followed by addressing logic, and finally data inputs—mirroring the approach of a human expert.
  • Automated Sensitization: It successfully generated complex inquiries that accounted for multiple paths and conditions, including "OR" logic for suspected faulty paths.
  • Efficiency: Due to the high level of abstraction, search trees remained small, making the computation highly efficient for small-to-medium devices.

Discussion and Limitations

While the Information Path Model provides a powerful framework for diagnostic design, several areas for future work remain. The current vocabulary is limited to three primitives; extending this to include computational units like adders and state-holding devices (memory) is necessary for broader applicability. Additionally, the model currently assumes faults occur on paths rather than within devices and assumes unidirectional information flow. Integrating internal device faults and handling bidirectional buses are critical next steps for the evolution of automated hardware troubleshooting.

Summary updated

BibTeX
@inproceedings{hamscher1983using,
  author = {Walter Hamscher},
  title = {{Using Structural and Functional Information in Diagnostic Design}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1983},
}

Loading related content...

Figure