New Systematic MDS Array Codes With Two Parities

Abstract

Row-diagonal parity (RDP) code is a classical $(k+2,~k)$ systematic maximum distance separable (MDS) array code with $k \leq L-1$ under sub-packetization level $l = L-1$ , where L is a prime integer. When $k = L-1$ , its encoding requires $2-{}\frac {2}{k}$ XORs per original data bit, which exactly achieves theoretical optimal lower bound. In this paper, we present three new constructions of $(k+2,~k)$ systematic MDS array codes. First, under sub-packetization level $l = 4$ , we novelly design a $(17,~15)$ array code ${\mathcal {C}}_{1}$ , where k can reach the largest possible value to satisfy the MDS property. Moreover, when $k \leq 7$ , the encoding complexity of its subcodes can exactly achieve the theoretical optimal $2-{}\frac {2}{k}$ XORs per original data bit, and likewise, the decoding complexity of the subcodes with $k \leq 4$ is also exactly optimal. Under sub-packetization level $l = L-1$ with certain primes L, the second construction yields an MDS array code ${\mathcal {C}}_{2}$ with $k \leq {}\frac {L(L-1)}{2}$ , and the encoding complexity of ${\mathcal {C}}_{2}$ is also exactly optimal for $k = L-1$ , $2L-3$ . Furthermore, based on bit permutation, the third MDS array code ${\mathcal {C}}_{3}$ is obtained with $k \leq L(L-1)$ under sub-packetization level $l = 2(L-1)$ with certain primes L. In particular, as an extension of ${\mathcal {C}}_{2}$ , ${\mathcal {C}}_{3}$ exactly achieves the optimal encoding complexity for $k = 2(2L-3)$ , which does not hold for other array codes in the literature.

Keywords

• Array code
• maximum distance separable (MDS) code
• encoding complexity
• update complexity
• decoding complexity