A Generalization of Array Codes With Local Properties and Efficient Encoding/Decoding
Hanxu Hou, Yunghsiang Sam Han, Patrick P. C. Lee, You Wu, Guojun Han, Mario Blaum · IEEE Transactions on Information Theory · 2022
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$.