Upper bounds for binary identifying codes

: Exoo G, Junnila V, Laihonen T, Ranto S

Publisher: ACADEMIC PRESS INC ELSEVIER SCIENCE

: 2009

: Advances in Applied Mathematics

: ADVANCES IN APPLIED MATHEMATICS

: ADV APPL MATH

: 42

: 3

: 277

: 289

: 13

: 0196-8858

DOI: https://doi.org/10.1016/j.aam.2008.06.004

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 M(t+r)(n + m) <= M(t)(m)M(r)(n) is true. For example, we show results like M(1+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.