Improved bounds on identifying codes in binary Hamming spaces

Let ℓℓ, nn and rr be positive integers. Define Fn={0,1}nFn={0,1}n. The Hamming distance between words x and y of FnFn is denoted by d(x,y). The ball of radius rr is defined as Br(X)={y∈Fn∣∃x∈X:d(x,y)≤r}, where XX is a subset of FnFn. A code C⊆FnC⊆Fn is called (r,≤ℓ)(r,≤ℓ)-identifying if for all X,Y⊆FnX,Y⊆Fn such that |X|≤ℓ|X|≤ℓ, |Y|≤ℓ|Y|≤ℓ and X≠YX≠Y, the sets Br(X)∩CBr(X)∩C and Br(Y)∩CBr(Y)∩C are different. The concept of identifying codes was introduced by Karpovsky, Chakrabarty and Levitin in 1998.In this paper, we present various results concerning (r,≤ℓ)(r,≤ℓ)-identifying codes in the Hamming space FnFn. First we concentrate on improving the lower bounds on (r,≤1)(r,≤1)-identifying codes for r>1r>1. Then we proceed by introducing new lower bounds on (r,≤ℓ)(r,≤ℓ)-identifying codes with ℓ≥2ℓ≥2. We also prove that (r,≤ℓ)(r,≤ℓ)-identifying codes can be constructed from known ones using a suitable direct sum when ℓ≥2ℓ≥2. Constructions for (r,≤2)(r,≤2)-identifying codes with the best known cardinalities are also given.