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

CNRS

Résultats de recherche: Le chapitre dans un livre, un rapport, une anthologie ou une collection › Contribution à une conférence › Revue par des pairs

Résumé

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ⁿ⁺¹.

langue originale	Anglais
titre	Applied Algebra, Algebraic Algorithms and Error-Correcting Codes - 17th International Symposium, AAECC- 17, Proceedings
Editeur	Springer Verlag
Pages	267-270
Nombre de pages	4
ISBN (imprimé)	9783540772231
Les DOIs	https://doi.org/10.1007/978-3-540-77224-8_31
état	Publié - 1 janv. 2007
Evénement	17th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC-17 - Bangalore, Inde Durée: 16 déc. 2007 → 20 déc. 2007

Série de publications

Nom	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	4851 LNCS
ISSN (imprimé)	0302-9743
ISSN (Electronique)	1611-3349

Une conférence

Une conférence	17th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC-17
Pays/Territoire	Inde
La ville	Bangalore
période	16/12/07 → 20/12/07

Accès au document

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

Contient cette citation

Charon, I., Cohen, G., Hudry, O., & Lobstein, A. (2007). Links between discriminating and identifying codes in the binary hamming space. Dans Applied Algebra, Algebraic Algorithms and Error-Correcting Codes - 17th International Symposium, AAECC- 17, Proceedings (p. 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. p. 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. Dans 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, p. 267-270, 17th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC-17, Bangalore, Inde, 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).

Résultats de recherche: Le chapitre dans un livre, un rapport, une anthologie ou une collection › Contribution à une conférence › Revue par des pairs

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. Dans 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

Résumé

Série de publications

Une conférence

Accès au document

Empreinte digitale

Contient cette citation