Optimal codes for strong identification

Combinatorial aspects of packing and covering (05B40) Reliability, testing and fault tolerance of networks and computer systems (68M15) Other types of codes (94B60) Fault detection; testing in circuits and networks (94C12)

Review text

Codes for identification (introduced in [\textit{M. G. Karpovsky, K. Chakrabarty} and \textit{L. B. Levitin}, On a new class of codes for identifying vertices in graphs, IEEE Trans. Inf. Theory 44, 599-611 (1998; Zbl 1105.94342)]) locate faulty processors in a multi-processor system. The idea is as follows. Let \(n\) processors be labelled with binary vectors of length \(n.\) A processor is able to check the processors whose label differs in at most \(t\) positions from its own. It reports a `1' to a central controller if something is wrong in this neighbourhood, and a `0' otherwise. The aim is to find a (small !) code \(C \subset \{0,1\}^n\) such that the reports from the processors from \(C\) allows localisation of the faulty processors if at most \(l\) processors are simultaneously malfunctioning. For a strongly \((t,\leq l)\) identifying code, we require more: it should also allow localisation of the faulty processors if these can give incorrect reports. The author presents, for each \(l\geq 3,\) infinite sequences of strongly \((1,\leq l)\) identifying codes of minimum cardinality.

Recommendations

Cites work

Cited in

(16)

This page was built for publication: Optimal codes for strong identification

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1612759)