New Set of Codes for the Maximum-Likelihood Decoding Problem

Morgan Barbier (1)

1 TANC - Algorithmic number theory for cryptology

The maximum-likelihood decoding problem is known to be NP-hard for general linear and Reed-Solomon codes. In this paper, we introduce the notion of A-covered codes, that is, codes that can be decoded through a polynomial time algorithm A whose decoding bound is beyond the covering radius. For these codes, we show that the maximum-likelihood decoding problem is reachable in polynomial time in the code parameters. Focusing on bi- nary BCH codes, we were able to find several examples of A-covered codes, including two codes for which the maximum-likelihood decoding problem can be solved in quasi-quadratic time.

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.

Mots clés: Maximum-likelihood decoding; perfect codes; covering radius; list decoding

Domaines: Théorie de l'information [cs.IT]; Théorie de l'information et codage [math.IT]

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