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

Keywords

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

ASJC Scopus subject areas

  • Engineering(all)

Cite this