Probabilistic syndrome decoding in self diagnosable digital systems

Self-diagnosis of multi-unit digital system is reconsidered following hypotheses: 1) Faults are not equal probable. Each unit of a system has associated its own probability of failure. Unit malfunctions are assumed to be statistically independent. 2) The outcomes of tests perforned between units are not deterministic. They are characterized by their conditional probability for any possible status of testing and tested unit. Attemption is restricted to the case where test results are independent of one another. Given a set of test results, the problem of finding the most likely set of faulty units (probabilistic one-step diagnosability) is considered here. Moreover an approach to probabilistic diagnosability with repair is presented. It is shown that there exists a significant class of systems for which this problem is easily solved and a decoding procedure is given whose complexity is O(n) where n is the number of system units.