Introduction
Model-Based Diagnosis (MBD) is a critical process for identifying the root causes of system failures by comparing observed behavior against a formal model. While well-established for combinational circuits, MBD faces significant hurdles in sequential circuits. These systems incorporate memory elements, such as flip-flops, meaning their outputs depend not only on current inputs but also on past states. This temporal dependency makes diagnosing transient or intermittent faults—common in high-radiation environments like aerospace—exceptionally complex.
The Challenge of Sequential Diagnosis
In sequential systems, a fault may manifest only briefly (transient) or at irregular intervals (intermittent). Traditional diagnostic tools often assume "permanent" faults to simplify the mathematics. However, such assumptions fail to capture "soft errors" that disrupt signals momentarily. To address this, researchers have proposed a general framework that identifies any fault pattern without restrictive assumptions.
As shown in the circuit schematic above, signals propagate through logic gates ($x_n, a_n$) and are stored in flip-flops ($f_n$). A fault in any component can propagate through time, affecting future states and outputs ($o_n$).
Proposed Methodology: FTNL and MOA Encoding
The authors introduce a two-pronged approach to streamline sequential diagnosis:
1. Finite Trace Next Logic (FTNL)
Rather than employing complex temporal logics like Linear Temporal Logic (LTL), which are computationally expensive and designed for infinite sequences, the researchers developed Finite Trace Next Logic (FTNL). FTNL focuses on finite time horizons and utilizes a single temporal operator, X ("next"), to describe signal transitions through memory over a specific window of time.
2. Multi-Operand Adder (MOA) Encoding
To solve the diagnosis, the circuit is "unrolled" over $T$ time steps, transforming the temporal problem into a Boolean Satisfiability (SAT) problem. A core requirement is finding the minimal cardinality—the smallest set of faults that explains the observations.
While standard methods use Sorting Networks (SNs) for fault counting, this research utilizes Multi-Operand Adders (MOAs). MOAs are digital circuits that sum binary inputs and are mathematically more compact than SNs, leading to significantly smaller logic representations.
Key Results and Performance Trade-offs
The transition to MOA-based encoding yielded substantial improvements in space complexity:
- Variable and Clause Reduction: MOAs reduced the number of variables by 19.7 to 67.6 times and clauses by 18.4 to 62 times compared to Sorting Networks.
- Setup Efficiency: The time required to convert circuit models into Conjunctive Normal Form (CNF) for SAT solvers was 6.2 to 22.2 times faster.
Despite these gains in memory efficiency and setup speed, a trade-off exists: the actual SAT solving time was 3.4 to 5.5 times slower for MOA models than for SN models. This suggests that MOAs are ideal for memory-constrained environments, while SNs remain preferable when raw processing speed is the primary bottleneck.
Conclusion and Future Directions
This research demonstrates that simplifying temporal logic and optimizing cardinality encoding can drastically reduce the complexity of sequential circuit diagnosis. By moving away from permanent fault assumptions, the framework becomes robust enough for high-reliability applications. Future work will focus on determining the optimal time horizon ($T$) for completeness and extending the logic to handle asynchronous systems with multiple clocks.
Summary updated