Optimal Locally Repairable Codes Via Elliptic Curves

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.