Title :
Optimal linear codes with a local-error-correction property
Author :
Prakash, N. ; Kamath, Govinda M. ; Lalitha, V. ; Kumar, P. Vijay
Author_Institution :
Dept. of ECE, Indian Inst. of Sci., Bangalore, India
Abstract :
Motivated by applications to distributed storage, Gopalan et al recently introduced the interesting notion of information-symbol locality in a linear code. By this it is meant that each message symbol appears in a parity-check equation associated with small Hamming weight, thereby enabling recovery of the message symbol by examining a small number of other code symbols. This notion is expanded to the case when all code symbols, not just the message symbols, are covered by such “local” parity. In this paper, we extend the results of Gopalan et. al. so as to permit recovery of an erased code symbol even in the presence of errors in local parity symbols. We present tight bounds on the minimum distance of such codes and exhibit codes that are optimal with respect to the local error-correction property. As a corollary, we obtain an upper bound on the minimum distance of a concatenated code.
Keywords :
Hamming codes; error correction codes; linear codes; parity check codes; Hamming weight; code symbols; concatenated code; distributed storage; erased code symbol; information-symbol locality; local parity symbols; local-error-correction property; message symbol; optimal linear codes; parity-check equation; Concatenated codes; Hamming weight; Linear code; Parity check codes; Silicon; Systematics; Upper bound;
Conference_Titel :
Information Theory Proceedings (ISIT), 2012 IEEE International Symposium on
Conference_Location :
Cambridge, MA
Print_ISBN :
978-1-4673-2580-6
Electronic_ISBN :
2157-8095
DOI :
10.1109/ISIT.2012.6284028