A1 Refereed original research article in a scientific journal
Upper bounds for binary identifying codes
Authors: Exoo G, Junnila V, Laihonen T, Ranto S
Publisher: ACADEMIC PRESS INC ELSEVIER SCIENCE
Publication year: 2009
Journal: Advances in Applied Mathematics
Journal name in source: ADVANCES IN APPLIED MATHEMATICS
Journal acronym: ADV APPL MATH
Volume: 42
Issue: 3
First page : 277
Last page: 289
Number of pages: 13
ISSN: 0196-8858
DOI: https://doi.org/10.1016/j.aam.2008.06.004
Abstract
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.
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.
UTU Research Portal