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

Shun Shii Lin, Ferng Ching Lin

Research output: Contribution to journalArticle

1 Citation (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)205-217
Number of pages13
JournalJournal of the Chinese Institute of Engineers, Transactions of the Chinese Institute of Engineers,Series A/Chung-kuo Kung Ch'eng Hsuch K'an
Volume19
Issue number2
DOIs
Publication statusPublished - 1996 Jan 1
Externally publishedYes

Fingerprint

Fault detection

Keywords

  • Multiple-fault detection
  • Multistage interconnection network
  • Parallel processing

ASJC Scopus subject areas

  • Engineering(all)

Cite this

@article{d340915887ec4b948d5530deb7ad03f4,
title = "Multiple-fault detection of multistage interconnection networks with two and four valid states",
abstract = "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.",
keywords = "Multiple-fault detection, Multistage interconnection network, Parallel processing",
author = "Lin, {Shun Shii} and Lin, {Ferng Ching}",
year = "1996",
month = "1",
day = "1",
doi = "10.1080/02533839.1996.9677780",
language = "English",
volume = "19",
pages = "205--217",
journal = "Chung-kuo Kung Ch'eng Hsueh K'an/Journal of the Chinese Institute of Engineers",
issn = "0253-3839",
publisher = "Chinese Institute of Engineers",
number = "2",

}

TY - JOUR

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

AU - Lin, Shun Shii

AU - Lin, Ferng Ching

PY - 1996/1/1

Y1 - 1996/1/1

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 -