This paper introduces an efficient diagnosis algorithm for regular structures (EDARS). The algorithm provides a diagnosis which is correct, but possibly incomplete, if the cardinality of the actual fault set is below a “syndrome-dependent bound” asserted by the algorithm itself. The time complexity of EDARS is O(nt) when executed on t-regular structures of size n. The correctness and the completeness degree of EDARS were evaluated by means of simulation. Grids, hypercubes and cube-connected cycle (CCC) structures were considered. Simulation results with grid structures showed a strong influence of structure degree over diagnosis performance. Furthermore, comparisons of simulation results obtained with hypercubes, CCCs and grids of the same size and degree showed that diameter and bisection width also appear to influence the performance of EDARS, particularly with respect to diagnosis completeness.

Diagnosis of Regular Structures

A. CARUSO
Primo
Software
;
2000-01-01

Abstract

This paper introduces an efficient diagnosis algorithm for regular structures (EDARS). The algorithm provides a diagnosis which is correct, but possibly incomplete, if the cardinality of the actual fault set is below a “syndrome-dependent bound” asserted by the algorithm itself. The time complexity of EDARS is O(nt) when executed on t-regular structures of size n. The correctness and the completeness degree of EDARS were evaluated by means of simulation. Grids, hypercubes and cube-connected cycle (CCC) structures were considered. Simulation results with grid structures showed a strong influence of structure degree over diagnosis performance. Furthermore, comparisons of simulation results obtained with hypercubes, CCCs and grids of the same size and degree showed that diameter and bisection width also appear to influence the performance of EDARS, particularly with respect to diagnosis completeness.
File in questo prodotto:
File Dimensione Formato  
00857538.pdf

solo utenti autorizzati

Tipologia: Versione editoriale
Licenza: NON PUBBLICO - Accesso privato/ristretto
Dimensione 562.64 kB
Formato Adobe PDF
562.64 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11587/117163
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 8
  • ???jsp.display-item.citation.isi??? 8
social impact