MDS codes extended to longer lengths with efficient new algorithm
Extension of MDS Codes over Finite Fields
Information Theory
Summary
This work finds a way to make certain special error-correcting codes, called MDS codes, longer while keeping their unique structure different from common Reed–Solomon codes. The authors created a practical step-by-step method that does this extension faster than previously possible. They tested their method on several known kinds of these codes and successfully produced new longer codes with properties not seen before. These extended codes could be useful for data transmission and storage where very reliable error correction is needed.
What this means in practice
- •For data storage engineers: Design longer error-correcting codes that maintain strong protection while differing from Reed–Solomon codes, improving flexibility in storage system error resilience.
- •For communications system developers: Implement extended MDS codes with novel parameters to enhance error correction in high-reliability data transmissions over small finite fields.
Authors
Puyin Wang, Jinquan Luo
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(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.