Optimal locally repairable codes via elliptic curves

Xudong Li, Liming Ma, Chaoping Xing

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 \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.
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},
}

Loading related content...

Figure