DocumentCode :
1780210
Title :
Codes with locality for two erasures
Author :
Prakash, N. ; Lalitha, V. ; Kumar, P.V.
Author_Institution :
Electr. Commun. Eng., Indian Inst. of Sci., Bangalore, India
fYear :
2014
fDate :
June 29 2014-July 4 2014
Firstpage :
1962
Lastpage :
1966
Abstract :
In this paper, we study codes with locality that can recover from two erasures via a sequence of two local, parity-check computations. By a local parity-check computation, we mean recovery via a single parity-check equation associated with small Hamming weight. Earlier approaches considered recovery in parallel; the sequential approach allows us to potentially construct codes with improved minimum distance. These codes, which we refer to as locally 2-reconstructible codes, are a natural generalization along one direction, of codes with all-symbol locality introduced by Gopalan et al, in which recovery from a single erasure is considered. By studying the generalized Hamming weights of the dual code, we derive upper bounds on the minimum distance of locally 2-reconstructible codes and provide constructions for a family of codes based on Turán graphs, that are optimal with respect to this bound. The minimum distance bound derived here is universal in the sense that no code which permits all-symbol local recovery from 2 erasures can have larger minimum distance regardless of approach adopted. Our approach also leads to a new bound on the minimum distance of codes with all-symbol locality for the single-erasure case.
Keywords :
Hamming codes; graph theory; parity check codes; Turán graphs; all-symbol local recovery; all-symbol locality; dual code; erasure recovery; local parity-check computations; locally 2-reconstructible codes; single parity-check equation; small Hamming weight; Frequency modulation; Hamming weight; Linear codes; Maintenance engineering; Silicon; Upper bound;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Information Theory (ISIT), 2014 IEEE International Symposium on
Conference_Location :
Honolulu, HI
Type :
conf
DOI :
10.1109/ISIT.2014.6875176
Filename :
6875176
Link To Document :
بازگشت