Deterministic asymmetrical system-level diagnosis model is considered assuming connected graphs, permanent faults and complete t-diagnosis. Diagnosis model properties are investigated. It is shown that any one-step t-diagnosable graph always consists of at least 2·(n - 1) edges, where 1 < t <= n - 1. The notion of optimal one-step t-diagnosable graphs is defined for 1 < t <= n - 1. It is shown that optimal one-step t-diagnosable graphs with 2·(n - 1) edges can be synthetized based on undirected spanning trees by replacement of each unoriented edge with two oppositely directed edges. It is proven that synthetized optimal graphs are always one-step t-diagnosable. The practical value of the considered deterministic asymmetrical system-level diagnosis model is the possibility to describe timer-based tests assuming that a faulty timer always masks the faults of tested units but never distorts the state of fault-free tested units.
Kramarenko Michael Borisovich Synthesis of optimal one-step t-diagnosable graphs for a deterministic asymmetrical system-level diagnosis model // Проблеми телекомунікацій, Vol. 2013, Issue 3, 2013, pp. 53-60