Source-linked AI summary
Extension of MDS Codes over Finite Fields
Puyin Wang, Jinquan Luo
TL;DR
A general, easily verifiable way to extend non-RS MDS codes is lacking. The paper gives a hyperplane-based iterative extension procedure. Its examples include longer non-RS MDS codes whose Schur-square dimensions exceed 2k.
Problem
A general, easily verifiable criterion for extending MDS codes, particularly non-RS constructions, is lacking.
Source: §1 · p. 2Method
The procedure identifies hyperplanes generated by k − 1 columns and uses inner products to test candidate columns before extending the code step by step.
Source: §4 · p. 13Results
The examples yield longer non-RS MDS codes, including codes whose Schur-square dimensions are strictly greater than 2k.
Source: §4 · p. 13Takeaways & Limitations
Across examples over small finite fields, the procedure increases code lengths and can also increase Schur-square dimensions beyond 2k.
Source: §4 · p. 13The iterative choice of each new column can affect later extensions, and failure to extend a chosen sequence does not establish that the original code cannot reach a greater length.
Source: §4 · pp. 13–14
Abstract
from arXiv · showhide
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\left(\binom{n}{k-1} q^{k-1} k^3\right)$ 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.
1 Introduction
The introduction frames extending non-RS MDS codes as an important problem without a general, easily verifiable criterion. It presents a practical condition and an efficient algorithm for systematically finding longer non-RS MDS codes.
1 Introduction
- MDS codes attain the Singleton bound, and non-RS MDS codes are inequivalent to Reed–Solomon codes, which are constructed by evaluating polynomials over finite fields.Source: §1 · p. 1
- Non-RS MDS constructions include algebraic-geometry and cyclic codes, explicit families, and twisted Reed–Solomon codes.Source: §1 · pp. 1–2
- A general, easily verifiable criterion for extending MDS codes—particularly non-RS codes—is still lacking, despite the importance of constructing new MDS codes from known ones.Source: §1 · p. 2
- The paper proposes a practical extension condition and an efficient algorithm, representing admissible vectors as those avoiding finitely many hyperplanes in F_q^k.Source: §1 · p. 2
2 Preliminary
The preliminary section sets out code and generator-matrix terminology, equivalence, and the paper’s definition of extension. It also introduces Schur-square and Cauchy-structure criteria used to assess whether codes are non-RS.
2 Preliminary
- A generator matrix is a k × n matrix whose rows form a basis of the code.Source: §2 · p. 2
- Equivalent codes differ by coordinate permutations and nonzero coordinate scalings; an MDS code inequivalent to every RS code is called non-RS.Source: §2 · p. 2
- An extension appends one coordinate to each codeword, equivalently adding one column to the generator matrix.Source: §2 · p. 2
- The Schur square is the componentwise product code C ∗ C; its dimension gives a sufficient, but sometimes inconclusive, test for non-RS equivalence when it equals 2k − 1.Source: §2 · pp. 2–3
- When the Schur-square test is inconclusive, the paper uses a Cauchy-structure criterion: for A′, all entries of A must be nonzero, all 2 × 2 minors nonzero, and all 3 × 3 minors zero.Source: §2 · p. 3
3 Meet-in-the-Middle Algorithm
This section presents a meet-in-the-middle procedure for extending non-RS MDS codes by testing candidate columns against geometric constraints, with expected cost approximately O(kq^k) when n < q. Examples from several code families over fields of order at most 32 demonstrate longer codes retaining non-RS structure, with varied Schur-square dimensions.
Algorithm
- The algorithm seeks a column β nonorthogonal to every normal vector for hyperplanes spanned by k − 1 existing columns, yielding an MDS extension that remains non-RS when the original code is non-RS.MDS validity follows because each such set of k − 1 columns together with β is linearly independent.Source: §3 · pp. 3–4
Complexity
- For n < q, the algorithm’s expected cost is approximately O(kq^k), versus a significantly costlier direct exhaustive search.The comparison is in number of multiplications in Fq.Source: §3 · p. 4
Examples
- Over F8, successive extensions produce a non-RS MDS code reaching the maximal possible length, although the code itself is not new.The example demonstrates reaching the MDS bound q + 2 over F8.Source: §3 · p. 5
- Over F9, the algorithm produces a non-RS [9, 4, 6] MDS code with dim(C2) = 9; known arc classifications suggest length 9 is maximal for such non-RS dimension-four codes.The passage explains that extending to length 10 would require a non-RS 10-arc in PG(3, 9), which known classifications do not support.Source: §3 · p. 6
- In two examples, extending the TGRS codes introduced in yields non-RS MDS codes [9, 3, 7] and [9, 4, 6], with dim(C2) equal to 6 and 8, respectively.Source: §3 · pp. 6–7
- Over F19, the unique admissible projective extension of a non-RS code yields an [11, 5, 7] MDS code with dim(C2) = 10.The starting code has dim(C0^2) = 10.Source: §3 · p. 7
- Over F13, extension gives a non-RS [9, 4, 6] MDS code with dim(C2) = 9, exceeding the cited subgroup-based construction’s largest length of 8.Its Schur-square dimension also exceeds 2k, so it is not equivalent to a one-column CTRS code.Source: §3 · p. 8
3 Meet-in-the-Middle Algorithm
- Over F17, extension produces a non-RS [10,4,7] code with Schur-square dimension 10, exceeding the dimension 2k of the cited column-twisted Reed–Solomon families.A second [10,4,7] code has Schur-square dimension 9 and is also not equivalent to those families.Source: §3 · p. 9
- Dimension-three extensions include [10,3,8] over F13, [14,3,12] over F19 and F23, [16,3,14] over F27, and [16,3,14] over F29.The extended codes reported in these examples remain non-RS and have Schur-square dimension 6.Source: §3 · pp. 10–11
- In both cases, G2 = (G0 | β1, β2) generates a non-RS MDS code: [10, 3, 8] over F16 and [19, 3, 17] over F32, each with dim(C2²) = 6.The construction also permits adjoining f(∞), the coefficient of x³ in f, while preserving the MDS property.Source: §3 · p. 11
- Extensions generate non-RS MDS codes [10, 3, 8] over F13, [12, 3, 10] over F17, and [16, 3, 14] over F29.For the first two codes, dim(C2 4) = 6; for the third, dim(C2 9) = 6.Source: §3 · pp. 12–13
- The extension procedure produces MDS non-RS codes over F9 and F13 and over F17, each with Schur-square dimension dim(C2)=9, exceeding 2k=8.Source: §3 · p. 13
4 Conclusion and further study
The procedure extends non-RS MDS codes by adding columns while preserving their non-RS property, and examples show increased lengths and Schur-square dimensions. Each column choice can affect later extensions, so a sequence that stops need not be the longest from the original code.
4 Conclusion and further study
- To extend an MDS code, the method excludes new columns lying in hyperplanes generated by k −1 existing columns and tests admissibility using their normal vectors.When the initial code is non-RS, the extended codes remain non-RS.Source: §4 · p. 13
- The examples increase code lengths and sometimes produce Schur-square dimensions strictly greater than 2k, with many resulting non-RS codes longer than previously known ones.The authors describe these examples as evidence that the procedure works in practice.Source: §4 · p. 13
- A choice of new column can affect the next extension, and stopping when no column can be added does not establish that the sequence is longest from the original code.The authors suggest automorphisms, algebraic properties, and backtracking as possible ways to explore alternative sequences.Source: §4 · pp. 13–14