On Determining Deep Holes of Generalized Reed-Solomon Codes

DOI10.1007/978-3-642-45030-3_10zbMATH Open1321.94136OpenAlexW3020932339MaRDI QIDQ2872075FDOQ2872075

Authors: Qi Cheng, Jiyou Li, Jincheng Zhuang 

Publication date: 14 January 2014

Published in: Algorithms and Computation (Search for Journal in Brave)

Abstract: 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 $R{S}_q(F_q,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 $R{S}_p(D,k)$, where $p$ is a prime, $|D|>kgeqslantfracp-12$. Our techniques are built on the idea of deep hole trees, and several results concerning the Erd{"o}s-Heilbronn conjecture.

Full work available at URL: https://arxiv.org/abs/1309.3546

Recommendations

• On Determining Deep Holes of Generalized Reed–Solomon Codes
• On deep holes of generalized Reed-Solomon codes
• Deep holes of generalized Reed-Solomon codes
• Determining deep hole trees of generalized Reed-Solomon codes and an application
• On Deciding Deep Holes of Reed-Solomon Codes
• On deep holes of standard Reed-Solomon codes
• Some results on deep holes of generalized projective Reed-Solomon codes
• Remark on conjecture of deep holes of standard Reed-Solomon code
• Deep Holes of Projective Reed-Solomon Codes
• On deep holes of primitive projective Reed-Solomon codes

zbMATH Keywords

deep holeReed-Solomon codedeep hole treeErdős-Heilbronn conjecture

Mathematics Subject Classification ID

Geometric methods (including applications of algebraic geometry) applied to coding theory (94B27)

Cited In (13)

• A study of deep holes in the first-order Reed-Muller codes
• Deep holes of generalized Reed-Solomon codes
• Deep holes in Reed-Solomon codes based on Dickson polynomials
• On Deciding Deep Holes of Reed-Solomon Codes
• Holes in Generalized Reed–Muller Codes
• On Determining Deep Holes of Generalized Reed–Solomon Codes
• On the error distance of extended Reed-Solomon codes
• Remark on conjecture of deep holes of standard Reed-Solomon code
• On deep holes of standard Reed-Solomon codes
• Determining deep hole trees of generalized Reed-Solomon codes and an application
• On deep holes of generalized Reed-Solomon codes
• On deep holes of Gabidulin codes
• Some results on deep holes of generalized projective Reed-Solomon codes

This page was built for publication: On Determining Deep Holes of Generalized Reed-Solomon Codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2872075)