Journal of Combinatorial Theory, Ser. A, Vol. 99, pp. 232-243, 2002.

Iiro HONKALA
Department of Mathematics
University of Turku
20014 Turku, Finland
e-mail: honkala@utu.fi

&

Antoine LOBSTEIN
Centre National de la Recherche Scientifique
Ecole Nationale Supérieure des Télécommunications
46 rue Barrault, 75634 Paris cédex 13, France
e-mail: lobstein@infres.enst.fr

Abstract.A binary code C included in {0,1}ⁿ is called r-identifying if the sets B_r(x) $\cap$ C, where B_r(x) is the set of all vectors within the Hamming distance r from x, are all nonempty and no two are the same. Denote by M_r(n) the minimum possible cardinality of a binary r-identifying code in {0,1}ⁿ. We prove that if s in [O,1) is a constant, then the limit when n goes to infinity of n^-1log₂M_[sn](n) is equal to 1-H(s), where H(x)=-xlog₂x -(1-x)log₂(1-x). We also prove that the problem whether or not a given binary linear code is r-identifying is $\Pi_2$-complete.

Revenir à la page d'accueil