Optimal codes for strong identification (Q1612759): Difference between revisions

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.