Source-linked AI summary
Optimal locally repairable codes via elliptic curves
Xudong Li, Liming Ma, Chaoping Xing
TL;DR
Optimal locally repairable codes meet the Singleton-type bound, but constructing q-ary examples longer than q+1 remains a challenge. This paper uses elliptic curves over finite fields to construct such codes. It reports code families with distance linear in length and locality up to 23.
Problem
The paper addresses the challenge of constructing q-ary optimal locally repairable codes with length greater than q+1.
Source: §1 · p. 1, §1.2 · p. 2Method
The construction uses elliptic-curve automorphisms and mixes functions from the fixed subfield and elliptic function field as evaluation functions for an algebraic-geometry-code subcode.
Source: §1.2 · p. 2Results
The paper reports optimal code families with distance linear in length and locality as large as 23, including theorem families with locality 2 and specified higher localities.
Source: §1.2 · pp. 2–3Takeaways & Limitations
The elliptic-curve construction yields q-ary optimal locally repairable codes whose lengths exceed q+1.
Source: §1.2 · p. 2The stated theorems assume q = p^a with even a and restrict p and locality r to listed cases; these conditions are used to find explicit maximal elliptic curves.
Source: §1.2 · pp. 2–3
Abstract
from arXiv · showhide
Constructing locally repairable codes achieving Singleton-type bound (we call them optimal codes in this paper) is a challenging task and has attracted great attention in the last few years. Tamo and Barg \cite{TB14} first gave a breakthrough result in this topic by cleverly considering subcodes of Reed-Solomon codes. Thus, $q$-ary optimal locally repairable codes from subcodes of Reed-Solomon codes given in \cite{TB14} have length upper bounded by $q$. Recently, it was shown through extension of construction in \cite{TB14} that length of $q$-ary optimal locally repairable codes can be $q+1$ in \cite{JMX17}. Surprisingly it was shown in \cite{BHHMV16} that, unlike classical MDS codes, $q$-ary optimal locally repairable codes could have length bigger than $q+1$. Thus, it becomes an interesting and challenging problem to construct $q$-ary optimal locally repairable codes of length bigger than $q+1$. In the present paper, we make use of rich algebraic structures of elliptic curves to construct a family of $q$-ary optimal locally repairable codes of length up to $q+2\sqrt{q}$. It turns out that locality of our codes can be as big as $23$ and distance can be linear in length.
1. Introduction
The introduction frames optimal locally repairable codes as codes meeting the Singleton-type bound and asks how to construct them with lengths beyond q+1. It presents elliptic-curve constructions, states two theorem families, and outlines the paper’s progression from preliminaries to explicit constructions and proofs.
1.1. Known results.
- Earlier constructions faced restrictions on locality, length, or alphabet size, while some produced q-ary optimal codes longer than q+1.The cited Reed-Solomon-based construction has locality conditions; its extension permits more flexibility and length q+1, and a separate work showed lengths exceeding q+1.Source: §1.1 · p. 2
1.2. Our main results.
- The paper uses elliptic curves over finite fields to construct q-ary optimal locally repairable codes with lengths greater than q+1.It takes a subgroup of the curve’s automorphism group, uses functions from the fixed subfield and elliptic function field as evaluation functions, and obtains a subcode of an algebraic geometry code.Source: §1.2 · p. 2
- Theorem 1.1 gives optimal q-ary codes with length n = 3ℓ, dimension k = 2t + 1, distance d = n − 3t, and locality 2 for specified q.The theorem requires q = p^a with even a and p = 3 or p ≡ 2 (mod 3).Source: §1.2 · pp. 2–3
- Theorem 1.2 gives optimal q-ary codes with length n = (r + 1)ℓ, dimension k = r(t−1) + 1, and distance d = n−(t−1)(r + 1) for specified r and p.The stated cases include r = 3, 5, 7, or 11, with prime conditions listed in the theorem.Source: §1.2 · pp. 2–3
- The paper reports that its codes can have distance linear in length and locality as large as 23.The introduction contrasts this with earlier codes exceeding q+1, which had small distance and locality.Source: §1.2 · p. 3
1.3. Organization of the paper.
- The paper introduces code and elliptic-curve preliminaries, constructs maximal and minimal elliptic curves with specified automorphism groups, then builds codes and proves the main theorems.Source: §1.3 · p. 3
2. Preliminaries
This section establishes the coding and function-field tools used to construct locally repairable codes from elliptic curves. It covers locality, elliptic-curve structure, field extensions and automorphisms, and algebraic-geometry code evaluation.
2.1. Locally repairable codes.
- Locality r means each coordinate can be recovered from at most r other coordinates; optimality here means attaining the Singleton-type bound.The paper focuses on linear codes over Fq, with length, dimension, distance, and locality as parameters.Source: §2.1 · pp. 3–4
2.2. Elliptic curves over finite fields.
- An elliptic curve’s rational points correspond to rational places, and a curve is maximal or minimal when its point count reaches the respective Hasse-Weil bound.The text also relates rational points to the zero divisor class group and introduces the curve’s L-polynomial and zeta function.Source: §2.2 · pp. 4–5
2.3. Extension theory of function fields.
- For a separable function-field extension, Riemann-Roch spaces supply finite-dimensional vector spaces, while a subgroup of automorphisms defines a fixed subfield.A place splits completely when its images under the subgroup’s automorphisms are pairwise distinct.Source: §2.3 · p. 6
2.4. Automorphism groups of elliptic curves.
- For an elliptic curve E/Fq, |Aut(E)| divides 24; if G ≤ Aut(E/Fq) fixes O and |G| = r + 1 for positive r, at most r + 2 other rational places ramify in E/E^G.Source: §2.4 · p. 7
2.5. Algebraic geometry codes.
- An algebraic-geometry code evaluates functions in L(G) at distinct rational places, and its subcodes inherit the distance lower bound n − deg(G).The code dimension equals dim_Fq L(G); for a subcode defined by V, its dimension is dim_Fq V.Source: §2.5 · p. 9
3. Maximal and minimal elliptic curves
This section supplies explicit maximal and minimal elliptic curves for later code constructions. It gives extension-field criteria and examples with specified automorphism-group sizes.
Maximal and minimal curves over extensions
- A maximal elliptic curve remains maximal over Fq^s exactly when s is odd, and is minimal there when s is even; a minimal curve remains minimal for every s.The section uses these extension-field rules to obtain curves over fields with even extension degree.Source: §3 · p. 9
Explicit maximal elliptic curves
- For every even a, a maximal curve over F2^a of the form y2 + y = x3 + γ can be chosen with automorphism group size 24.When a ≡ 0 (mod 4), the construction uses a twist of a minimal curve; when a ≡ 2 (mod 4), it uses y2 + y = x3.Source: §3 · p. 10
- For p ≡ 3 (mod 4) and even a, the section gives maximal curves y2 = x3 + θ2x with automorphism-group size 4 for p ≠ 3 and 12 for p = 3.For odd p ≠ 2 with p ≡ 2 (mod 3), it also gives maximal curves y2 = x3 + θ3 with automorphism-group size 6.Source: §3 · pp. 10–11
4. Construction of locally repairable codes via elliptic curves
The constructions use elliptic-curve automorphisms and evaluation functions to build locally repairable codes that attain the Singleton-type bound. Separate constructions cover locality 2 and odd localities 3, 5, 7, 11, and 23.
4.1. A general construction via automorphism groups.
- The evaluation functions lie in a space of dimension rt − (r − 1), with distance at least n − deg(D) when the divisor conditions hold.The evaluation points are grouped into fibers of size r + 1; values at any one point are recoverable from the other r values in its group.Source: §4.1 · p. 12
- The general construction yields optimal q-ary codes with length n = ℓ(r + 1), dimension k = rt − r + 1, distance d = n − (t − 1)(r + 1), and locality r.It selects evaluation points in split fibers of an elliptic-curve function-field extension and combines functions from the fixed subfield and the elliptic function field.Source: §4.1 · pp. 11, 12, 14, 15
4.2. Locality r = 2.
- If E/Fq is an elliptic curve whose automorphism group contains a subgroup of order 3 and ℓ rational places of F split completely in E/F, then for 0 ≤ t < ℓ there exists a q-ary [3ℓ, 2t+1, 3ℓ−3t] locally repairable code with locality 2.Source: §4.2 · p. 15
- For locality 2, the paper identifies cases with ℓ up to q + 2√q, yielding code lengths up to three times that value.The stated bounds on ℓ differ by characteristic and curve case; examples include q = 64 with ℓ ≤ 26 and q = 81 with ℓ ≤ 33.Source: §4.2 · pp. 16–17
4.3. Locality r = 3, 5, 7, 11 or 23.
- For q = 64, the construction gives an optimal 64-ary locally repairable code of length 80, dimension 3t + 2, distance 80 − 4(t − 1), and locality 3 for every 1 ≤ t ≤ 20.Source: §4.3 · p. 18