Discriminating and Identifying Codes in the Binary Hamming Space

Details Discriminating and Identifying Codes in the Binary Hamming Space Discriminating and Identifying Codes in the Binary Hamming Space

2007-03-14

arxiv.org/abs/cs/0703066v1

Computer Science

Discrete Mathematics

Scientific paper

Let $F^n$ be the binary $n$-cube, or binary Hamming space of dimension $n$, endowed with the Hamming distance, and ${\cal E}^n$ (respectively, ${\cal O}^n$) the set of vectors with even (respectively, odd) weight. For $r\geq 1$ and $x\in F^n$, we denote by $B_r(x)$ the ball of radius $r$ and centre $x$. A code $C\subseteq F^n$ is said to be $r$-identifying if the sets $B_r(x) \cap C$, $x\in F^n$, are all nonempty and distinct. A code $C\subseteq {\cal E}^n$ is said to be $r$-discriminating if the sets $B_r(x) \cap C$, $x\in {\cal O}^n$, are all nonempty and distinct. We show that the two definitions, which were given for general graphs, are equivalent in the case of the Hamming space, in the following sense: for any odd $r$, there is a bijection between the set of $r$-identifying codes in $F^n$ and the set of $r$-discriminating codes in $F^{n+1}$. We then extend previous studies on constructive upper bounds for the minimum cardinalities of identifying codes in the Hamming space.

Affiliated with

Also associated with

No associations

Rating

Discriminating and Identifying Codes in the Binary Hamming Space does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Discriminating and Identifying Codes in the Binary Hamming Space, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Discriminating and Identifying Codes in the Binary Hamming Space will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-715737