51. A Tight Rate Bound and Matching Construction for Locally Recoverable Codes With Sequential Recovery From Any Number of Multiple Erasures.
- Author
-
Balaji, S. B., Kini, Ganesh R., and Kumar, P. Vijay
- Subjects
PARITY-check matrix ,BINARY codes ,REGULAR graphs ,CIPHERS ,CONSTRUCTION - 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]
- Published
- 2020
- Full Text
- View/download PDF