© 1998 by British Computer Society
On Detecting Multiple Faults in Baseline Interconnection Networks
1 National Taiwan Normal University, Taipei, Taiwan, ROC Email: linss{at}ice.ntnu.edu.tw, 2 Chung Cheng Institute of Technology, Tao-Yuan, Taiwan, ROC
This paper presents detection algorithms for baseline interconnection networks in the presence of multiple faults. We develop a procedure for finding the constraints of test vectors. This reduces the number of distinct test vectors and solves the problems efficiently. Furthermore, we design a new and systematic procedure for generating admissible permutations and reduction rules to find constraints easier. By using this novel approach, we are able to derive the following new results. (1) Four distinct test vectors are necessary and sufficient for detecting multiple faults in an 8*8 baseline network. (2) Six distinct test vectors are sufficient for detecting multiple faults in a 16 * 16 baseline network. (3) Six tests are necessary and sufficient for detecting multiple faults in a 16 * 16 baseline network. This improves the previous result of [1], which needs 8 tests to accomplish the same task. (4) We show that (2log2 N) – 2 tests are sufficient for detecting multiple faults in an N * N baseline network for N 
16. This also improves the result of [1], which needs 2 log2 N tests.
Received January 21, 1997. revised June 23, 1998.