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

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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
Mathematics
Identifiers
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: 2017-12-12Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Authority records BETA

Janson, Svante

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)
Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 443 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf