On codes identifying sets of vertices in Hamming spaces (Q5947251): Difference between revisions

Let \(C\subseteq \mathbb{F}^n_2\) be a binary code of length \(n\). If \(X\subseteq \mathbb{F}^n_2\), define \(I_t(X):= \{y\in C: d(x,y)\leq t\) for some \(x\in X\}\). For a collection \({\mathcal F}\) of subsets of \(\mathbb{F}^n_2\), the code \(C\) is said to be \((t,{\mathcal F})\)-identifying if for distinct \(X_1,X_2\in{\mathcal F}\), \(I_t(X_1)\neq I_t(X_2)\). The authors give the following helpful interpretation: \(2^n\) processors are located at the vertices of the \(n\)-dimensional hypercube, \([0, 1]^n\). A subset \(X\) of the processors are faulty. Each processor in the code \(C\) (here a processor is identified with the binary string of its coordinates) reports whether or not there are any faulty processors within Hamming distance \(t\) of the reporting processor. The information reported by the processors in code \(C\) (i.e., a processor reports `yes' if there are any faulty processors within distance \(t\) and `no' otherwise) is sufficient to identify the set \(X\) of faulty processors, assuming it is known that \(X\in{\mathcal F}\). The authors specialize their attention to the case \({\mathcal F}={\mathcal F}_{\leq l}:= \{X\subseteq \mathbb{F}^n_2:|X|\leq l\}\) (i.e., there are at most \(l\) faulty processors); and \({\mathcal F}={\mathcal F}_s:= \{X\subseteq \mathbb{F}^n_2:|X|= s\}\) (i.e., there are exactly \(s\) faulty processors). The authors are especially interested in lower bounds for the size of a code \(C\) identifying \({\mathcal F}_{\leq l}\) and \({\mathcal F}_s\). They give several such lower bounds. They also show, in some cases, that these lower bounds are sharp by constructing specific codes meeting the lower bounds.