Paper Info
Title
Improved bounds on identifying codes in binary Hamming spaces
Abstract
Let @?, n and r be positive integers. Define F^n={0,1}^n. The Hamming distance between words x and y of F^n is denoted by d(x,y). The ball of radius r is defined as B"r(X)={y@?F^n|@?x@?X:d(x,y)@?r}, where X is a subset of F^n. A code C@?F^n is called (r,@?@?)-identifying if for all X,Y@?F^n such that |X|@?@?, |Y|@?@? and XY, the sets B"r(X)@?C and B"r(Y)@?C are different. The concept of identifying codes was introduced by Karpovsky, Chakrabarty and Levitin in 1998. In this paper, we present various results concerning (r,@?@?)-identifying codes in the Hamming space F^n. First we concentrate on improving the lower bounds on (r,@?1)-identifying codes for r1. Then we proceed by introducing new lower bounds on (r,@?@?)-identifying codes with @?=2. We also prove that (r,@?@?)-identifying codes can be constructed from known ones using a suitable direct sum when @?=2. Constructions for (r,@?2)-identifying codes with the best known cardinalities are also given.
Year
DOI
Venue
2010
10.1016/j.ejc.2009.09.002
Eur. J. Comb.
Keywords
Field
DocType
radius r,positive integer,code c,hamming space f,suitable direct sum,hamming distance,binary hamming space,improved bound,known cardinalities,new lower bound,lower bound,define f
Integer,Discrete mathematics,Hamming code,Combinatorics,Direct sum,Cardinality,Hamming distance,Hamming space,Code (cryptography),Mathematics,Binary number
Journal
Volume
Issue
ISSN
31
3
0195-6698
Citations 
PageRank 
References 
8
0.55
15
Authors
4
Name
Order
Citations
PageRank
Geoffrey Exoo118739.86
Ville Junnila24310.51
Tero Laihonen336339.39
Sanna M. Ranto415713.49