New Constructions of <i>q</i> -Ary MDS Array Codes Derived From F _<i>q</i> [ <i>x</i> ]/ <i> x ^m </i> + λ and Their Efficient Erasure Encoding/Decoding

The <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">q</i>-ary maximum distance separable (MDS) array codes, especially <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">q</i> = 2<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">v</sup>, have important applications in the storage systems to prevent data loss. At now, almost all algebraic constructions of such codes are carried out over the quotient ring R<sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><i>m</i></sub> = F<sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><i>q</i></sub>[<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">x</i>]/⟨<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">x</i><sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">m</sup>+1⟩ or its subring F<sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><i>q</i></sub>[<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">x</i>]/⟨<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">x</i><sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">m−1</sup>+<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">x</i><sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">m−2</sup>+· · ·+1⟩. In this paper, we consider the construction of MDS array codes derived form R<sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><i>m</i>,λ</sub> = F<sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><i>q</i></sub>[<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">x</i>]/⟨<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">x</i><sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">m</sup> + λ⟩, where λ ∈ F<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">∗</sup> <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><i>q</i></sub> = F<sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><i>q</i></sub>\{0}, gcd(<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">m, q</i>) = 1. By giving λ-GCD Constraint of polynomials and the punctured λ-twisted circulant matrices, a generic construction and its extensions of such codes are presented. Under this framework, four new explicit constructions are also provided. Specifically, some low-density MDS array codes are obtained in Explicit Constructions I and I ′ . Explicit Constructions II and III provide long MDS array codes that can be applied in the large-scale storage systems. Explicit Construction IV gives MDS array codes both with the optimal repair bandwidth and the lowest update complexity, whose sub-packetization level is smaller than that of codes in [31]. In addition, by the LU factorization, a decoding method for erasures is obtained. For long codes, the syndromes can be computed fast. When the erased number ρ ≤ 3 (the most common errors in the storage systems), its computational complexity is asymptotically optimal. By an example, the new encoder possesses fewer exclusive ORs per data bit than that of MDS array codes constructed over R<sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><i>m</i></sub> in [29].