Almost Cover-Free Codes and Designs

Abstract : An s-subset of codewords of a binary code X is said to be (s,l)-bad in X if the code X contains a subset of other l codewords such that the conjunction of the l codewords is covered by the disjunctive sum of the s codewords. Otherwise, the s-subset of codewords of X is called (s,l)-good in X. A binary code X is said to be a cover-free (CF) (s,l)-code if the code X does not contain (s,l)-bad subsets. In this paper, we introduce a natural probabilistic generalization of CF (s,l)-codes, namely: a binary code X is said to be an almost CF (s,l)-code if the relative number of its (s,l)-good s-subsets is close to 1. We develop a random coding method based on the ensemble of binary constant weight codes to obtain lower bounds on the capacity of such codes. Our main result shows that the capacity for almost CF (s,l)-codes is essentially greater than the rate for ordinary CF (s,l)-codes.
Type de document :
Communication dans un congrès
Pascale Charpin, Nicolas Sendrier, Jean-Pierre Tillich. The 9th International Workshop on Coding and Cryptography 2015 WCC2015, Apr 2015, Paris, France. 2016, Proceedings of the 9th International Workshop on Coding and Cryptography 2015 WCC2015. 〈wcc2015.inria.fr〉
Liste complète des métadonnées

Littérature citée [12 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01276693
Contributeur : Jean-Pierre Tillich <>
Soumis le : vendredi 19 février 2016 - 17:41:33
Dernière modification le : lundi 22 février 2016 - 11:01:21
Document(s) archivé(s) le : vendredi 20 mai 2016 - 11:38:13

Fichier

wcc15-fr2-2.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01276693, version 1

Collections

Citation

A.G. D'Yachkov, I.V. Vorobyev, N.A. Polyanskii, V.Yu. Shchukin. Almost Cover-Free Codes and Designs. Pascale Charpin, Nicolas Sendrier, Jean-Pierre Tillich. The 9th International Workshop on Coding and Cryptography 2015 WCC2015, Apr 2015, Paris, France. 2016, Proceedings of the 9th International Workshop on Coding and Cryptography 2015 WCC2015. 〈wcc2015.inria.fr〉. 〈hal-01276693〉

Partager

Métriques

Consultations de la notice

19

Téléchargements de fichiers

37