New upper bounds and constructions of multi-erasure locally recoverable codes (Q6107451): Difference between revisions

For a \([n,k,d]\) linear code \(C\) over \(\mathbb{F}_q\) we say that the \(i\)-th code symbol \(c_i,1\leq i\leq n\) has locality \(r\) if this symbol can be recovered by using at most \(r\) other code symbols. \(C\) is called a locally recoverable code (LRC) with recoverability \(r\) and is denoted by \((n,k,d,r)_q\) LRC. The code \(C\) is called an \((m, n, k; k_0, d_0, d)_q\) multi-erasure locally recoverable code (ME-LRC) if it consist of \(m \times n\) arrays such that: \begin{itemize} \item Each row in each array in \(C\) belongs to an \([n, k_0, d_0]\) linear code. \item Reading the symbols of \(C\) row-wise, \(C\) is an \([mn, k, d]\) linear code. \end{itemize} Know bounds on ME-LRCs are discussed and a new Cadambe-Mazumdar-like bound is presented. For an \((m, n, k; k_0, d_0, d)_q\) ME-LRC this new bound states: \[ d\leq \left( m+1-\lceil\frac{k}{k_0}\rceil\right)w^{(q)}_{\max}[n,k_0,d_0], \] where \(w^{(q)}_{\max}[n,k,d]\) is the largest possible weight of a codeword of a linear code over \(\mathbb{F}_q\) with length \(n,\) dimension \(k,\) and minimum distance \(d.\) Some useful propositions on linear codes achieving Griesmer bound are shown and later used for derivation of some bounds on the maximum weight and minimum distance of linear codes. A new upper bound of ME-LRCs is proposed and using linear codes achieving Griesmer bounds two constructions for some explicit ME-LRCs attaining the bound are shown.