Paper detail

On MDS Condition and Erased Lines Recovery of Generalized Expanded-Blaum-Roth Codes and Generalized Blaum-Roth Codes

Generalized Expanded-Blaum-Roth (GEBR) codes [1] are designed for large-scale distributed storage systems that have larger recoverability for single-symbol failures, multi-column failures and multi-row failures, compared with locally recoverable codes (LRC). GEBR codes encode an $α\times k$ information array into a $pτ\times (k+r)$ array such that lines of slope $i$ with $0\leq i\leq r-1$ have even parity and each column contains $pτ-α$ local parity symbols, where $p$ is an odd prime and $k+r\leq pτ$. Necessary and sufficient conditions for GEBR codes to be $(n,k)$ recoverable (i.e., any $k$ out of $n=k+r$ columns can retrieve all information symbols) are given in [2] for $α=(p-1)τ$. However, the $(n,k)$ recoverable condition of GEBR codes is unknown when $α<(p-1)τ$. In this paper, we present the $(n,k)$ recoverable condition for GEBR codes for $α< (p-1)τ$. In addition, we present a sufficient condition for enabling GEBR codes to recover some erased lines of any slope $i$ ($0\leq i\leq pτ-1$) for any parameter $r$ when $τ$ is a power of $p$. Moreover, we present the construction of Generalized Blaum-Roth (GBR) codes that encode an $α\times k$ information array into an $α\times (k+r)$ array. We show that GBR codes share the same MDS condition as the $(n,k)$ recoverable condition of GEBR codes, and we also present a sufficient condition for GBR codes to recover some erased lines of any slope $i$ ($0\leq i\leq α-1$).