Computer Science – Information Theory
Scientific paper
2010-11-12
Computer Science
Information Theory
in Yet Another Conference on Cryptography, Porquerolle : France (2010)
Scientific paper
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.
No associations
LandOfFree
New Set of Codes for the Maximum-Likelihood Decoding Problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with New Set of Codes for the Maximum-Likelihood Decoding Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and New Set of Codes for the Maximum-Likelihood Decoding Problem will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-203485