Explicit Constructions of High-Rate MDS Array Codes With Optimal Repair Bandwidth

Maximum distance separable (MDS) codes are optimal error-correcting codes in the sense that they provide the maximum failure tolerance for a given number of parity nodes. Suppose that an MDS code with <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula> information nodes and <inline-formula> <tex-math notation="LaTeX">$r=n-k$ </tex-math></inline-formula> parity nodes is used to encode data in a distributed storage system. It is known that if <inline-formula> <tex-math notation="LaTeX">$h$ </tex-math></inline-formula> out of the <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula> nodes are inaccessible and <inline-formula> <tex-math notation="LaTeX">$d$ </tex-math></inline-formula> surviving (helper) nodes are used to recover the lost data, then we need to download at least <inline-formula> <tex-math notation="LaTeX">$h/(d+h-k)$ </tex-math></inline-formula> fraction of the data stored in each of the helper nodes (Dimakis <italic>et al.</italic>, 2010 and Cadambe <italic>et al.</italic>, 2013). If this lower bound is achieved for the repair of any <inline-formula> <tex-math notation="LaTeX">$h$ </tex-math></inline-formula> erased nodes from any <inline-formula> <tex-math notation="LaTeX">$d$ </tex-math></inline-formula> helper nodes, we say that the MDS code has the <inline-formula> <tex-math notation="LaTeX">$(h,d)$ </tex-math></inline-formula>-optimal repair property. We study high-rate MDS array codes with the optimal repair property (also known as minimum storage regenerating codes, or MSR codes). Explicit constructions of such codes in the literature are only available for the cases where there are at most three parity nodes, and these existing constructions can only optimally repair a single node failure by accessing all the surviving nodes. In this paper, given any <inline-formula> <tex-math notation="LaTeX">$r$ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula>, we present two explicit constructions of MDS array codes with the <inline-formula> <tex-math notation="LaTeX">$(h,d)$ </tex-math></inline-formula>-optimal repair property for all <inline-formula> <tex-math notation="LaTeX">$h\le r$ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">$k\le d\le n-h$ </tex-math></inline-formula> simultaneously. Codes in the first family can be constructed over any base field <inline-formula> <tex-math notation="LaTeX">$F$ </tex-math></inline-formula> as long as <inline-formula> <tex-math notation="LaTeX">$|F|\ge sn$ </tex-math></inline-formula>, where <inline-formula> <tex-math notation="LaTeX">$s=\text {lcm}(1,2, {\dots },r)$ </tex-math></inline-formula>. The encoding, decoding, repair of failed nodes, and update procedures of these codes all have low complexity. Codes in the second family have the optimal access property and can be constructed over any base field <inline-formula> <tex-math notation="LaTeX">$F$ </tex-math></inline-formula> as long as <inline-formula> <tex-math notation="LaTeX">$|F|\ge n+1$ </tex-math></inline-formula>. Moreover, both code families have the optimal error resilience capability when repairing failed nodes. We also construct several other related families of MDS codes with the optimal repair property.