TL;DR
This paper introduces novel constructions for Linear Complementary Dual (LCD) Maximum Distance Separable (MDS) codes that are not equivalent to the standard Reed-Solomon codes. These new "non-Reed-Solomon type" LCD MDS codes are built upon existing methods for twisted Reed-Solomon and Roth-Lempel codes, offering new algebraic structures with potential applications in secure communication and data storage.
What Problem Does This Paper Address?
Linear Complementary Dual (LCD) codes and Maximum Distance Separable (MDS) codes are both highly desirable in coding theory due to their strong algebraic properties and wide range of applications, from communication systems and data storage to quantum computing and cryptography. MDS codes offer the best possible error correction for a given length and dimension, while LCD codes have gained recent attention for their use in protecting against side-channel and fault injection attacks.
While many LCD MDS codes have been constructed using generalized Reed-Solomon (GRS) codes, the field is actively seeking new constructions that are not simply variations of GRS codes. Specifically, researchers are interested in codes that are "monomially inequivalent" to GRS codes, meaning they cannot be transformed into a GRS code through a simple matrix operation (multiplication by a monomial matrix). This paper addresses the challenge of constructing such "non-Reed-Solomon type" LCD MDS codes, particularly for Euclidean and Hermitian duals, and demonstrating their distinctness from existing constructions.
Methods
The authors build upon two key existing constructions:
- Twisted Reed-Solomon Codes: Introduced by Beelen et al. [3], these codes generalize standard Reed-Solomon codes. The paper leverages the conditions under which these twisted codes become MDS and then applies specific choices of parameters and field extensions to ensure they are also Euclidean or Hermitian LCD.
- Roth-Lempel Codes: Introduced by Roth and Lempel [20], these codes are known to be MDS and of non-Reed-Solomon type. The paper adapts these constructions to satisfy the LCD property, again by carefully selecting parameters and field properties.
The core methodology involves:
- Generator Matrix Construction: Designing specific generator matrices for twisted Reed-Solomon and Roth-Lempel codes.
- LCD Property Verification: Using the criterion that a code is Euclidean (or Hermitian) LCD if and only if the product of its generator matrix with its transpose (or conjugate transpose) is nonsingular (Lemma 2.3).
- MDS Property Assurance: Employing conditions from existing literature (e.g., Lemma 2.6, Lemma 2.7) that guarantee MDS properties for twisted Reed-Solomon codes under specific field and parameter choices.
- Non-Reed-Solomon Type Demonstration: Relying on the established fact that Roth-Lempel codes are inherently non-Reed-Solomon type, and for twisted Reed-Solomon codes, using conditions (like specific minor evaluations) that prove they are not monomially equivalent to RS codes (Lemma 2.7, Remark 2.8).
- Field Lifting: Utilizing field extensions (e.g., from $\mathbb{F}_q$ to $\mathbb{F}_{q^2}$) to construct codes with desired properties, as the LCD property is preserved under such lifting.
Datasets
Not discussed in the paper. The paper focuses on theoretical constructions and algebraic properties, not empirical evaluation on datasets.
Key Insights and Ideas
- Bridging Existing Constructions: The paper successfully bridges the gap between existing non-MDS-equivalent constructions (twisted Reed-Solomon) and known non-Reed-Solomon MDS codes (Roth-Lempel) to create LCD MDS codes of non-Reed-Solomon type.
- Systematic Construction: The work provides a systematic approach to finding these new codes by carefully selecting parameters for known code families and applying specific field properties.
- Distinctness from Prior Work: A crucial insight is the explicit demonstration that the newly constructed codes are not monomially equivalent to LCD codes constructed by the method of Carlet et al. [9], highlighting their novelty and algebraic diversity. This is achieved by analyzing the structure of their generator matrices.
- Dual Nature of LCD and MDS: The paper showcases how to combine the desirable properties of both LCD and MDS codes, often by leveraging specific field characteristics (like the existence of primitive elements and subgroup structures).
Key Results
The paper presents several new classes of Euclidean and Hermitian LCD MDS codes of non-Reed-Solomon type. Specific examples are provided for various finite fields (e.g., $\mathbb{F}_{81}$, $\mathbb{F}_{121}$, $\mathbb{F}_{25}$, $\mathbb{F}_{49}$) and code parameters.
- Euclidean LCD MDS Codes: Theorems 3.4 and 3.6 provide constructions for Euclidean LCD MDS codes of non-Reed-Solomon type based on twisted Reed-Solomon and Roth-Lempel codes, respectively. For instance, Theorem 3.4 guarantees a $[2k, k]_q$ Euclidean LCD MDS non-Reed-Solomon code under specific conditions on $q$, $k$, and field extensions.
- Hermitian LCD MDS Codes: Theorems 3.9 and 3.13 offer analogous constructions for Hermitian LCD MDS codes over $\mathbb{F}_{q^2}$.
- Examples: Concrete examples are given, such as a $[8, 4]_{81}$ Euclidean LCD MDS non-Reed-Solomon code derived from a twisted Reed-Solomon code (Example 3.3), and a $[10, 5]_{121}$ Hermitian LCD MDS non-Reed-Solomon code derived from a twisted Reed-Solomon code (Example 3.10).
Limitations and Future Work
- Monomial Equivalence: While the paper proves that its constructions are not monomially equivalent to Carlet et al.'s method, a comprehensive classification of all inequivalent LCD MDS codes of non-Reed-Solomon type remains an open problem.
- Parameter Specificity: The constructions often rely on specific conditions for field size ($q$), code dimension ($k$), and the existence of primitive elements or specific subgroup structures. Finding codes for arbitrary parameters might require further investigation.
- Practical Performance: The paper focuses on algebraic properties. Future work could explore the practical performance of these codes in terms of decoding complexity and error correction capabilities in real-world applications.
- Generalization: The paper primarily uses twisted Reed-Solomon and Roth-Lempel codes. Exploring other known families of MDS codes for LCD properties could yield further novel constructions.
Summary updated