On codes identifying sets of vertices in Hamming spaces
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.
- On the size of identifying codes in binary hypercubes
- On the complexity of the identification problem in Hamming spaces
- Cycles identifying vertices and edges in binary hypercubes and 2-dimensional tori
- Optimal codes for strong identification
- Families of optimal codes for strong identification
- Paths and cycles identifying vertices in twisted cubes
- On t-revealing codes in binary Hamming spaces
- Constructions of r-identifying codes and (r, l)-identifying codes
- Combinatorics of singly-repairable families
- Codes for strong identification
- Vertex identifying codes for the n-dimensional lattice
- On the covering of vertices for fault diagnosis in hypercubes
- Optimal identification of sets of edges using 2-factors
- scientific article; zbMATH DE number 2159641 (Why is no real title available?)
- scientific article; zbMATH DE number 1456824 (Why is no real title available?)
- Bounds on r-identifying codes in q-ary Lee space
- Extension of universal cycles for globally identifying colorings of cycles
- Links Between Discriminating and Identifying Codes in the Binary Hamming Space
- Identification in \(\mathbb Z^2\) using Euclidean balls
- On Iiro Honkala's contributions to identifying codes
- On identifying codes in binary Hamming spaces
- Various bounds for liar's domination number
- Constructing codes identifying sets of vertices
- New bounds on binary identifying codes
- Adaptive identification in graphs
- Improved bounds on identifying codes in binary Hamming spaces
This page was built for publication: On codes identifying sets of vertices in Hamming spaces
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5947251)
