Upper bounds for binary identifying codes

A nonempty set of words in a binary Hamming space F-n is called an r-identifying code if for every word the set of codewords within distance r from it is unique and nonempty. The smallest possible cardinality of an r-identifying code is denoted by M-r(n). In this paper, we consider questions closely related to the open problem whether Mt+r(n + m) <= M-t(m)M-r(n) is true. For example, we show results like M1+r(n + m) <= 4M(1)(m)M-r(n), which improve previously known bounds. We also consider codes which identify sets of words of size at most l. The smallest cardinality of such a code is denoted by M-r((<= l)) (n). we prove that M-r+1((<= l)) (n + m) <= M-r((<= l)) (n)M-t((<= l)) (m) is true for all l >= r + 3 when r >= 1 and t = 1. We also obtain a result M-1 (n + 1) <= (2 + epsilon(n))M-1(n) where epsilon(n) -> 0 when n -> infinity. This bound is related to the conjecture M-1 (n + 1) <= 2M(1) (n). Moreover. we give constructions for the best known 1-identifying codes of certain lengths. (C) 2008 Elsevier Inc. All rights reserved.