Links between discriminating and identifying codes in the binary hamming space

Irène Charon; Gérard Cohen; Olivier Hudry; Antoine Lobstein

doi:10.1007/978-3-540-77224-8_31

Links between discriminating and identifying codes in the binary hamming space

Irène Charon
, Gérard Cohen
, Olivier Hudry
, Antoine Lobstein

Centre national de la recherche scientifique

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

Let Fⁿ be the binary n-cube, or binary Hamming space of dimension n, endowed with the Hamming distance, and εⁿ (respectively, οⁿ) the set of vectors with even (respectively, odd) weight. For r ≥ 1 and x ∈ Fⁿ, we denote by B_r(x) the ball of radius r and centre x. A code C ⊆ F ⁿ is said to be r-identifying if the sets B_r(x) ∩ C, x ∈ Fⁿ, are all nonempty and distinct. A code C ⊆ εⁿ is said to be r-discriminating if the sets B _r(x)∩C, x ∈ οⁿ, 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 ⁿ and the set of r-discriminating codes in Fⁿ⁺¹.

Original language	English
Title of host publication	Applied Algebra, Algebraic Algorithms and Error-Correcting Codes - 17th International Symposium, AAECC- 17, Proceedings
Publisher	Springer Verlag
Pages	267-270
Number of pages	4
ISBN (Print)	9783540772231
DOIs	https://doi.org/10.1007/978-3-540-77224-8_31
Publication status	Published - 1 Jan 2007
Event	17th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC-17 - Bangalore, India Duration: 16 Dec 2007 → 20 Dec 2007

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	4851 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	17th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC-17
Country/Territory	India
City	Bangalore
Period	16/12/07 → 20/12/07

Keywords

Coding theory
Discriminating codes
Graph theory
Hamming space
Hypercube
Identifying codes

Access to Document

10.1007/978-3-540-77224-8_31

Cite this

Charon, I., Cohen, G., Hudry, O., & Lobstein, A. (2007). Links between discriminating and identifying codes in the binary hamming space. In Applied Algebra, Algebraic Algorithms and Error-Correcting Codes - 17th International Symposium, AAECC- 17, Proceedings (pp. 267-270). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4851 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-540-77224-8_31

Charon, Irène ; Cohen, Gérard ; Hudry, Olivier et al. / Links between discriminating and identifying codes in the binary hamming space. Applied Algebra, Algebraic Algorithms and Error-Correcting Codes - 17th International Symposium, AAECC- 17, Proceedings. Springer Verlag, 2007. pp. 267-270 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{25832a54ecca40698e373b03d8ad3968,

title = "Links between discriminating and identifying codes in the binary hamming space",

abstract = "Let Fn be the binary n-cube, or binary Hamming space of dimension n, endowed with the Hamming distance, and εn (respectively, οn) the set of vectors with even (respectively, odd) weight. For r ≥ 1 and x ∈ Fn, we denote by Br(x) the ball of radius r and centre x. A code C ⊆ F n is said to be r-identifying if the sets Br(x) ∩ C, x ∈ Fn, are all nonempty and distinct. A code C ⊆ εn is said to be r-discriminating if the sets B r(x)∩C, x ∈ ο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 Fn+1.",

keywords = "Coding theory, Discriminating codes, Graph theory, Hamming space, Hypercube, Identifying codes",

author = "Ir{\`e}ne Charon and G{\'e}rard Cohen and Olivier Hudry and Antoine Lobstein",

year = "2007",

month = jan,

day = "1",

doi = "10.1007/978-3-540-77224-8\_31",

language = "English",

isbn = "9783540772231",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "267--270",

booktitle = "Applied Algebra, Algebraic Algorithms and Error-Correcting Codes - 17th International Symposium, AAECC- 17, Proceedings",

note = "17th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC-17 ; Conference date: 16-12-2007 Through 20-12-2007",

}

Charon, I, Cohen, G, Hudry, O & Lobstein, A 2007, Links between discriminating and identifying codes in the binary hamming space. in Applied Algebra, Algebraic Algorithms and Error-Correcting Codes - 17th International Symposium, AAECC- 17, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4851 LNCS, Springer Verlag, pp. 267-270, 17th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC-17, Bangalore, India, 16/12/07. https://doi.org/10.1007/978-3-540-77224-8_31

Links between discriminating and identifying codes in the binary hamming space. / Charon, Irène; Cohen, Gérard; Hudry, Olivier et al.
Applied Algebra, Algebraic Algorithms and Error-Correcting Codes - 17th International Symposium, AAECC- 17, Proceedings. Springer Verlag, 2007. p. 267-270 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4851 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Links between discriminating and identifying codes in the binary hamming space

AU - Charon, Irène

AU - Cohen, Gérard

AU - Hudry, Olivier

AU - Lobstein, Antoine

PY - 2007/1/1

Y1 - 2007/1/1

N2 - Let Fn be the binary n-cube, or binary Hamming space of dimension n, endowed with the Hamming distance, and εn (respectively, οn) the set of vectors with even (respectively, odd) weight. For r ≥ 1 and x ∈ Fn, we denote by Br(x) the ball of radius r and centre x. A code C ⊆ F n is said to be r-identifying if the sets Br(x) ∩ C, x ∈ Fn, are all nonempty and distinct. A code C ⊆ εn is said to be r-discriminating if the sets B r(x)∩C, x ∈ ο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 Fn+1.

AB - Let Fn be the binary n-cube, or binary Hamming space of dimension n, endowed with the Hamming distance, and εn (respectively, οn) the set of vectors with even (respectively, odd) weight. For r ≥ 1 and x ∈ Fn, we denote by Br(x) the ball of radius r and centre x. A code C ⊆ F n is said to be r-identifying if the sets Br(x) ∩ C, x ∈ Fn, are all nonempty and distinct. A code C ⊆ εn is said to be r-discriminating if the sets B r(x)∩C, x ∈ ο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 Fn+1.

KW - Coding theory

KW - Discriminating codes

KW - Graph theory

KW - Hamming space

KW - Hypercube

KW - Identifying codes

U2 - 10.1007/978-3-540-77224-8_31

DO - 10.1007/978-3-540-77224-8_31

M3 - Conference contribution

AN - SCOPUS:38349047920

SN - 9783540772231

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 267

EP - 270

BT - Applied Algebra, Algebraic Algorithms and Error-Correcting Codes - 17th International Symposium, AAECC- 17, Proceedings

PB - Springer Verlag

T2 - 17th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC-17

Y2 - 16 December 2007 through 20 December 2007

ER -

Charon I, Cohen G, Hudry O, Lobstein A. Links between discriminating and identifying codes in the binary hamming space. In Applied Algebra, Algebraic Algorithms and Error-Correcting Codes - 17th International Symposium, AAECC- 17, Proceedings. Springer Verlag. 2007. p. 267-270. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-77224-8_31

Links between discriminating and identifying codes in the binary hamming space

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this