Improved upper bounds on binary identifying codes

被引:8
作者
Exoo, Geoffrey [1 ]
Laihonen, Tero
Ranto, Sanna
机构
[1] Indiana State Univ, Dept Math & Comp Sci, Terre Haute, IN 47809 USA
[2] Univ Turku, Dept Math, FIN-20014 Turku, Finland
[3] Univ Turku, Turku Ctr Comp Sci, FIN-20014 Turku, Finland
基金
芬兰科学院;
关键词
binary Hamming space; covering codes; fault diagnosis; identifying codes; multiprocessor systems;
D O I
10.1109/TIT.2007.907434
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
In binary Hamming spaces, we construct new 1-identifying codes from 2-fold 1-coverings that are 1-identifying. We improve on previously known upper bounds for the cardinalities of I-identifying codes of many lengths when n >= 10. We construct t-identifying codes using the direct sum of t I-identifying codes. This solves partly an open problem posed by Blass, Honkala, and Litsyn in 2001. We also prove a general result concerning the direct sum of a t-identifying code with the whole space of any dimension.
引用
收藏
页码:4255 / 4260
页数:6
相关论文
共 20 条
  • [1] Blass U, 2000, J COMB DES, V8, P151, DOI 10.1002/(SICI)1520-6610(2000)8:2<151::AID-JCD8>3.0.CO
  • [2] 2-S
  • [3] Bounds on identifying codes
    Blass, U
    Honkala, I
    Litsyn, S
    [J]. DISCRETE MATHEMATICS, 2001, 241 (1-3) : 119 - 128
  • [4] Charon I, 2007, ELECTRON J COMB, V14
  • [5] Cohen G, 1997, COVERING CODES
  • [6] FURTHER RESULTS ON THE COVERING RADIUS OF CODES
    COHEN, GD
    LOBSTEIN, AC
    SLOANE, NJA
    [J]. IEEE TRANSACTIONS ON INFORMATION THEORY, 1986, 32 (05) : 680 - 694
  • [7] EXOO G, COMPUTATIONAL RESULT
  • [8] EXOO G, IN PRESS DISCR APPL
  • [9] Codes identifying sets of vertices in random networks
    Frieze, Alan
    Martin, Ryan
    Moncel, Julien
    Ruszinko, Miklos
    Smyth, Cliff
    [J]. DISCRETE MATHEMATICS, 2007, 307 (9-10) : 1094 - 1107
  • [10] On robust and dynamic identifying codes
    Honkala, I
    Karpovsky, MG
    Levitin, LB
    [J]. IEEE TRANSACTIONS ON INFORMATION THEORY, 2006, 52 (02) : 599 - 612