Computer Science – Information Theory
Scientific paper
2005-09-21
Computer Science
Information Theory
Scientific paper
For generalized Reed-Solomon codes, it has been proved \cite{GuruswamiVa05} that the problem of determining if a received word is a deep hole is co-NP-complete. The reduction relies on the fact that the evaluation set of the code can be exponential in the length of the code -- a property that practical codes do not usually possess. In this paper, we first presented a much simpler proof of the same result. We then consider the problem for standard Reed-Solomon codes, i.e. the evaluation set consists of all the nonzero elements in the field. We reduce the problem of identifying deep holes to deciding whether an absolutely irreducible hypersurface over a finite field contains a rational point whose coordinates are pairwise distinct and nonzero. By applying Schmidt and Cafure-Matera estimation of rational points on algebraic varieties, we prove that the received vector $(f(\alpha))_{\alpha \in \F_q}$ for Reed-Solomon $[q,k]_q$, $k < q^{1/7 - \epsilon}$, cannot be a deep hole, whenever $f(x)$ is a polynomial of degree $k+d$ for $1\leq d < q^{3/13 -\epsilon}$.
Cheng Qing-Qi
Murray Elizabeth
No associations
LandOfFree
On Deciding Deep Holes of 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 On Deciding Deep Holes of Reed-Solomon Codes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Deciding Deep Holes of Reed-Solomon Codes will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-486182