text: Array codes have been widely employed in storage systems, such as Redundant Arrays of Inexpensive Disks (RAID). The row-diagonal parity (RDP) codes and EVENODD codes are two popular double-parity array codes. As the capacity of hard disks increases, better fault tolerance by using array codes with three or more parity disks is needed. Although many extensions of RDP codes and EVENODD codes have been proposed, the high decoding complexity is the main drawback of them. In this paper, we present a new construction for all families of EVENODD codes and RDP codes, and propose a unified form of them. Under this unified form, RDP codes can be treated as shortened codes of EVENODD codes. Moreover, an efficient decoding algorithm based on an LU factorization of Vandermonde matrix is proposed when the number of continuous surviving parity columns is no less than the number of erased information columns. The new decoding algorithm is faster than the existing algorithms when more than three information columns fail. The proposed efficient decoding algorithm is also applicable to other Vandermonde array codes. Thus the proposed MDS array code is practically very meaningful for storage systems that need higher reliability.
  @cite_13: In this paper, we propose an efficient interpolation-based systematic encoder for low-rate Blaum-Roth codes. Our algorithm is based upon an equivalent definition of [p, k] Blaum-Roth codes from the perspective of generator matrices. Moreover, applying the interpolation method first proposed by D.J.J. to the generator matrix, we then derive a formula to resolve the erasure-only decoding problem. Finally, we present a straightforward systematic encoder based on this formula. Compared to the encoders in [5] and [14], it is more efficient for low-rate codes.
  @cite_18: Proper data placement schemes based on erasure correcting codes are one of the most important components for a highly available data storage system. For such schemes, low decoding complexity for correcting (or recovering) storage node failures is essential for practical systems. In this paper, we describe a new coding scheme, which we call the STAR code, for correcting triple storage node failures (erasures). The STAR code is an extension of the double-erasure-correcting EVENODD code and a modification of the generalized triple-erasure-correcting EVENODD code. The STAR code is an Maximum Distance Separable (MDS) code and thus is optimal in terms of node failure recovery capability for a given data redundancy. We provide detailed STAR code decoding algorithms for correcting various triple node failures. We show that the decoding complexity of the STAR code is much lower than those of existing comparable codes; thus, the STAR code is practically very meaningful for storage systems that need higher reliability.
  @cite_26: Binary maximum distance separable (MDS) array codes are widely used in storage systems. EVENODD code and row-diagonal parity (RDP) code are two well-known binary MDS array codes with two parity columns. The Blaum–Bruck–Vardy (BBV) code is an extension of the double-erasure-correcting EVENODD code. It is known that the BBV code is always MDS for three parity columns, and sufficient conditions for up to eight parity columns to be MDS are also known. However, the MDS condition for more than eight parity columns is an open problem since then. In this letter, we study the MDS condition of BBV code and give a sufficient MDS condition of the BBV code with more than eight parity columns.
  @cite_4: We present a novel method, that we call EVENODD, for tolerating up to two disk failures in RAID architectures. EVENODD employs the addition of only two redundant disks and consists of simple exclusive-OR computations. This redundant storage is optimal, in the sense that two failed disks cannot be retrieved with less than two redundant disks. A major advantage of EVENODD is that it only requires parity hardware, which is typically present in standard RAID-5 controllers. Hence, EVENODD can be implemented on standard RAID-5 controllers without any hardware changes. The most commonly used scheme that employes optimal redundant storage (i.e., two extra disks) is based on Reed-Solomon (RS) error-correcting codes. This scheme requires computation over finite fields and results in a more complex implementation. For example, we show that the complexity of implementing EVENODD in a disk array with 15 disks is about 50 of the one required when using the RS scheme. The new scheme is not limited to RAID architectures: it can be used in any system requiring large symbols and relatively short codes, for instance, in multitrack magnetic recording. To this end, we also present a decoding algorithm for one column (track) in error. >
  @cite_9: The generalized RDP codes are identified as the most practical and efficient triple-erasure correcting MDS (maximum-distance separable) codes, since they can encode optimally and support arbitrary code length. However, none of the existing decoding algorithms for these codes is adequate in that their decoding complexity leaves a relatively large room for improvement. In this letter, we present an improved decoding algorithm for the generalized RDP codes. Compared with the existing decoding algorithms, the proposed algorithm has a much lower decoding complexity, which is very close to the theoretical lower bound.
  @cite_21: A new family of maximum distance separable (MDS) array codes is presented. The code arrays contain p information columns and r independent parity columns, each column consisting of p-1 bits, where p is a prime. We extend a previously known construction for the case r=2 to three and more parity columns. It is shown that when r=3 such extension is possible for any prime p. For larger values of r, we give necessary and sufficient conditions for our codes to be MDS, and then prove that if p belongs to a certain class of primes these conditions are satisfied up to r spl les 8. One of the advantages of the new codes is that encoding and decoding may be accomplished using simple cyclic shifts and XOR operations on the columns of the code array. We develop efficient decoding procedures for the case of two- and three-column errors. This again extends the previously known results for the case of a single-column error. Another primary advantage of our codes is related to the problem of efficient information updates. We present upper and lower bounds on the average number of parity bits which have to be updated in an MDS code over GF (2 sup m ), following an update in a single information bit. This average number is of importance in many storage applications which require frequent updates of information. We show that the upper bound obtained from our codes is close to the lower bound and, most importantly, does not depend on the size of the code symbols.
  @cite_1: 
  @cite_19: Row-Diagonal Parity (RDP) is a new algorithm for protecting against double disk failures. It stores all data unencoded, and uses only exclusive-or operations to compute parity. RDP is provably optimal in computational complexity, both during construction and reconstruction. Like other algorithms, it is optimal in the amount of redundant information stored and accessed. RDP works within a single stripe of blocks of sizes normally used by file systems, databases and disk arrays. It can be utilized in a fixed (RAID-4) or rotated (RAID-5) parity placement style. It is possible to extend the algorithm to encompass multiple RAID-4 or RAID-5 disk arrays in a single RDP disk array. It is possible to add disks to an existing RDP array without recalculating parity or moving data. Implementation results show that RDP performance can be made nearly equal to single parity RAID-4 and RAID-5 performance.
  @cite_23: 
  @cite_2: In P. Corbett et a. (2004), the authors present a row-diagonal parity scheme with two parity columns for a (p - 1) times (p + 1) array, p a prime, that recovers any two erased columns. The code minimizes the number of XORs at the encoding. It was left as an open problem generalizing this scheme to multiple parities. In this paper, we present such a generalization. In particular, when we have three parity columns, the new code recovers any three erased columns. Efficient encoding and decoding algorithms are presented
  @cite_5: 
  @cite_16: 
  @cite_10: An optimal family of array codes over GF(q) for correcting multiple phased burst errors and erasures, where each phased burst corresponds to an erroneous or erased column in a code array, is introduced. As for erasures, these array codes have an efficient decoding algorithm which avoids multiplications (or divisions) over extension fields, replacing these operations with cyclic shifts of vectors over GF(q). The erasure decoding algorithm can be adapted easily to handle single column errors as well. The codes are characterized geometrically by means of parity constraints along certain diagonal lines in each code array, thus generalizing a previously known construction for the special case of two erasures. Algebraically, they can be interpreted as Reed-Solomon codes. When q is primitive in GF(q), the resulting codes become (conventional) Reed-Solomon codes of length P over GF(q sup p-1 ), in which case the new erasure decoding technique can be incorporated into the Berlekamp-Massey algorithm, yielding a faster way to compute the values of any prescribed number of errors. >
  @cite_20: Data placement scheme based on the generalized EVENODD array code was one of the most important choices for data storage systems to tolerate failures. The efficiency of the erasure code was directly related to the number of XOR operations during the encoding and decoding. We provided an improved decoding algorithm of the generalized EVENODD array code for correcting various triple node failures. It showed that the decoding complexity of the new algorithm was much lower than those of the existing comparable algorithm, thus it made the generalized EVENODD array code more efficiency in storage systems.
summary: Huang and Xu @cite_18 extended the EVENODD codes to be STAR codes with three parity columns. The EVENODD codes were extended by Blaum, Bruck and Vardy @cite_21 @cite_1 for three or more parity columns, with the additional assumption that the multiplicative order of 2 mod @math is equal to @math . A sufficient condition for the extended EVENODD codes to be MDS with more than eight parity columns is given in @cite_26 . Goel and Corbett @cite_16 proposed the RTP codes that extend the RDP codes to tolerate three disk failures. Blaum @cite_2 generalized the RDP codes that can correct more than three column erasures and showed that the extended EVENODD codes and generalized RDP codes share the same MDS property condition. Blaum and Roth @cite_10 proposed Blaum-Roth codes, which are non-systematic MDS array codes constructed over a Vandermonde matrix. Some efficient systematic encoding methods for Blaum-Roth codes are given in @cite_10 @cite_23 @cite_13 . We call the existing MDS array codes in @cite_4 @cite_19 @cite_21 @cite_1 @cite_16 @cite_2 @cite_10 @cite_18 @cite_20 @cite_5 @cite_9 as Vandermonde MDS array codes, as their constructions are based on Vandermonde matrices.