Discriminating and Identifying Codes in the Binary Hamming Space
| dc.creator | Cohen, Charon | |
| dc.creator | Lobstein, Hudry | |
| dc.date | 2007-03-14 | |
| dc.date.accessioned | 2026-07-07T07:51:50Z | |
| dc.date.available | 2026-07-07T07:51:50Z | |
| dc.description | 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. | |
| dc.identifier | https://arxiv.org/abs/cs/0703066 | |
| dc.identifier | http://arxiv.org/abs/cs/0703066 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/125660 | |
| dc.subject | Discrete Mathematics | |
| dc.title | Discriminating and Identifying Codes in the Binary Hamming Space | |
| dc.type | text |