An optimal result for codes identifying sets of words

In this paper, we consider identifying codes in binary Hamming spaces Fⁿ. The concept of identifying codes was introduced by Karpovsky, Chakrabarty and Levitin. Currently, the subject forms a topic of its own with several possible applications, for example, to sensor networks. Let a code C ¿ Fⁿ. For any set of words X ¿ Fⁿ, denote by I_r(X) = I_r(C; X) the set of codewords within distance r from at least one x ¿ X. Now a code C ¿ Fⁿ is called (r, ¿ ¿)-identifying if the sets I_r(X) are distinct for all X ¿ Fⁿ of size at most ¿. Let us denote by M_r ^(¿¿) (n) the smallest possible cardinality of an (r, ¿ ¿)-identifying code. In 2002, Honkala and Lobstein showed for ¿ = 1 that lim_n¿¿ 1/n log₂ M_r ^(¿¿) (n) = 1 - h(¿) where r = [¿n], ¿ ¿ (0, 1) and h(x) is the binary entropy function. In this paper, we prove that this result holds for any fixed ¿ ¿ 1 when ¿ ¿ (0, 1/2). We also show that M_r ^(¿¿) (n) = O(n^3/2) for every fixed ¿ and r slightly less than n/2, and give an explicit construction of small (r, ¿ 2)-identifying codes for r = [n/2] - 1.