On Determining Deep Holes of Generalized Reed-Solomon Codes

الأصل · EN

For a linear code, deep holes are defined to be vectors that are further away from codewords than all other vectors. The problem of deciding whether a received word is a deep hole for generalized Reed-Solomon codes is proved to be co-NP-complete. For the extended Reed-Solomon codes RSq(,k), a conjecture was made to classify deep holes by Cheng and Murray in 2007. Since then a lot of effort has been made to prove the conjecture, or its various forms. In this paper, we classify deep holes completely for generalized Reed-Solomon codes RSₚ (D,k), where p is a prime, |D| > k p-1/2. Our techniques are built on the idea of deep hole trees, and several results concerning the Erdös-Heilbronn conjecture.