TY - JOUR

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

AU - Lin, Shun Shii

AU - Lin, Ferng Ching

N1 - Funding Information:
This work was supported in part by National Science Council of the Republic of China under Contract NSC 81-0408-E-003-503.

PY - 1996

Y1 - 1996

N2 - 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 [8] 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 [9] which need (6log2N + 2) tests.

AB - 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 [8] 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 [9] which need (6log2N + 2) tests.

KW - Multiple-fault detection

KW - Multistage interconnection network

KW - Parallel processing

UR - http://www.scopus.com/inward/record.url?scp=0030102345&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0030102345&partnerID=8YFLogxK

U2 - 10.1080/02533839.1996.9677780

DO - 10.1080/02533839.1996.9677780

M3 - Article

AN - SCOPUS:0030102345

VL - 19

SP - 205

EP - 217

JO - Chung-kuo Kung Ch'eng Hsueh K'an/Journal of the Chinese Institute of Engineers

JF - Chung-kuo Kung Ch'eng Hsueh K'an/Journal of the Chinese Institute of Engineers

SN - 0253-3839

IS - 2

ER -