On the size of identifying codes in binary hypercubes

In this paper, we consider identifying codes in binary Hamming spaces FnFn, i.e., in binary hypercubes. The concept of (r,⩽ℓ)(r,⩽ℓ)-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 us denote by Mr(⩽ℓ)(n) the smallest possible cardinality of an (r,⩽ℓ)(r,⩽ℓ)-identifying code in FnFn. In 2002, Honkala and Lobstein showed for ℓ=1ℓ=1 thatlimn→∞1nlog2Mr(⩽ℓ)(n)=1−h(ρ), where r=⌊ρn⌋r=⌊ρn⌋, ρ∈[0,1)ρ∈[0,1) and h(x)h(x) is the binary entropy function. In this paper, we prove that this result holds for any fixed ℓ⩾1ℓ⩾1 when ρ∈[0,1/2)ρ∈[0,1/2). We also show that Mr(⩽ℓ)(n)=O(n3/2) for every fixed ℓ and r   slightly less than n/2n/2, and give an explicit construction of small (r,⩽2)(r,⩽2)-identifying codes for r=⌊n/2⌋−1r=⌊n/2⌋−1.