On the size of identifying codes in binary hypercubes
2009 (English)In: Journal of combinatorial theory. Series A (Print), ISSN 0097-3165, E-ISSN 1096-0899, Vol. 116, no 5, 1087-1096 p.Article in journal (Refereed) Published
In this paper, we consider identifying codes in binary Hamming spaces F-n, i.e., in binary hypercubes. The concept of (r, <= l)-identifying codes was introduced by Karpovsky, Chakrabarty and Levitin in 1998. Currently, the subject forms a topic of its own with several possible applications, for example, to sensor networks. Let us denote by M-r((<= l)) (n) the smallest possible cardinality of an (r, <= l)-identifying code in F-n. In 2002, Honkala and Lobstein showed for l = 1 that lim(n ->infinity)1/nlog(2)M(r)((<= l))(n) = 1 - h(rho), where r = left perpendicular rho nright perpendicular, rho epsilon [0, 1) and h(x) is the binary entropy function. In this paper, we prove that this result holds for any fixed l >= 1 when rho epsilon [0, 1/2). We also show that M-r((<= l))(n) = O(n(3/2)) for every fixed l and r slightly less than n/2, and give an explicit construction of small (r, <= 2)-identifying codes for r = left perpendicularn/2right perpendicular - 1.
Place, publisher, year, edition, pages
2009. Vol. 116, no 5, 1087-1096 p.
Identifying code, Optimal rate, Hypercube, Fault diagnosis
IdentifiersURN: urn:nbn:se:uu:diva-114387DOI: 10.1016/j.jcta.2009.02.004ISI: 000266210400009OAI: oai:DiVA.org:uu-114387DiVA: diva2:293872