On Detecting Multiple Faults in Baseline Interconnection Networks

Shun Shii Lin, Shan Tai Chen

Research output: Contribution to journalArticle

2 Citations (Scopus)

Abstract

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 (2 log2 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 2log2 N tests.

Original languageEnglish
Pages (from-to)254-269
Number of pages16
JournalComputer Journal
Volume41
Issue number4
DOIs
Publication statusPublished - 1998 Jan 1

ASJC Scopus subject areas

  • Computer Science(all)

Cite this