Bounds for Binary Linear Locally Repairable Codes via a Sphere-Packing Approach
Anyu Wang, Zhifang Zhang, Dongdai Lin · IEEE Transactions on Information Theory · 2019
For locally repairable codes (LRCs), Cadambe and Mazumdar derived the first field-dependent parameter bound, known as the C-M bound. However, the C-M bound depends on an undetermined parameter kopt(q)(n, d). In this paper, a sphere-packing approach is developed for upper bounding the parameter k for [n, k, d] linear LRCs with locality r. When restricted to the binary field, three upper bounds (i.e., Bound A, Bound B, and Bound C) are derived in an explicit form. More specifically, Bound A holds under the hypothesis that the local repair groups are disjoint and of equal size. Comparing with previous bounds obtained under the same hypothesis, Bound A either covers them as special cases or has an advantage due to its explicit form. Then, the hypothesis is removed in Bound B and Bound C. As the price for explicit form, Bound B specially holds for d ≥ 5 and Bound C for r = 2. Through specific comparisons, we show that Bound B and Bound C both tend to outperform the C-M bound, as n goes large. Moreover, a family of binary linear LRCs with d ≥ 6 attaining Bound B are constructed and later extended to a wider range of parameters by a shortening technique. Lastly, most of the bounds and constructions are extended to q-ary LRCs.