Two Families of Linear Codes Containing Non-GRS MDS Codes
Pith reviewed 2026-05-16 22:19 UTC · model grok-4.3
The pith
Modifying generator matrices of generalized Reed-Solomon codes produces two new families of linear MDS codes that include non-GRS examples.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
By modifying the generator matrices of GRS codes, the authors obtain two new families of linear codes over finite fields. For each family they derive a parity-check matrix and prove necessary and sufficient conditions on the field elements and multipliers that make the code MDS. Certain subfamilies yield MDS codes that are not GRS codes, and the paper characterizes their self-orthogonality and self-duality properties with explicit constructions and examples.
What carries the argument
Modified generator matrices obtained from GRS codes, together with the derived parity-check matrices that enforce the MDS minimum-distance condition.
If this is right
- The two families admit explicit parity-check matrices that confirm the MDS property when the given algebraic conditions hold.
- Subfamilies produce MDS codes that lie outside the GRS class.
- Additional parameter restrictions yield self-orthogonal and self-dual members of each family.
- Concrete examples over small finite fields illustrate both the MDS and non-GRS properties.
Where Pith is reading between the lines
- The modification technique may extend to other evaluation-based code families to produce further non-equivalent MDS codes.
- Non-GRS MDS codes in these families could possess distinct automorphism groups or decoding algorithms compared with classical GRS codes.
- The constructions supply infinite families of MDS codes over fields of any fixed characteristic once suitable multipliers are chosen.
- Such codes may support new applications in distributed storage or cryptographic protocols that exploit their explicit algebraic structure.
Load-bearing premise
The chosen modifications to the GRS generator matrices preserve the linear independence of any k columns so that the minimum distance equals n minus k plus one under the stated conditions on the evaluation points.
What would settle it
An explicit parameter set satisfying the paper's necessary and sufficient conditions for which the constructed code has minimum distance strictly smaller than n minus k plus one.
read the original abstract
We construct two new families of linear codes by modifying the generator matrices of generalized Reed-Solomon (GRS) codes. For these codes, we explicitly derive parity-check matrices and establish necessary and sufficient conditions ensuring the MDS property. Additionally, we explore subfamilies within these constructions that are non-GRS MDS codes. We also characterize their self-orthogonal and self-dual properties and present some explicit constructions and examples.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript constructs two new families of linear codes by modifying the generator matrices of generalized Reed-Solomon (GRS) codes. It explicitly derives parity-check matrices for these codes and establishes necessary and sufficient conditions for the MDS property. The paper also explores subfamilies that yield non-GRS MDS codes, characterizes their self-orthogonal and self-dual properties, and provides explicit constructions and examples.
Significance. If the constructions and conditions are correct, the paper provides valuable new families of MDS codes that are not generalized Reed-Solomon codes, addressing a key open area in coding theory where few non-GRS MDS codes are known. The explicit parity-check matrices and algebraic conditions enable practical verification and potential use in applications requiring high-distance codes. The self-orthogonality characterizations may have implications for related areas such as quantum error-correcting codes.
major comments (1)
- [Abstract and main construction sections] The abstract asserts explicit derivations of parity-check matrices and necessary-and-sufficient conditions for the MDS property, yet the manuscript provides no proof sketches, matrix examples, or verification steps for these claims. This absence prevents confirmation that the column-independence arguments in the parity-check matrix actually establish the Singleton bound under the stated parameter conditions.
minor comments (1)
- Clarify the precise range of field sizes and evaluation-point choices for which the necessary-and-sufficient conditions hold, to avoid potential hidden restrictions.
Simulated Author's Rebuttal
We thank the referee for the careful reading and constructive feedback. We address the single major comment below and will strengthen the exposition in the revised manuscript.
read point-by-point responses
-
Referee: [Abstract and main construction sections] The abstract asserts explicit derivations of parity-check matrices and necessary-and-sufficient conditions for the MDS property, yet the manuscript provides no proof sketches, matrix examples, or verification steps for these claims. This absence prevents confirmation that the column-independence arguments in the parity-check matrix actually establish the Singleton bound under the stated parameter conditions.
Authors: We agree that the current presentation would benefit from more explicit guidance. In the revised version we will insert concise proof sketches immediately after the statements of the parity-check matrices, detailing the column-independence arguments that establish the Singleton bound. We will also add two or three fully worked matrix examples (with explicit parameter choices) together with step-by-step verification that the MDS condition holds precisely when the stated algebraic conditions are satisfied. These additions will not change any theorems or constructions but will make the reasoning self-contained and easier to verify. revision: yes
Circularity Check
No significant circularity; algebraic constructions are self-contained
full rationale
The paper presents explicit constructions of two families of linear codes obtained by modifying the generator matrices of generalized Reed-Solomon codes. It derives parity-check matrices directly from these modifications and states necessary and sufficient conditions on the modification parameters that ensure the resulting codes meet the Singleton bound. These conditions are verified via standard finite-field linear algebra (linear independence of columns in the parity-check matrix) and the known MDS property of the underlying GRS codes. No derivation step reduces by construction to a fitted parameter, self-referential definition, or load-bearing self-citation whose validity depends on the present work. Subfamilies claimed to be non-GRS MDS codes are exhibited with explicit examples, and self-orthogonality characterizations follow from the same algebraic setup without circular reduction. The argument is therefore independent of its own outputs.
Axiom & Free-Parameter Ledger
axioms (1)
- standard math Standard properties of finite fields, evaluation points, and the Singleton bound for linear codes
Reference graph
Works this paper leans on
-
[1]
K. Abdukhalikov, C. Ding, and G. K. Verma. Some constructions of non- generalized Reed-Solomon MDS codes.ArXiv:2506.04080, 2025
-
[2]
S. Ball. On large subsets of a finite vector space in which every subset of basis size is a basis.Journal of the European Mathematical Society, 14(3):733–748, 2012
work page 2012
-
[3]
S. Ball and M. Lavrauw. Arcs in finite projective spaces.EMS Surveys in Mathematical Sciences, 6(1-2):133–172, 2019
work page 2019
- [4]
- [5]
- [6]
-
[7]
V. R. Cadambe, C. Huang, and J. Li. Permutation code: Optimal exact-repair of a single failed node in MDS code based distributed storage systems.2011 IEEE International Symposium on Information Theory Proceedings, pages 1225–1229, 2011
work page 2011
-
[8]
A. R. Calderbank and P. W. Shor. Good quantum error-correcting codes exist. Physical review. A, Atomic, molecular, and optical physics, 54 2:1098–1105, 1995. 28
work page 1995
-
[9]
L. R. A. Casse and D. G. Glynn. The solution to Beniamino Segre’s problem Ir,q, r= 3, q= 2 h.Geom. Dedicata, 13(2):157–163, 1982
work page 1982
-
[10]
J. H. Conway and N. J. A. Sloane.Sphere packings, lattices and groups, volume 290 ofGrundlehren der mathematischen Wissenschaften. Springer-Verlag, New York, third edition, 1999
work page 1999
- [11]
-
[12]
S. H. Dau, W. Song, Z. Dong, and C. Yuen. Balanced sparsest generator matrices for MDS codes.2013 IEEE International Symposium on Information Theory, pages 1889–1893, 2013
work page 2013
-
[13]
S. H. Dau, W. Song, and C. Yuen. On the existence of MDS codes over small fields with constrained generator matrices.2014 IEEE International Symposium on Information Theory, pages 1787–1791, 2014
work page 2014
-
[14]
S. T. Dougherty, S. Mesnager, and P. Sol´ e. Secret-sharing schemes based on self-dual codes.2008 IEEE Information Theory Workshop, pages 338–342, 2008
work page 2008
-
[15]
D. G. Glynn. The non-classical 10-arc of PG(4, 9).Discret. Math., 59:43–51, 1986
work page 1986
- [16]
-
[17]
J. W. P. Hirschfeld.Projective geometries over finite fields. Oxford Mathematical Monographs. The Clarendon Press, Oxford University Press, New York, second edition, 1998
work page 1998
- [18]
-
[19]
J. I. Kokkala, D. S. Krotov, and P. R. J. ¨Osterg˚ ard. On the classification of MDS codes.IEEE Transactions on Information Theory, 61:6485–6492, 2014
work page 2014
-
[20]
J. Lavauzelle and J. Renner. Cryptanalysis of a system based on twisted Reed–Solomon codes.Designs, Codes and Cryptography, 88:1285 – 1300, 2019
work page 2019
-
[21]
Y. Li, Z. Sun, and S. Zhu. A family of linear codes that are either non-GRS MDS codes or NMDS codes.IEEE Transactions on Communications, 2025
work page 2025
- [22]
-
[23]
W. Liu, J. Luo, P. Wang, and D. Zhai. Column twisted Reed-Solomon codes as MDS codes.ArXiv:2507.08755, 2025. 29
work page internal anchor Pith review Pith/arXiv arXiv 2025
-
[24]
I. G. Macdonald.Symmetric Functions and Hall Polynomials. Oxford University Press, Oxford, 2nd edition, 1995
work page 1995
-
[25]
F. J. MacWilliams and N. J. A. Sloane.The Theory of Error-Correcting Codes. Elsevier, Amsterdam, The Netherlands, 1977
work page 1977
-
[26]
S. D. Marchi. Polynomials arising in factoring generalized vandermonde determi- nants: an algorithm for computing their coefficients.Mathematical and Computer Modelling, 34:271–281, 2001
work page 2001
-
[27]
D. Mirandola and G. Z´ emor. Critical pairs for the product singleton bound. IEEE Transactions on Information Theory, 61:4928–4937, 2015
work page 2015
-
[28]
R. M. Roth and A. Lempel. A construction of non-Reed-Solomon type MDS codes.IEEE Transactions on Information Theory, 35:655–657, 1989
work page 1989
-
[29]
K. Sakakibara and J. Taketsugu. Application of random relaying of partitioned MDS codeword block to persistent relay CSMA over random error channels.2013 5th International Congress on Ultra Modern Telecommunications and Control Systems and Workshops (ICUMT), pages 106–112, 2013
work page 2013
-
[30]
B. Segre. Curve razionali normali ek-archi negli spazi finiti.Annali di Matem- atica Pura ed Applicata, 39:357–378, December 1955
work page 1955
-
[31]
P. W. Shor. Scheme for reducing decoherence in quantum computer memory. Physical review. A, Atomic, molecular, and optical physics, 52 4:R2493–R2496, 1995
work page 1995
- [32]
- [33]
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.