Computer Science – Information Theory
Scientific paper
2008-02-08
Computer Science
Information Theory
Scientific paper
The complexity of maximal likelihood decoding of the Reed-Solomon codes $[q-1, k]_q$ is a well known open problem. The only known result in this direction states that it is at least as hard as the discrete logarithm in some cases where the information rate unfortunately goes to zero. In this paper, we remove the rate restriction and prove that the same complexity result holds for any positive information rate. In particular, this resolves an open problem left in [4], and rules out the possibility of a polynomial time algorithm for maximal likelihood decoding problem of Reed-Solomon codes of any rate under a well known cryptographical hardness assumption. As a side result, we give an explicit construction of Hamming balls of radius bounded away from the minimum distance, which contain exponentially many codewords for Reed-Solomon code of any positive rate less than one. The previous constructions only apply to Reed-Solomon codes of diminishing rates. We also give an explicit construction of Hamming balls of relative radius less than 1 which contain subexponentially many codewords for Reed-Solomon code of rate approaching one.
Cheng Qing-Qi
Wan Daqing
No associations
LandOfFree
Complexity of Decoding Positive-Rate Reed-Solomon Codes 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 Complexity of Decoding Positive-Rate Reed-Solomon Codes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Complexity of Decoding Positive-Rate Reed-Solomon Codes will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-402589