A1 Refereed original research article in a scientific journal

New bounds on binary identifying codes




AuthorsExoo G, Laihonen T, Ranto S

PublisherELSEVIER SCIENCE BV

Publication year2008

JournalDiscrete Applied Mathematics

Journal name in sourceDISCRETE APPLIED MATHEMATICS

Journal acronymDISCRETE APPL MATH

Volume156

Issue12

First page 2250

Last page2263

Number of pages14

ISSN0166-218X

DOIhttps://doi.org/10.1016/j.dam.2007.09.017


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 M-1 (6) = 19. It is also shown, using a non-constructive approach, that there exist asymptotically good (r, <= l)-identifying codes for fixed l >= 2. In order to construct (r, <= l)-identifying codes, we prove that a direct sum of r codes that are (l, <= l)-identifying is an (r, <= l)-identifying code for l >= 2. (C) 2007 Elsevier B.V. All rights reserved.




Last updated on 2024-26-11 at 21:46