Multiple-fault detection of multistage interconnection networks with two and four valid states

In this paper, we study the multiple-fault detection methods for a class of multistage interconnection networks using the totally exhaustive combinatorial model [8, 9, 11] with multiple-fault assumption. We find that six tests are sufficient and necessary for detecting multiple faults of the 4*4 and 8*8 baseline networks with two valid states plus that the number of tests is double as the network size doubled. We show that multiple faults can be detected by 2log₂N tests in an N*N baseline network with two valid states, N ≥ 8. This improves upon the previous results of [8] which need 2log₂N + 2 tests to accomplish the same task. We also prove that, if K distinct vectors are sufficient for diagnosing an R*R baseline network with two valid states, then 2[log₂(N*K/R+2)] tests are sufficient for diagnosing an N*N baseline network with two valid states for N ≥ R. To detect the multiple faults of an N*N reverse baseline network with four valid states, we have developed a new and systematic procedure in which multiple faults can be detected by (4log₂N + 2) tests, N ≥ 8. This is also more efficient than the results of [9] which need (6log₂N + 2) tests.