New Set of Codes for the Maximum-Likelihood Decoding Problem

Morgan Barbier 1
1 TANC - Algorithmic number theory for cryptology
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France, X - École polytechnique, CNRS - Centre National de la Recherche Scientifique : UMR7161
Résumé : Le problème du décodage par maximum de vraisemblance est connue comme NP-difficile pour les codes linéaires en générales et pour les codes de Reed-Solomon. Dans ce papier, nous introduisons la notion de codes A-couvert, c'est des codes qui peuvent être décodés en tant polynomial par un algorithme A qui décode au moins jusqu'au rayon de revouvrement. Pour ces codes, nous montrons que le problème de décodage par maximum de vraisemblance est résolvable en temps polynomial. En s'intéressant aux codes BCH binaires, nous sommes capable de trouver quelques examples de codes A-couvert, dont deux codes pour lesquels le problème du décodage par maximum de vraisemblance peut être résolue en temps quasi-quadratique.
Type de document :
Communication dans un congrès
Yet Another Conference on Cryptography, Oct 2010, Porquerolle, France. 2010
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00534726
Contributeur : Morgan Barbier <>
Soumis le : jeudi 11 novembre 2010 - 10:02:01
Dernière modification le : jeudi 10 mai 2018 - 02:06:38
Document(s) archivé(s) le : jeudi 30 juin 2011 - 13:36:20

Fichiers

article_V0_4_HAL.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00534726, version 1
  • ARXIV : 1011.2834

Collections

Citation

Morgan Barbier. New Set of Codes for the Maximum-Likelihood Decoding Problem. Yet Another Conference on Cryptography, Oct 2010, Porquerolle, France. 2010. 〈inria-00534726〉

Partager

Métriques

Consultations de la notice

234

Téléchargements de fichiers

219