A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
On identifying codes in binary Hamming spaces
Tekijät: Honkala I, Lobstein A
Kustantaja: ACADEMIC PRESS INC ELSEVIER SCIENCE
Julkaisuvuosi: 2002
Journal: Journal of Combinatorial Theory, Series A
Tietokannassa oleva lehden nimi: JOURNAL OF COMBINATORIAL THEORY SERIES A
Lehden akronyymi: J COMB THEORY A
Vuosikerta: 99
Numero: 2
Aloitussivu: 232
Lopetussivu: 243
Sivujen määrä: 12
ISSN: 0097-3165
DOI: https://doi.org/10.1006/jcta.2002.3263
Tiivistelmä
A binary code C subset of or equal to {0, 1}(n) is called r-identifying, if the sets B-r(x) boolean AND C, where B-r(x) is the set of all vectors within the Hamming distance r from x, are all nonempty and no two are the same. Denote by M-r(n) the minimum possible cardinality of a binary r-identifying code in {0, 1)(n). We prove that if rho is an element of [0, 1) is a constant, then lim(n-->infinity) n(-1) log(2) M-[rhon](n) = 1 - H(rho), where H(x) = -x log(2)x - (1 - x) log(2)(1 - x). We also prove that the problem whether or not a given binary linear code is lr-identifying is Pi(2)-complete. (C) 2002 Elsevier Science (USA).
A binary code C subset of or equal to {0, 1}(n) is called r-identifying, if the sets B-r(x) boolean AND C, where B-r(x) is the set of all vectors within the Hamming distance r from x, are all nonempty and no two are the same. Denote by M-r(n) the minimum possible cardinality of a binary r-identifying code in {0, 1)(n). We prove that if rho is an element of [0, 1) is a constant, then lim(n-->infinity) n(-1) log(2) M-[rhon](n) = 1 - H(rho), where H(x) = -x log(2)x - (1 - x) log(2)(1 - x). We also prove that the problem whether or not a given binary linear code is lr-identifying is Pi(2)-complete. (C) 2002 Elsevier Science (USA).
Turun yliopiston Tutkimustietojärjestelmän portaali