Fault-Diagnosis for a Class of Multistage Interconnection Networks

Abstract

To study the fault-diagnosis method for a class of multistage interconnection networks a general fault model is first constructed. Specific steps for diagnosing single faults and detecting multiple faults in interconnection networks such as the indirect binary n-cube network and the flip network are then developed. The following results are derived in this study: 1) independent of the network size, only four tests are required for detecting a single fault; 2) the number of tests required for locating a single fault and determining the fault type ranges from 4 to max(12, 6 + 2 ⌈log2(log2N)⌉) except for four types of single faults in the switching elements which cannot be pinpointed at the switching element level where N is the number of inputs/outputs; 3) only four tests are required for locating a single fault if the switching element is designed in such a way that any physical defection of the switching element causes both outputs of the related switching element to be faulty; and 4) multiple faults can be detected by 2(1 + log2N) tests.