A Fault Identification Algorithm for t_i-Diagnosable Systems

Abstract

In this paper, a new approach to identifying faulty units in t <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i</inf> -diagnosable systems is described. This approach exploits special properties of the highly structured t <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i</inf> -diagnosable systems to produce a faulty unit identification algorithm which is shown to be of time complexity O(|E|) where |E| corresponds to the number of tests in the system. The diagnosis quality of the algorithm is as follows: 1) if the algorithm identifies a unit as faulty, it is always correct; 2) if the collection of test outcomes takes on a form that is compatible with a permanent fault situation, the algorithm identifies all of the corresponding faulty units; and 3) the algorithm identifies at least one faulty unit over collections of test outcomes significantly larger than those that are compatible with permanent fault situations.