Syndrome Decoding of Self-Diagnosis Models by a Tournament Matrix

Yoshiteru ISHIDA, Norihiko ADACHI, Hidekatsu TOKUMARU

Summary :

This paper presents a simple algorithm for diagnosis of a graph-theoretical, self-diagnosis model. The algorithm is based on a ranking method. That is, the algorithm uses the analogy between the rule used in the ranking method: the player who was hit more players directly or indirectly should be ranked lower and the rule used in diagnosis : the unit which is identified as faulty by more other units directly or indirectly should be more strongly suspected as faulty. With this algorithm, faulty units are identified from a given syndrome by simple calculation of a matrix. Although another algorithm is proposed whose complexity is less than the algorithm proposed here, this algorithm has the following two features :
(1) Simplicity :
The algorithm uses only the matrix multiplication and further, the matrix is directly obtainable from syndromes. Thus the algorithm can be implemented easily as a computer program.
(2) Universality :
This algorithm can be used not only for self-diagnosis model of PMC type, but for other types of self-diagnosis models including probabilistic model with slight modifications.
These features of the algorithm are investigated for the systems with design D_1t (t1, 2). The modification of the algorithm for the probabilistic self-diagnosis model is also discussed. The approach seems to open a channel between theoretical works of ranking theory in the field of graph theory and syndrome decoding of models in system diagnosis.

• Publication: IEICE TRANSACTIONS on transactions Vol.E69-E No.5 pp.659-665
• Publication Date: 1986/05/25
• Type of Manuscript: PAPER
• Category: Computer System

Authors

Yoshiteru ISHIDA
Norihiko ADACHI
Hidekatsu TOKUMARU

Keyword