On the Locality of Codeword Symbols
On the Locality of Codeword Symbols
复制标题
DOI：
10.1109/tit.2012.2208937
复制
发表时间：
2011-06
影响因子：
2.5
通讯作者：
Parikshit Gopalan;Cheng Huang;Huseyin Simitci;S. Yekhanin
中科院分区：
文献类型：
--
作者：
Parikshit Gopalan;Cheng Huang;Huseyin Simitci;S. Yekhanin
考虑线性[n，k，d]q码C。我们说C的第i个坐标具有局部性r，如果这个坐标的值可以通过访问C的其他r个坐标来恢复。数据存储应用需要具有小冗余、信息坐标的低局部性、大距离和奇偶坐标的低局部性的代码。本文对这些参数之间的关系进行了深入的研究。我们建立了一个紧界的冗余n-k的消息长度，距离和信息坐标的局部性。我们把达到这个界限的码称为最优码。我们证明了一些结构定理的最佳码，这是特别强的小距离。这给出了码字长度、最坏情况距离和信息符号的局部性之间的权衡的相当完整的画面。然后，我们考虑的奇偶校验符号和擦除校正超出最坏情况下的最佳代码的距离的地方。使用我们的结构定理，我们得到了一个紧界的奇偶校验符号可能在这样的代码的一个广泛的类的参数设置的地方。我们证明，有一个良好的局部性和纠正擦除超出最小距离的能力之间的权衡。
Consider a linear [n,k,d]q code C. We say that the ith coordinate of C has locality r , if the value at this coordinate can be recovered from accessing some other r coordinates of C. Data storage applications require codes with small redundancy, low locality for information coordinates, large distance, and low locality for parity coordinates. In this paper, we carry out an in-depth study of the relations between these parameters. We establish a tight bound for the redundancy n-k in terms of the message length, the distance, and the locality of information coordinates. We refer to codes attaining the bound as optimal. We prove some structure theorems about optimal codes, which are particularly strong for small distances. This gives a fairly complete picture of the tradeoffs between codewords length, worst case distance, and locality of information symbols. We then consider the locality of parity check symbols and erasure correction beyond worst case distance for optimal codes. Using our structure theorem, we obtain a tight bound for the locality of parity symbols possible in such codes for a broad class of parameter settings. We prove that there is a tradeoff between having good locality and the ability to correct erasures beyond the minimum distance.