On the size of identifying codes in binary hypercubes

Abstract: We consider identifying codes in binary Hamming spaces F^n, i.e., in binary hypercubes. The concept of identifying codes was introduced by Karpovsky, Chakrabarty and Levitin in 1998. Currently, the subject forms a topic of its own with several possible applications, for example, to sensor networks. Let C be a subset of F^n. For any subset X of F^n, denote by I_r(X)=I_r(C;X) the set of elements of C within distance r from at least one x in X. Now C is called an (r,<= l)-identifying code if the sets I_r(X) are distinct for all subsets X of size at most l. We estimate the smallest size of such codes with fixed l and r/n converging to some number rho in (0,1). We further show the existence of such a code of size O(n^{3/2}) for every fixed l and r slightly less than n/2, and give for l=2 an explicit construction of small such codes for r the integer part of n/2-1 (the largest possible value).

Review text

A binary Hamming space of dimension \(n\) is denoted by \(\mathbb{F}^n\). For a code \(C \subseteq \mathbb{F}^n\) and a set \(X \subseteq \mathbb{F}^n\), the codeword \(r\)-neighborhood of \(X\) is \(I_r(C;X) := B_r(X) \cap C\), where \(B_r(X)\) is the union of the balls of radius \(r\) centered at the elements of \(X\). A code is said to be \((r,\leq \ell)\)-identifying if for all \(X,Y \subseteq \mathbb{F}^n\) such that \(|X| \leq \ell\), \(|Y| \leq \ell\), and \(X \neq Y\) we have \(I_r(C;X) \neq I_r(C;Y)\). \textit{I. Honkala} and \textit{A. Lobstein} [J. Comb. Theory, Ser. A 99, No. 2, 232--243 (2002; Zbl 1005.94030)] determined the asymptotic behaviour of the smallest possible cardinality of \((r,\leq \ell)\)-identifying codes, for \(\ell = 1\) and \(r = \lfloor {\rho}n \rfloor\), \(\rho < 1\). The current work extends this result to any fixed \(\ell\) and \(\rho < 1/2\). Other results obtained include a construction of small \((r,\leq 2)\)-identifying codes for \(r = \lfloor n/2 \rfloor - 1\).

Recommendations

Cites work

Cited in

(22)

This page was built for publication: On the size of identifying codes in binary hypercubes

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