A Generalization of Array Codes With Local Properties and Efficient Encoding/Decoding

摘要

An $(n,k)$ recoverable property array code is composed of $mtimes n$ arrays such that any $k$ out of $n$ columns suffice to retrieve all the information symbols, where $n k$ . Note that maximum distance separable (MDS) array code is a special $(n,k)$ recoverable property array code of size $mtimes n$ with the number of information symbols being $km$ . Expanded-Blaum-Roth (EBR) codes and Expanded-Independent-Parity (EIP) codes are two classes of $(n,k)$ recoverable property array codes that can repair any one symbol in a column by locally accessing some other symbols within the column, where the number of symbols $m$ in a column is a prime number. By generalizing the constructions of EBR and EIP codes, we propose new $(n,k)$ recoverable property array codes, such that any one symbol can be locally recovered and the number of symbols in a column can be not only a prime number but also a power of an odd prime number. Also, we present an efficient encoding/decoding method for the proposed generalized EBR (GEBR) and generalized EIP (GEIP) codes based on the LU factorization of a Vandermonde matrix. We show that the proposed decoding method has less computational complexity than existing methods. Furthermore, we show that the proposed GEBR codes have both a larger minimum symbol distance and a larger recovery ability of erased lines for some parameters when compared to EBR codes. We also present a necessary and sufficient condition of enabling EBR codes to recover any $r$ erased lines of a slope for any parameter $r$ , which was an open problem. Moreover, we show that EBR codes can recover any $r$ consecutive erased lines of any slope for any parameter $r$ .