Constructions of Optimal Cyclic $({r},{\delta })$ Locally Repairable Codes
Bin Chen, Shu‐Tao Xia, Jie Hao, Fang‐Wei Fu · IEEE Transactions on Information Theory · 2017
A code is said to be an r-local locally repairable code (LRC) if each of its coordinates can be repaired by accessing at most r other coordinates. When some of the r coordinates are also erased, the r-local LRC cannot accomplish the local repair, which leads to the concept of (r, δ)-locality. A q-ary [n, k] linear code C is said to have (r, δ)-locality (δ ≥ 2) if for each coordinate i, there exists a punctured subcode of C with support containing i, whose length is at most r+δ-1, and whose minimum distance is at least δ. The (r, δ)-LRC can tolerate δ-1 erasures in every local code (i.e., punctured subcode), which degenerates to an r-local LRC when δ = 2. A q-ary (r, δ) LRC is called optimal if it meets the singleton-like bound for (r, δ)-LRCs. A class of optimal q-ary cyclic r-local LRCs with lengths n | q - 1 were constructed by Tamo, Barg, Goparaju, and Calderbank based on the q-ary Reed-Solomon codes. In this paper, we construct a class of optimal q-ary cyclic (r, δ)-LRCs (δ ≥ 2) with length n | q - 1, which generalizes the results of Tamo et al. Moreover, we construct a new class of optimal q-ary cyclic r-local LRCs with lengths n | q + 1 and a new class of optimal q-ary cyclic (r, δ)-LRCs (δ ≥ 2) with lengths n | q + 1. The constructed optimal LRCs with length n = q + 1 have the best-known length for a given finite field with size q when the minimum distance is larger than 4.