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:
- Gates: These transmit data only when a specific control signal is active.
- Junctions: These serve as points where multiple information paths merge.
- Selectors: These route a signal to one of several potential outputs based on an address input.
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.
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