• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

New Bounds on Binary Identifying Codes

Geoffrey Exoo, Tero Laihonen, Sanna Ranto, New Bounds on Binary Identifying Codes. Discrete Applied Mathematics 156(12), 2250–2263, 2008.

Abstract:

The original motivation for identifying codes comes from fault diagnosis in multiprocessor systems. Currently, the subject forms a topic of its own with several possible applications, for example, to sensor networks.

In this paper, we concentrate on identification in binary Hamming spaces. We give a new lower bound on the cardinality of r-identifying codes when r≥2. Moreover, by a computational method, we show that M1(6)=19. It is also shown, using a non-constructive approach, that there exist asymptotically good (r,≤ℓ)-identifying codes for fixed ℓ≥2. In order to construct (r,≤ℓ)-identifying codes, we prove that a direct sum of r codes that are (1,≤ℓ)-identifying is an (r,≤ℓ)-identifying code for ℓ≥2.

BibTeX entry:

@ARTICLE{jExLaRa08a,
  title = {New Bounds on Binary Identifying Codes},
  author = {Exoo, Geoffrey and Laihonen, Tero and Ranto, Sanna},
  journal = {Discrete Applied Mathematics},
  volume = {156},
  number = {12},
  publisher = {Elsevier},
  pages = {2250–2263},
  year = {2008},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Publication Forum rating of this publication: level 2

Edit publication