Extended codes and deep holes of MDS codes

Yansheng Wu, Cunsheng Ding, Tingfang ChenarXiv 2023 · DOI · arXiv

TL;DR

This paper investigates how extending existing MDS (Maximum Distance Separable) codes affects their MDS property. The core finding is that an extended MDS code remains MDS if and only if a specific condition related to the covering radius of its dual code and the properties of the extension vector is met. This result provides a crucial link between code extension, deep holes, and the MDS property, with applications to Reed-Solomon and related codes.

What Problem Does This Paper Address?

MDS codes are highly efficient error-correcting codes with numerous applications. A common technique to create new codes from existing ones is "code extension," which increases the code length by one. However, this extension process can degrade the code's properties, including its MDS status. Specifically, the paper addresses the question of when an extended MDS code remains an MDS code. This is a fundamental question for constructing new, powerful MDS codes. The paper also delves into the concept of "deep holes" – vectors that are furthest from any codeword – and their relationship to the MDS property of extended codes, particularly for generalized Reed-Solomon (GRS) codes.

Methods

The paper introduces two types of code extensions: the "first kind" (using a generator matrix and a vector) and the "second kind" (using a vector and a specific construction). The primary focus is on the second kind of extension. The authors establish a key theorem (Theorem 6) that connects the MDS property of an extended code $C(u)$ to the covering radius of the dual code $C^\perp$ and whether the extension vector $u$ is a "deep hole" of $C^\perp$. This theorem serves as the central tool for subsequent analyses. The paper then applies this theorem to specific families of MDS codes, including GRS codes and extended GRS (EGRS) codes, to determine conditions under which their extensions remain MDS and to calculate their covering radii. Techniques involve leveraging existing results on deep holes of Reed-Solomon codes and algebraic manipulations of generator and parity check matrices.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • The MDS Extension Criterion: The paper's main contribution is Theorem 6, which states that an extended MDS code $C(u)$ remains MDS if and only if the covering radius of its dual code $C^\perp$ is equal to its dimension $k$, and the extension vector $u$ is a deep hole of $C^\perp$. This provides a precise condition for preserving the MDS property.
  • Deep Holes are Key: The concept of "deep holes" is not just a theoretical curiosity but a critical component in determining the MDS status of extended codes. The paper shows a direct link between deep holes of the dual code and the MDS property of the extended code.
  • GRS and EGRS Code Extensions: The paper provides concrete applications of the main theorem to GRS and EGRS codes, characterizing when their extensions are MDS and determining their covering radii. This demonstrates the practical utility of the theoretical results.
  • Covering Radius of PRS Codes: The paper offers partial answers to existing conjectures about the covering radii of projective Reed-Solomon (PRS) codes, further highlighting the importance of deep holes and covering radii in MDS code theory.

Key Results

  • Theorem 6: For an MDS code $C$, its extended code $C(u)$ is MDS if and only if $\rho(C^\perp) = k$ and $u$ is a deep hole of $C^\perp$.
  • GRS Code Extensions: Conditions are derived for when extended GRS codes $C_k(a, v)(u)$ remain MDS, relating to deep holes of their duals (Theorem 9).
  • Covering Radii: The covering radii of various MDS code families, including GRS, EGRS, and PRS codes, are determined under specific conditions. For instance, Theorem 14 provides the covering radius of $C_k(a, 1, \infty)^+$ under certain conditions, and Theorem 17 addresses the covering radius of PRS(k).
  • Specific Examples: The paper provides examples for specific parameters (e.g., $n=q=4, k=3$) to illustrate the application of the theorems.

Limitations and Future Work

  • Hardness of Deep Hole Determination: The paper acknowledges that determining deep holes for general linear codes is a difficult problem. This inherent difficulty makes it challenging to apply the main theorem in all cases, especially for arbitrary MDS codes.
  • Open Problems: The paper explicitly mentions "Open Problem 1" regarding the existence of vectors $u$ that keep an MDS code extended while remaining MDS. While the paper provides conditions, finding such vectors for arbitrary MDS codes remains a hard problem.
  • Conjectures: The paper presents Conjecture 2 regarding the covering radii of PRS codes and invites further research to prove or disprove it. Similarly, Conjecture 1 is posed for extended MDS codes.
  • Future Work: The authors suggest that proving the presented conjectures would be valuable. Further research into determining deep holes for more general classes of MDS codes is also implied as a direction for future work.

Summary updated

BibTeX
@misc{wu2023extended,
  author = {Yansheng Wu and Cunsheng Ding and Tingfang Chen},
  title = {{Extended codes and deep holes of MDS codes}},
  year = {2023},
  eprint = {2312.05534},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2312.05534},
}

Loading related content...

Figure