×

Self-implicating structures for diagnosable systems. (English) Zbl 0566.94024

In this paper, a new class of diagnosable systems, called \(t_ p\)-self- implicating systems, which is a special case of the well-known \(t_ p\)- diagnosable systems introduced by F. P. Preparata, G. Metze and R. T. Chien [IEEE Trans. Electron. Comput. EC-16, 848-854 (1967; Zbl 0189.169)], is described. If there are no more than \(t_ p\) faulty units and the faults are assumed to be permanent, then the faulty units in a \(t_ p\)-self-implicating system can always be identified using at least one of two straightforward criteria associated with test outcomes. In each case, the given faulty unit in effect implicates itself as faulty. Necessary and sufficient conditions are given on the structures of PMC models for self-implication. Finally, an algorithm for identifying the set of faulty units in a \(t_ p\)-self-implicating system is given which is linear in the number of tests in the system, rendering it more efficient than the most efficient known algorithm for the general class of \(t_ p\)-diagnosable systems.

MSC:

94C15 Applications of graph theory to circuits and networks

Citations:

Zbl 0189.169
PDFBibTeX XMLCite
Full Text: DOI