Extension of MDS Codes over Finite Fields
Abstract
In this paper, we investigate extending of [n,k,n−k+1] non-Reed--Solomon(non-RS) MDS codes to [n+1,k,n−k+2] non-RS MDS codes. We develop a practical iterative algorithm for constructing longer MDS codes while preserving their non-RS structure. The proposed algorithm is inspired by the meet-in-the-middle algorithm in cryptanalysis. On average, it requires at most O(kqk) multiplications, compared with O(binomnk−1 qk−1 k3) multiplications for generic exhaustive search. Applying the proposed algorithm to several known families of MDS codes, including elliptic-curve, twisted Reed--Solomon, column-twisted Reed--Solomon, cyclic, and missing-monomial MDS codes over fields of order at most $32$, we obtain new MDS codes of increased lengths that remain inequivalent to Reed--Solomon codes. In particular, we construct [9,4,6] codes over F9 and F13, each with Schur-square dimension $9$. Over F17, we obtain two inequivalent [10,4,7] codes with Schur-square dimensions $9$ and $10$, respectively. The latter is the dual of an extended [10,6,5] code, demonstrating that the method also applies when k>n/2. For these dimension-four codes, the Schur-square dimensions $9$ and $10$ exceed both that of RS code (Schur-square dimension $7$) and those of specific elliptic-curve and column-twisted Reed--Solomon families (Schur-square dimension $8$). Some of these parameters of non-RS MDS codes have not been reported before.
Related
- Superpolynomial Lists for Reed-Solomon Codes over Binary Extension Fields
- Sharp spherical Lp→ L4 extension estimates over finite fields in odd dimensions
- Sharp L2 → L4 extension inequality for quadratic surfaces in finite fields
- Sharp endpoint extension inequalities for the moment curve on finite fields II: an extremal property of the uniform distribution
- Stabiliser codes over prime fields as weighted graphs and as quantum sets of lines
BibTeX
@misc{wang2026extension,
title = {{Extension of MDS Codes over Finite Fields}},
author = {Puyin Wang and Jinquan Luo},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.31023},
eprint = {2610.31023},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.31023},
}
RIS
TY - UNPB
TI - Extension of MDS Codes over Finite Fields
AU - Puyin Wang
AU - Jinquan Luo
PY - 2026
DA - 2026/10/22
PB - arXiv
DO - 10.48550/arxiv.2610.31023
UR - https://arxiv.org/abs/2610.31023
AB - In this paper, we investigate extending of [n,k,n−k+1] non-Reed--Solomon(non-RS) MDS codes to [n+1,k,n−k+2] non-RS MDS codes. We develop a practical iterative algorithm for constructing longer MDS codes while preserving their non-RS structure. The proposed algorithm is inspired by the meet-in-the-middle algorithm in cryptanalysis. On average, it requires at most O(kq^k) multiplications, compared with O(binomnk−1 q^k−1 k^3) multiplications for generic exhaustive search. Applying the proposed algorithm to several known families of MDS codes, including elliptic-curve, twisted Reed--Solomon, column-twisted Reed--Solomon, cyclic, and missing-monomial MDS codes over fields of order at most $32$, we obtain new MDS codes of increased lengths that remain inequivalent to Reed--Solomon codes. In particular, we construct [9,4,6] codes over F_9 and F_13, each with Schur-square dimension $9$. Over F_17, we obtain two inequivalent [10,4,7] codes with Schur-square dimensions $9$ and $10$, respectively. The latter is the dual of an extended [10,6,5] code, demonstrating that the method also applies when k>n/2. For these dimension-four codes, the Schur-square dimensions $9$ and $10$ exceed both that of RS code (Schur-square dimension $7$) and those of specific elliptic-curve and column-twisted Reed--Solomon families (Schur-square dimension $8$). Some of these parameters of non-RS MDS codes have not been reported before.
ER -