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

Abstract

An (n,k) recoverable property array code is composed of m\times 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 m\times 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.