Explicit Maximally Recoverable Codes With Locality

被引：105

作者：

Gopalan, Parikshit ^{[1
]}

Huang, Cheng ^{[1
]}

Jenkins, Bob ^{[1
]}

Yekhanin, Sergey ^{[1
]}

机构：

[1] Microsoft Corp, Redmond, WA 98052 USA

来源：

IEEE TRANSACTIONS ON INFORMATION THEORY | 2014年 / 60卷 / 09期

关键词：

Codes with locality; maximally recoverable codes;

D O I：

10.1109/TIT.2014.2332338

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

Consider a systematic linear code where some (local) parity symbols depend on few prescribed symbols, whereas other (heavy) parity symbols may depend on all data symbols. Such codes have been studied recently in the context of erasure coding for data storage, where the local parities facilitate fast recovery of any single symbol when it is erased, whereas the heavy parities provide tolerance to a large number of simultaneous erasures. A code as above is maximally recoverable, if it corrects all erasure patterns, which are information theoretically correctable given the prescribed dependence relations between data symbols and parity symbols. In this paper, we present explicit families of maximally recoverable codes with locality. We also initiate the general study of the tradeoff between maximal recoverability and alphabet size.

引用

页码：5245 / 5256

页数：12

共 22 条

[1]

[Anonymous], 1978, The Theory of Error-Correcting Codes

[2] On sets of vectors of a finite vector space in which every subset of basis size is a basis II [J].