A Tight Rate Bound and Matching Construction for Locally Recoverable Codes with Sequential Recovery From Any Number of Multiple Erasures
| Autor: | Balaji, S. B., Kini, Ganesh R., Kumar, P. Vijay |
|---|---|
| Rok vydání: | 2018 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | By a locally recoverable code (LRC), we will in this paper, mean a linear code in which a given code symbol can be recovered by taking a linear combination of at most $r$ other code symbols with $r << k$. A natural extension is to the local recovery of a set of $t$ erased symbols. There have been several approaches proposed for the handling of multiple erasures. The approach considered here, is one of sequential recovery meaning that the $t$ erased symbols are recovered in succession, each time contacting at most $r$ other symbols for assistance in recovery. Under the constraint that each erased symbol be recoverable by contacting at most $r$ other code symbols, this approach is the most general and hence offers maximum possible code rate. We characterize the maximum possible rate of an LRC with sequential recovery for any $r \geq 3$ and $t$. We do this by first deriving an upper bound on code rate and then going on to construct a {\em binary} code that achieves this optimal rate. The upper bound derived here proves a conjecture made earlier relating to the structure (but not the exact form) of the rate bound. Our approach also permits us to deduce the structure of the parity-check matrix of a rate-optimal LRC with sequential recovery. The parity-check matrix in turn, leads to a graphical description of the code. The construction of a binary code having rate achieving the upper bound derived here makes use of this description. Interestingly, it turns out that a subclass of binary codes that are both rate and block-length optimal, correspond to graphs known as Moore graphs that are regular graphs having the smallest number of vertices for a given girth. A connection with Tornado codes is also made in the paper. Comment: To admin: Has overlaps with 1806.04474,1611.08561,1801.06794 . This is for submitting to the Journal |
| Databáze: | arXiv |
| Externí odkaz: |
|