Improved bounds on identifying codes in binary Hamming spaces (Q966138): Difference between revisions

Consider the set \(\mathbb{F}^n\) of binary vectors of length \(n\). Let \(X\) be a subset of \(\mathbb{F}^n\). The \textit{ball \(B_r(X)\) of radius \(r\) } around \(X\) is the set of all binary vectors of length \(n\) that are at Hamming distance at most \(r\) from at least one element of \(X\). A code \(C\subset \mathbb{F}^n\) is called \textit{\((r,\leq l)\)-identifying} if for all \(X,Y\subseteq \mathbb{F}^n\) such that \(|X|,|Y|\leq l\) and \(X\neq Y\), the sets \(B_r(X)\cap C\) and \(B_r(Y)\cap C\) are different. Identifying codes were first introduced by \textit{M. G. Karpovsky, K. Chakrabarty} and \textit{L. B. Levitin} [IEEE Trans. Inform. Theory 44 (2), 599--561 (1998; Zbl 1105.94342)]. They are used to find malfunctioning processors in multiprocessor systems, and they are also used in sensor networks. In both applications, the goal is to find identifying codes, as small as possible. This article improves lower bounds on \((r,\leq 1)\)-identifying codes for \(r>1\). Then, new lower bounds on \((r,\leq l)\)-identifying codes with \(l\geq 2\) are presented. Two methods constructing \((r,\leq l)\)-identifying codes from known other \((r,\leq l)\)-identifying codes also are given.