System-level self-diagnosis in sparsely interconnected systems

A probabilistic diagnosis algorithm for identifying faulty units in sparsely interconnected systems is presented. The algorithm is partially based on a comparison approach where identical test vectors are applied to all units and their outputs are intracompared. The comparison diagnosis schemes based on majority-voting or voting-with-threshold-of-1 are inappropriate for diagnosing those systems implemented on a single chip or wafer. Unlike other schemes, the authors' scheme adjusts algorithm parameters depending on unit yield, degree of connectivity, and the probability of common-cause failures. Fault coverage is further improved by disseminating test results to neighbors. The fault coverage of the diagnosis algorithm is remarkably high, and diagnosis decisions are made in a distributed manner. The algorithm is quite general in that it can be applied to arbitrarily connected systems