New bounds on binary identifying codes
详细信息 查看全文
- 作者：Geoffrey Exoo ; Tero Laihonen ; Sanna Ranto
- 关键词：Identifying code ; Hamming space ; Lower bound ; Asymptotic behaviour ; Direct sum
- 刊名：Discrete Applied Mathematics
- 出版年：2008
- 出版时间：28 June 2008
- 年：2008
- 卷：156
- 期：12
- 页码：2250-2263
- 全文大小：368 K
文摘
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.