2010/11/12 by Morgan Barbier, Barbier, Morgan
Computer Science · Engineering · Mathematics · #Cellular Automata and Applications #Coding theory and cryptography #FOS: Computer and information sciences #Information Theory (cs.IT) #cs.IT #graph theory and CDMA systems #math.IT
paper · pdf · doi:10.48550/arxiv.1011.2834
in Yet Another Conference on Cryptography, Porquerolle : France (2010)
arxiv created 2010/11/12 · openalex publication_date 2010/11/12 · arxiv updated 2010/11/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.