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 2log2N tests in an N*N baseline network with two valid states, N ≥ 8. This improves upon the previous results of  which need 2log2N + 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[log2(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 (4log2N + 2) tests, N ≥ 8. This is also more efficient than the results of  which need (6log2N + 2) tests.
|Number of pages||13|
|Journal||Journal of the Chinese Institute of Engineers, Transactions of the Chinese Institute of Engineers,Series A/Chung-kuo Kung Ch'eng Hsuch K'an|
|Publication status||Published - 1996|
- Multiple-fault detection
- Multistage interconnection network
- Parallel processing
ASJC Scopus subject areas