A Tight Rate Bound and Matching Construction for Locally Recoverable Codes with Sequential Recovery From Any Number of Multiple Erasures
share
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 ≥ 3 and t. We do this by first deriving an upper bound on code rate and then going on to construct a 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.
READ FULL TEXT