Hyperderivative Reed-Solomon codes decoding radius and difficult cases studied
Covering Radius and Deep Holes of Hyperderivative Reed-Solomon Codes under the NRT Metric
Information Theory
Summary
This paper studies a type of error-correcting code called Hyperderivative Reed-Solomon codes, which are used to protect data. The authors focus on how far off a received message can be from any valid codeword—the covering radius—and identifying particularly tricky received messages called deep holes. They describe these deep holes using mathematical properties related to polynomials and geometric structures, and provide several explicit examples. They also make a conjecture about the codes’ behavior and offer formulas to count these difficult cases in some situations.
What this means in practice
- •For coding engineers: Improve error correction and decoding algorithms by understanding the limiting error radius and rare difficult cases in HRS codes under NRT metric.
- •For cryptography developers: Design cryptographic systems using properties of deep holes in HRS codes to enhance security guarantees.
Authors
Zhihao Zhu, Haojie Gu, Jun Zhang, Yu Li
Abstract
The deep hole problem is a fundamental problem in coding theory, and it has many important applications in code constructions and cryptography. The deep hole problem of Reed-Solomon codes has gained a lot of attention. As a generalization of Reed-Solomon codes under Hamming metric, we study the covering radius and deep holes of Hyperderivative Reed-Solomon (HRS) codes under the Niederreiter-Rosenbloom-Tsfasman (NRT) metric. We determine the NRT covering radius of HRS code and characterize its NRT deep holes via Maximum Distance Separable (MDS) extensions and polynomial remainder conditions. We further relate the enumeration of NRT deep holes to the characteristic polynomial of an associated hyperplane arrangement. We also provide three classes of explicit NRT deep-hole constructions, propose a Cheng-Murray type conjecture for HRS codes under the NRT metric and obtain a conditional low-layer description. Using these characterizations, we derive exact enumeration formulas in several special cases.