uu.seUppsala University Publications
Change search
ReferencesLink to record
Permanent link

Direct link
On the size of identifying codes in binary hypercubes
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Analysis and Applied Mathematics.
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
Abstract [en]

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.
Keyword [en]
Identifying code, Optimal rate, Hypercube, Fault diagnosis
National Category
URN: urn:nbn:se:uu:diva-114387DOI: 10.1016/j.jcta.2009.02.004ISI: 000266210400009OAI: oai:DiVA.org:uu-114387DiVA: diva2:293872
Available from: 2010-02-15 Created: 2010-02-15 Last updated: 2010-07-28Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Janson, Svante
By organisation
Analysis and Applied Mathematics
In the same journal
Journal of combinatorial theory. Series A (Print)

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 198 hits
ReferencesLink to record
Permanent link

Direct link