Bounds on the Parameters of Locally Recoverable Codes
Authors:
Top Cited Papers
- 18 January 2016
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 62 (6) , 3070-3083
Abstract
A locally recoverable code (LRC code) is a code over a finite alphabet, such that every symbol in the encoding is a function of a small number of other symbols that form a recovering set. In this paper, we derive new finite-length and asymptotic bounds on the parameters of LRC codes. For LRC codes with a single recovering set for every coordinate, we derive an asymptotic Gilbert-Varshamov type bound for LRC codes and find the maximum attainable relative distance of asymptotically good LRC codes. Similar results are established for LRC codes with two disjoint recovering sets for every coordinate. For the case of multiple recovering sets (the availability problem), we derive a lower bound on the parameters using expander graph arguments. Finally, we also derive finite-length upper bounds on the rate and the distance of LRC codes with multiple recovering sets.Keywords
All Related Versions
Funding Information
- NSF (CCF1217894)
- NSF through the Directorate for Engineering (CCF1422955, CCF1217894, CCF1217245)
- Russian Science Foundation (14-50-00150)
This publication has 31 references indexed in Scilit:
- Contagious Sets in Expanders2014
- Repair Locality With Multiple Erasure ToleranceIEEE Transactions on Information Theory, 2014
- Explicit Maximally Recoverable Codes With LocalityIEEE Transactions on Information Theory, 2014
- A Family of Optimal Locally Recoverable CodesIEEE Transactions on Information Theory, 2014
- Optimal Locally Repairable Linear CodesIEEE Journal on Selected Areas in Communications, 2014
- Locally Decodable CodesFoundations and Trends® in Theoretical Computer Science, 2012
- Weight distribution and decoding of codes on hypergraphsAdvances in Mathematics of Communications, 2008
- Expander graph arguments for message-passing algorithmsIEEE Transactions on Information Theory, 2001
- A new upper bound on nonbinary block codesDiscrete Mathematics, 1990
- Fast Probabilistic Algorithms for Verification of Polynomial IdentitiesJournal of the ACM, 1980