Lecture Notes in Computer Science, Vol. 4851, pp. 267-270, 2007.
Irène CHARON, Gérard COHEN, Olivier HUDRY & 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
{charon, cohen, hudry, lobstein}@enst.fr
Abstract. Let Fn be the binary n-cube, or binary Hamming space of dimension n, endowed with the Hamming distance, and En (respectively, On) the set of vectors with even (respectively, odd) weight. For r a nonnegative integer and x in Fn, we denote by Br(x) the ball of radius r and centre x. A code C included in Fn is said to be r-identifying if the sets Br(x) $\cap$ C, x in Fn, are all nonempty and distinct. A code C included in En is said to be r-discriminating if the sets Br(x) $\cap$ C, x in On, are all nonempty and distinct. We show that the two definitions, which were given for general graphs, are equivalent in the case of the Hamming space, in the following sense: for any odd r, there is a bijection between the set of r-identifying codes in Fn and the set of r-discriminating codes in Fn+1.