Diagnosability of Butterfly Networks under the Comparison Approach

Toru ARAKI  Yukio SHIBATA  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E85-A   No.5   pp.1152-1160
Publication Date: 2002/05/01
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Graphs and Networks
Keyword: 
fault diagnosis,  comparison approach,  diagnosability,  butterfly network,  

Full Text: PDF>>
Buy this Article




Summary: 
We consider diagnosability of butterfly networks under the comparison approach proposed by Maeng and Malek. Sengupta and Dahbura discussed characterization of diagnosable systems under the comparison approach, and designed a polynomial time algorithm to identify the faulty processors. However, for a general system, it is not algorithmically easy to determine its diagnosability. This paper proposes two comparison schemes for generating syndromes on butterfly networks, and determine the diagnosability of the network.