Bounds on the Size of Locally Recoverable Codes
Bounds on the Size of Locally Recoverable Codes
复制标题
DOI：
10.1109/tit.2015.2477406
复制
发表时间：
2015-09
影响因子：
2.5
通讯作者：
V. Cadambe;A. Mazumdar
中科院分区：
文献类型：
--
作者：
V. Cadambe;A. Mazumdar
在局部可恢复或可修复的代码中，码字的任何符号可以通过仅阅读少量（恒定）其它符号来恢复。本地可恢复性的概念在分布式存储领域非常重要，其中最常见的错误事件是单个存储节点故障（擦除）。一个共同的目标是通过从尽可能少的其他存储节点下载数据来修复节点。在这篇文章中，我们根据码的长度、大小和局部性来限制码的最小距离。与前面的界限不同，我们的界限来自一个非常简单的分析，并取决于所使用的字母表的大小。事实证明，二进制单纯形码满足我们的界限与平等，因此，单纯形码是第一个例子的最佳二进制局部可修复的代码家庭。我们还提供了基于随机编码和级联码的可扩展性结果，这些结果在数值上被验证为接近我们的界限。
In a locally recoverable or repairable code, any symbol of a codeword can be recovered by reading only a small (constant) number of other symbols. The notion of local recoverability is important in the area of distributed storage where a most frequent error-event is a single storage node failure (erasure). A common objective is to repair the node by downloading data from as few other storage nodes as possible. In this paper, we bound the minimum distance of a code in terms of its length, size, and locality. Unlike the previous bounds, our bound follows from a significantly simple analysis and depends on the size of the alphabet being used. It turns out that the binary Simplex codes satisfy our bound with equality; hence, the Simplex codes are the first example of an optimal binary locally repairable code family. We also provide achievability results based on random coding and concatenated codes that are numerically verified to be close to our bounds.