A connection assignment yielding easily diagnosable systems

The problem of determining nearly optimal connection assignments in functional distributed systems which are sequentially diagnosable in the model of Preparata is reconsidered. A class of diagnostic graphs yelding any permissible value of sequential diagnosability is introduced and it is shown that the number of diagnostic connections of systems in this class reaches the lower bound whenever this bound is known. Although syndrome decoding in diagnosis is a NP-complete problem, it is proved that efficient diagnostic procedures exist for system in the class under consideration. A syndrome decoding algorithm is presented.