pipette
ESEspañol

Extension of MDS Codes over Finite Fields

Puyin Wang, Jinquan Luo

Preprint

In the authors' words

In this paper, we investigate extending of non-Reed--Solomon(non-RS) MDS codes to 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 multiplications, compared with 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 , we obtain new MDS codes of increased lengths that remain inequivalent to Reed--Solomon codes. In particular, we construct codes over and , each with Schur-square dimension . Over , we obtain two inequivalent codes with Schur-square dimensions and , respectively. The latter is the dual of an extended code, demonstrating that the method also applies when . For these dimension-four codes, the Schur-square dimensions and exceed both that of RS code (Schur-square dimension ) and those of specific elliptic-curve and column-twisted Reed--Solomon families (Schur-square dimension ). Some of these parameters of non-RS MDS codes have not been reported before.

Main resultLimitation the authors admit

Appeared: Friday, October 23. arXiv. Preprint, not yet peer-reviewed.