Optimal Locally Repairable Codes Via Elliptic Curves

Xudong Li, Liming Ma, Chaoping Xing

TL;DR

This paper introduces a novel method for constructing optimal locally repairable codes (LRCs) using the rich algebraic structures of elliptic curves. These new codes achieve lengths exceeding the typical bound of $q+1$ (where $q$ is the alphabet size), offering improved efficiency for distributed storage systems and other applications.

What Problem Does This Paper Address?

In distributed storage systems, data is often encoded into blocks, and the ability to recover lost data efficiently is crucial. Locally Repairable Codes (LRCs) are a class of error-correcting codes designed for this purpose. An LRC with "locality $r$" means that a single lost data block can be reconstructed by accessing at most $r$ other blocks. A key goal in coding theory is to construct LRCs that are "optimal," meaning they achieve the best possible trade-off between code length ($n$), number of information symbols ($k$), minimum distance ($d$), and locality ($r$). This optimal trade-off is often described by the Singleton-type bound: $d \le n - k - \lfloor k/r \rfloor + 2$.

While significant progress has been made, constructing optimal LRCs with lengths greater than $q+1$ has remained a challenging open problem. Previous constructions were often limited to lengths up to $q$ or $q+1$, or required very large alphabet sizes, making them impractical. This paper aims to bridge this gap by developing a new construction for optimal LRCs with lengths exceeding $q+1$.

Methods

The core of this paper's contribution lies in leveraging the sophisticated mathematical properties of elliptic curves over finite fields. The authors construct LRCs by:

  • Utilizing Elliptic Curve Function Fields: They consider an elliptic curve $E$ defined over a finite field $\mathbb{F}_q$ and its associated function field $\mathbb{F}_q(E)$.
  • Exploiting Automorphism Groups: They analyze the automorphism groups of these elliptic curves. These groups, when acting on the function field, define subfields.
  • Constructing Subcodes of Algebraic Geometry Codes: By carefully selecting rational points on the elliptic curve and using elements from the function field (specifically, from Riemann-Roch spaces), they define subcodes of algebraic geometry codes. These subcodes are then shown to be optimal locally repairable codes.
  • Leveraging Maximal/Minimal Elliptic Curves: The construction relies on finding specific "maximal" or "minimal" elliptic curves over finite fields, which have a large number of rational points, a property directly related to the code length.

Datasets

Not discussed in the paper. The paper focuses on theoretical constructions rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Elliptic Curves as a Rich Source for Code Construction: The paper demonstrates that the intricate algebraic structure of elliptic curves provides a powerful framework for designing codes with desirable properties, particularly for achieving lengths beyond traditional limits.
  • Automorphism Groups Dictate Locality: The size and structure of the automorphism group of an elliptic curve directly influence the possible values of locality ($r$) for the constructed LRCs. This allows for a systematic way to control the locality parameter.
  • Bridging the Gap Beyond $q+1$: The most significant insight is the successful construction of optimal LRCs with lengths up to $q + 2\sqrt{q}$, significantly extending the known bounds and opening new avenues for practical code design.
  • Locality up to 23: The construction allows for surprisingly high locality values, reaching up to 23, which is a substantial improvement for applications requiring robust local repair capabilities.

Key Results

The paper presents two main theorems:

  • Theorem 1.1: Constructs $q$-ary optimal locally repairable codes with locality 2 and length up to $n = 3l$, where $l$ can be as large as $\frac{q+2\sqrt{q}}{3}$. The distance is $d = n - 3t$, and the code has $k = 2t+1$ information symbols. This theorem is proven using specific elliptic curves and their automorphism groups.
  • Theorem 1.2: Establishes the existence of $q$-ary optimal locally repairable codes with odd locality $r$ (specifically $r \in \{3, 5, 7, 11, 23\}$) and length $n = l(r+1)$, where $l$ is related to the number of rational points on the curve. The code has $k = rt - (r-1)$ information symbols and distance $d \ge n - (t-1)(r+1)$.

Limitations and Future Work

  • Specific Field Conditions: While the general framework applies broadly, the explicit constructions of maximal/minimal elliptic curves often rely on specific conditions for the prime $p$ and the exponent $a$ in $q=p^a$ (e.g., $p=2, 3$, or $p \equiv 2, 3 \pmod 4$). Extending these constructions to all $q$ might require further investigation.
  • Parameter Optimization: The theorems provide existence results for certain parameters. Further work could focus on optimizing the parameters ($l, t$) to achieve specific code lengths and rates for given $q$ and $r$.
  • Practical Implementation: While the theoretical results are significant, the practical implementation of codes based on elliptic curves can be computationally intensive. Future research might explore more efficient algorithms for code construction and decoding.
  • Generalizing Locality: The construction for odd locality relies on specific properties of automorphism groups. Exploring more general methods for achieving arbitrary odd localities could be a future direction.

Summary updated

Abstract

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 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 by Tamo and Barg have length upper bounded by q. Recently, it was shown through extension of construction by Tamo and Barg that length of q-ary optimal locally repairable codes can be q+1 by Jin et al.. Surprisingly it was shown by Barg et al. 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 this 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√(q). It turns out that locality of our codes can be as big as 23 and distance can be linear in length.
BibTeX
@article{li2018optimal,
  author = {Xudong Li and Liming Ma and Chaoping Xing},
  title = {{Optimal Locally Repairable Codes Via Elliptic Curves}},
  journal = {IEEE Transactions on Information Theory},
  year = {2018},
  doi = {10.1109/tit.2018.2844216},
}
Figure