Back to Search
Start Over
A Tight Rate Bound and Matching Construction for Locally Recoverable Codes With Sequential Recovery From Any Number of Multiple Erasures.
- Source :
-
IEEE Transactions on Information Theory . Feb2020, Vol. 66 Issue 2, p1023-1052. 30p. - Publication Year :
- 2020
-
Abstract
- This paper considers the natural extension of locally recoverable codes (LRC) to the case of ${t} > 1$ erased symbols. While several approaches have been proposed for the handling of multiple erasures, in the approach considered here, the t erased symbols are recovered in succession, each time contacting at most r other symbols for assistance. Under the local-recovery constraint, this sequential approach is the most general and hence offers the maximum possible code rate. We characterize the rate of an LRC with sequential recovery for any ${r} \geq 3$ and any t, by first deriving an upper bound on the code rate and then constructing a binary code achieving this optimal rate. The upper bound derived here proves an earlier conjecture. Our approach permits us to deduce the structure of the parity-check matrix of a rate-optimal LRC with sequential recovery. The derived structure of parity-check matrix leads to a graphical description of the code used in code construction. A subclass of binary codes that are both rate and block-length optimal, are shown to correspond to certain regular graphs known as Moore graphs, that have the smallest number of vertices for a given girth. A connection with Tornado codes is also made. [ABSTRACT FROM AUTHOR]
- Subjects :
- *PARITY-check matrix
*BINARY codes
*REGULAR graphs
*CIPHERS
*CONSTRUCTION
Subjects
Details
- Language :
- English
- ISSN :
- 00189448
- Volume :
- 66
- Issue :
- 2
- Database :
- Academic Search Index
- Journal :
- IEEE Transactions on Information Theory
- Publication Type :
- Academic Journal
- Accession number :
- 141381308
- Full Text :
- https://doi.org/10.1109/TIT.2019.2958970