Source-linked AI summary
Euclidean and Hermitian LCD MDS codes
Claude Carlet, Sihem Mesnager, Chunming Tang, Yanfeng Qi
TL;DR
The paper addresses the limited understanding of LCD MDS code existence, especially across lengths and dimensions. It develops Euclidean and Hermitian constructions using small dimension or codimension, self-orthogonal codes, and generalized Reed-Solomon codes, and completely resolves the Euclidean case for the stated parameters.
Problem
The paper studies the existence of q-ary LCD MDS codes for various lengths and dimensions, an area with relatively few results despite the importance of LCD and MDS codes.
Method
The authors construct Euclidean and Hermitian LCD MDS codes using small-dimension or small-codimension codes, self-orthogonal codes, and generalized Reed-Solomon codes.
Results
For q>3, a q-ary [n,k] Euclidean LCD MDS code exists whenever 0≤k≤n≤q+1, and also when q=2^m, n=q+2, and k=3 or q−1.
Takeaways & Limitations
The paper completely determines Euclidean LCD MDS existence for the known MDS parameters and provides new Euclidean and Hermitian LCD MDS code classes.
Abstract
from arXiv · showhide
Linear codes with complementary duals (abbreviated LCD) are linear codes whose intersection with their dual is trivial. When they are binary, they play an important role in armoring implementations against side-channel attacks and fault injection attacks. Non-binary LCD codes in characteristic 2 can be transformed into binary LCD codes by expansion. On the other hand, being optimal codes, maximum distance separable codes (abbreviated MDS) have been of much interest from many researchers due to their theoretical significant and practical implications. However, little work has been done on LCD MDS codes. In particular, determining the existence of $q$-ary $[n,k]$ LCD MDS codes for various lengths $n$ and dimensions $k$ is a basic and interesting problem. In this paper, we firstly study the problem of the existence of $q$-ary $[n,k]$ LCD MDS codes and completely solve it for the Euclidean case. More specifically, we show that for $q>3$ there exists a $q$-ary $[n,k]$ Euclidean LCD MDS code, where $0\le k \le n\le q+1$, or, $q=2^{m}$, $n=q+2$ and $k= 3 \text{or} q-1$. Secondly, we investigate several constructions of new Euclidean and Hermitian LCD MDS codes. Our main techniques in constructing Euclidean and Hermitian LCD MDS codes use some linear codes with small dimension or codimension, self-orthogonal codes and generalized Reed-Solomon codes.
I. INTRODUCTION
The paper studies the existence and construction of Euclidean and Hermitian LCD MDS codes, motivated by the applications of LCD codes and the optimality of MDS codes. It completely determines the Euclidean existence problem for the stated MDS parameters and develops several construction techniques.
- Motivation: LCD codes have applications in storage, communications, consumer electronics, cryptography, side-channel protection, and fault-injection protection.Non-binary LCD codes in characteristic 2 can be transformed into binary LCD codes by expansion.
- Motivation: The central problem is determining whether q-ary LCD MDS codes exist for various lengths n and dimensions k.MDS codes combine the complementary-dual property with optimal error-correcting and detecting capabilities.
- Related work: Prior work established several sufficient conditions for Euclidean LCD MDS codes, while the Euclidean problem had previously been completely solved only for even q.The introduction summarizes conditions involving q, n, k, divisibility, and parity for the odd-q case.
- Contributions: The paper uses linear codes with small dimension or codimension, self-orthogonal codes, and generalized Reed-Solomon codes to construct LCD MDS codes.It presents constructions for both Euclidean and Hermitian LCD MDS codes.
- Organization: The paper is organized around preliminaries, Euclidean LCD constructions and existence, and Hermitian LCD MDS constructions.The Euclidean results are used to completely determine the Euclidean existence problem for the known MDS parameters.
II. PRELIMINARIES
The preliminaries define finite-field notation, duality, self-orthogonality, LCD codes, and MDS codes. They also state matrix criteria for these properties and characterize MDS codes through generator-matrix column independence.
- Basic notation: An [n,k,d] code has length n, dimension k, and minimum distance d, while n−k is its codimension.The paper works over finite fields F_q and uses Euclidean and Hermitian dual codes.
- MDS codes: A code is MDS when it meets the Singleton bound, and its dual is then also MDS.Equivalently, every k columns of a generator matrix are linearly independent, so any k codeword symbols form an information set.
- LCD codes: An LCD code satisfies C∩C⊥={0}, while a Hermitian LCD code satisfies C∩C⊥H={0}.The distinction is made between Euclidean LCD codes over F_q and Hermitian LCD codes over F_q2.
- Matrix criteria: Euclidean or Hermitian LCD status is characterized by the corresponding generator-matrix Gram matrix being nonsingular.The paper also notes that any linear code is equivalent to one generated by a matrix of the form [I_k : P].
- Self-orthogonality: Euclidean or Hermitian self-orthogonality is characterized by the corresponding generator-matrix Gram matrix being zero.For a generator matrix G, the relevant conditions use G G^T or G Ḡ^T, respectively.
III. EXISTENCE AND CONSTRUCTIONS OF EUCLIDEAN LCD MDS CODES
The section completely determines Euclidean LCD MDS existence for lengths up to q+1 and gives constructions extending to selected q+2 cases. It develops transformations, self-orthogonal-code methods, and explicit matrix constructions to obtain new LCD MDS parameters.
- General constructions: LCD-preserving transformations produce codes with the same parameters as a given code under the stated dimension or codimension bounds.Theorem 3.3 preserves the parameters and minimum-distance behavior through a scaled generator-matrix construction and duality.
- Explicit constructions: Further matrix constructions provide LCD MDS codes with parameters [2k,k], [2k+1,k], and [2k+2,k] when k divides q−1 and k<q−1.The constructions verify MDS through nonsingular k×k submatrices and LCD status through nonsingular Gram matrices or explicit parameter choices.
- Existence classification: For q>3, Euclidean LCD MDS codes exist for every 0≤k≤n≤q+1, and also for q=2^m with n=q+2 and k=3 or q−1.The theorem provides the section’s complete existence statement in the stated parameter ranges.
IV. EXISTENCE AND CONSTRUCTION OF HERMITIAN LCD MDS CODES
The paper develops constructions of Hermitian LCD MDS codes using generator-matrix criteria, self-orthogonal codes, and field-element transformations. It obtains broad existence results for dimensions or codimensions below q−1, additional odd-q lengths, and q=2^m length q+2 cases.
- The constructions transform self-orthogonal codes into Hermitian LCD codes by selecting α outside a specified exceptional set or spectrum.
- A generator-matrix construction produces [2k], [2k + 1, k], and [2k + 2, k] Hermitian LCD MDS codes under the stated odd-q divisibility assumptions.
- For odd q, the constructions yield Hermitian LCD MDS codes with parameters [2k, k], [2k + 1, k], and [2k + 2, k] under divisibility conditions on k.
- Hermitian LCD MDS codes exist for n ≤ q + 1 when k ≤ q − 2 or n − k ≤ q − 2.
- When q = 2^m ≥ 8, Hermitian LCD MDS codes exist for n = q + 2 and k = 3 or k = q − 1.
V. CONCLUDING REMARKS
The paper constructs Euclidean and Hermitian LCD MDS codes and fully classifies the Euclidean existence range stated in the paper. Hermitian existence remains open for all q > 3 and 0 ≤ k ≤ n ≤ q^2 + 1.
- The paper proves that q-ary Euclidean LCD MDS codes exist for every q > 3 and 0 ≤ k ≤ n ≤ q + 1.
- It also presents secondary Euclidean and Hermitian constructions based on small dimension or codimension, self-orthogonal codes, and generalized Reed-Solomon codes.
- Existence of q^2-ary Hermitian LCD MDS codes for all q > 3 and 0 ≤ k ≤ n ≤ q^2 + 1 remains open.