Variant Codes Based on A Special Polynomial Ring and Their Fast Computations

In this paper, we propose two new classes of binary array codes, termed V-ETBR and V-ESIP codes, by reformulating and generalizing the variant technique of deriving the well-known generalized row-diagonal parity~(RDP) codes from shortened independent parity~(IP) codes. The V-ETBR and V-ESIP codes are both based on binary parity-check matrices and are essentially variants of two classes of codes over a special polynomial ring (termed ETBR and ESIP codes in this paper). To explore the conditions that make the variant codes binary Maximum Distance Separable~(MDS) array codes that achieve optimal storage efficiency, this paper derives the connections between V-ETBR/V-ESIP codes and ETBR/ESIP codes. These connections are beneficial for constructing various forms of the variant codes. By utilizing these connections, this paper also explicitly presents the constructions of V-ETBR and V-ESIP MDS array codes with any number of parity columns $r$, along with their fast syndrome computations. In terms of construction, all proposed MDS array codes have an exponentially growing total number of data columns with respect to the column size, while alternative codes have that only with linear order. In terms of computation, the proposed syndrome computations make the corresponding encoding/decoding asymptotically require $\lfloor \lg r \rfloor+1$ XOR~(exclusive OR) operations per data bit, when the total number of data columns approaches infinity. This is also the lowest known asymptotic complexity in MDS codes.