XI-Code: A Family of Practical Lowest Density MDS Array Codes of Distance 4
Zhijie Huang, Hong Jiang, Ke Zhou, Chong Wang, Yuhong Zhao · IEEE Transactions on Communications · 2016
Designing the lowest density maximum-distance separable (MDS) array codes has gained much attention in recent years due to the optimal redundancy and minimum update penalty (lowest density) of such codes. However, the existing lowest density MDS array codes of distance 4 have extremely strict constraints on the code length, which makes them impractical. In particular, most of them require the code length to be p (or p - 1), where p is a prime that satisfies: i) 3|(p - 1) and ii) 2 is primitive in GF(p). In this paper, we propose a new family of the lowest density MDS array codes of distance 4, called XI-Code. It has the properties of: 1) being capable of correcting both triple erasures and a single error combined with one erasure; 2) having code length of either p or p + 1 with p being an odd prime number; 3) achieving optimality in encoding and update; and 4) achieving optimality in erasure decoding for certain erasure patterns and near optimality for other erasure patterns. It is worth mentioning that XI-Code is the first discovered family of the lowest density MDS array codes of distance 4 that supports the code length of p or p + 1 with p being an odd prime.