Some results on optimal locally repairable codes
Some results on optimal locally repairable codes
复制标题
DOI：
10.1109/isit.2016.7541337
复制
发表时间：
2016-07
期刊：
影响因子：
--
通讯作者：
Jie Hao;Shutao Xia;Bin Chen
中科院分区：
文献类型：
--
作者：
Jie Hao;Shutao Xia;Bin Chen
在线性码中，如果一个码符号可以通过访问最多r个其他码符号来修复，则称该码符号具有局部性r。对于（n，k，r）局部可修码（LRC），最小距离的界可能是著名的Singleton-like界和考虑域大小的Cadambe-Mazumdar界.本文从校验矩阵的角度研究了最优LRC的构造。首先，在线性码等价的意义下，找到所有满足Singleton-like界的最优二元LRC，即，除了所提出的4类LRC之外，没有其他具有最小距离d = n-k-rk/rk +2的二进制（n，k，r）LRC。然后提出了一类距离为4且具有任意局部性的二进制LRC，并证明了其在Cadambe-Mazumdar界下是最优的。此外，我们给出了一类满足Singleton-like界的最小距离为4的高速率最优q元LRC，而所需的域大小仅为q ≥ r - 1.最后，提出了从长最优LRC得到短最优LRC的几种方法。
In a linear code, a code symbol is said to have locality r if it can be repaired by accessing at most r other code symbols. For an (n, k, r) locally repairable codes (LRC), the most important bounds on minimum distances might be the well-known Singleton-like bound and the Cadambe-Mazumdar bound which takes the field size into account. In this paper, we study the constructions of optimal LRCs from the view of parity-check matrices. Firstly, all the optimal binary LRCs meeting the Singleton-like bound are found in the sense of equivalence of linear codes, i.e., except the proposed 4 classes of LRCs, there is no other binary (n, k, r) LRC with minimum distance d = n - k - ⌈k/r⌉+2. Then a class of binary LRCs with distance 4 and arbitrary locality is proposed and shown to be optimal with respect to the Cadambe-Mazumdar bound. Moreover, we give a class of high rate optimal q-ary LRCs meeting the Singleton-like bound with minimum distance 4 while the required field size is only q ≥ r - 1. Finally, several methods to obtain short optimal LRCs from long optimal LRCs are proposed at the end of this paper.