Mathematics – Number Theory
Scientific paper
2011-08-17
Mathematics
Number Theory
10 pages
Scientific paper
Determining deep holes is an important open problem in decoding Reed-Solomon codes. It is well known that the received word is trivially a deep hole if the degree of its Lagrange interpolation polynomial equals the dimension of the Reed-Solomon code. For the standard Reed-Solomon codes $[p-1, k]_p$ with $p$ a prime, Cheng and Murray conjectured in 2007 that there is no other deep holes except the trivial ones. In this paper, we show that this conjecture is not true. In fact, we find a new class of deep holes for standard Reed-Solomon codes $[q-1, k]_q$ with $q$ a prime power of $p$. Let $q \geq 4$ and $2 \leq k\leq q-2$. We show that the received word $u$ is a deep hole if its Lagrange interpolation polynomial is the sum of monomial of degree $q-2$ and a polynomial of degree at most $k-1$. So there are at least $2(q-1)q^k$ deep holes if $k \leq q-3$.
Hong Shaofang
Wu Rongjun
No associations
LandOfFree
On deep holes of standard 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 deep holes of standard Reed-Solomon codes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On deep holes of standard Reed-Solomon codes will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-541028