{'fraction_non_alphanumeric': 0.06441020459712049, 'fraction_numerical': 0.024659004799191715, 'mean_word_length': 3.5461461174106503, 'pattern_counts': {'":': 0, '<': 42, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 42, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Partial-MDS Codes and their Application to RAID Type of Architectures

A family of codes with a natural two-dimensional structure is presented, inspired by an application of RAID type of architectures whose units are solid state drives (SSDs). Arrays of SSDs behave differently to arrays of hard disk drives (HDDs), since hard errors in sectors are common and traditional RAID approaches (like RAID 5 or RAID 6) may be either insufficient or excessive. An efficient solution to this problem is given by the new codes presented, called partial-MDS (PMDS) codes.


Introduction
Consider an array of, say, n storage devices. Each storage device contains a (large) number of sectors, each sector protected by an error-correcting code (ECC) dealing with the most common errors in the media. However, it may occur that one or more of the storage devices experiences a catastrophic failure. In that case, data loss will occur if no further protection is implemented. For that reason, the architecture known as Redundant Arrays of Inexpensive Disks (RAID) was proposed [15].
The way RAID architectures work is by assigning one or more devices to parity. For instance, take n sectors in the same location in each device (we call this set of n sectors, a "stripe"): n − 1 sectors carry information, while the nth is the XOR of the n − 1 information sectors. We repeat this for each stripe of sectors in the array. Such an architecture is called a RAID 4 or a RAID 5 type of architecture. In what follows, we will call it RAID 5, the difference between RAID 5 and RAID 4 consisting on the distribution of the parity sectors, but we do not address this issue here. A RAID 6 architecture gives protection against two catastrophic failures.
Architectures like RAID 5 and RAID 6 are efficient when the storage devices are hard disk drives (HDDs). However, when using solid state drives (SSDs) like flash, these types of architectures, by themselves, either are not efficient or they are wasteful. Arrays of SSDs pose new challenges for code design, so we will spend the rest of this section addressing some of them. Different ways to adapt RAID architectures to SSDs are being considered in recent literature. For instance, ways to enhance the performance of RAID 5 are described in [2] [21]. See also [16] [20], where the internal ECC and a RAID type of architecture communicate. In particular, [16] uses an adaptive method to increase the redundancy when the bit-error rate increases.
Contrary to HDDs, SSDs degrade significantly in time and as a function of the number of writes [33]. As time goes by and the number of writes increases, the likelihood of a hard error in a sector also increases. A hard error occurs mainly when the internal ECC of a sector is exceeded. In general, BCH codes [29] [30] are used for the internal ECC of a sector, although many other codes (including LDPC codes with soft decoding) are possible. Moreover, in recent years some remarkable non-traditional approaches for the ECC that exploit the assymetry of the SSD channel have been developed [3] [19] [22][23] [24][25] [26] [32]. However, we do not address the internal ECC problem in this paper. The point is, a hard error corresponds to an uncorrectable error in a sector. Normally, the ECC is coupled with a Cyclic Redundancy Code (CRC), which detects the situation when the ECC miscorrects (the ECC has an inherent detection capability that may not be sufficient, hence it often needs to be reinforced by the CRC). There are several ways to implement the CRC, but we do not address them here. We will assume instead that a hard error means that the information in a sector is lost (an erased sector) and that we can detect this situation.
From the discussion above, we see that, contrary to arrays of HDDs, arrays of SSDs present a mixed failure mode: on one hand we have catastrophic SSDs failures, as in the case of HDDs. On the other hand, we also have hard errors, which in general are silent: their existence is unknown until the sectors are accessed. This situation complicates the task of a RAID type of architecture. In effect, assume that a catastrophic SSD failure occurs in a RAID 5 architecture. Each sector of the failed device is reconstructed by XORing the corresponding sectors in each stripe of the surviving devices. However, if there is a stripe that in addition has suffered a hard error, such a stripe has two sectors that have failed. Since we are using RAID 5, we cannot recover from such an event and data loss will occur.
A possible solution to the situation above is using a RAID 6 type of architecture, in which two SSDs are used for parity. Certainly, this architecture allows for the recovery of two erased sectors in the same stripe. However, such a solution is expensive, since it requires an additional whole device to protect against hard errors. Moreover, two hard errors in a stripe, in addition to the catastrophic device failure, would still cause data loss, and such a scenario may not be unlikely, depending on the statistics of errors. We would like some solution intermediate between RAID 5 and RAID 6 allowing the handling of hard errors without the need of dedicating a whole second SSD to parity, and in addition being able to handle at least two hard errors in the same stripe, a catastrophic failure having occurred.
In order to handle this mixed environment of hard errors with catastrophic failures, we need to take into account the way information is written in SSDs, which is quite different to the way it is done in HDDs. In an SSD, a new write consists of erasing first a number of consecutive sectors and then rewriting all of them. Therefore, the short write operation in arrays of SSDs (like one sector at a time) is not an issue here: each time a new write is done, a group of, say, m sectors in each SSD is erased and then rewritten. So, the parity needs to be recomputed as part of the new write. We can assume that the array consists of m × n blocks (i.e., each block consists of m stripes), repeated one after the other. Each m × n block is an independent unit, and we will show how to compute the parity for each block. Also, each new write consists of writing a number of m × n blocks (this number may be one, depending on the application, the particular SSD used, and other factors). Our goal is to present a family of codes, that we call partial-MDS (PMDS) codes, allowing for the simultaneous correction of catastrophic failures and hard errors.
The paper is organized as follows: in Section 2, we present the theoretical framework as well as the basic definitions. In Section 3, we present our main construction. In Section 4, we study the special case in which the general construction of Section 3 extends RAID 5, and we find the general conditions for such codes to be PMDS. In Section 5, we study specific cases with parameters relevant to applications, each case analyzed in a separate subsection. In Section 6, we present an alternative construction to the one presented in Section 3, we compare the two and we study some relevant special cases of this second construction. In Section 7 we present a third construction for cases extending RAID 5. This third construction is not as powerful as the the previous ones (it cannot handle three erasures in the same stripe) but uses finite fields of smaller size, simplifying the implementation. In Section 8, we compute the probability of data loss when a catastrophic device failure has occurred under different scenarios. We conclude the paper by drawing some conclusions.
Although the results can be extended to finite fields of arbitrary characteristic, for simplicity, we consider only fields of characteristic 2.

Partial-MDS codes
Consider an m × n array, each entry of the array consisting of b symbols (we assume that each of the b symbols is a bit for the sake of the description, but in practice it may be a much larger symbol). Each stripe in the array is protected by r parity entries in such a way that any r erasures in the stripe will be recovered. In other words, each stripe of the array P P P P P P  constitutes and [n, n − r, r + 1] MDS code. In addition, we will add s extra "global" parities. Those s extra parities may be placed in different ways in the array, but in order to simplify the description we will place them in the last stripe. Being global means that these parities affect all mn entries in the array. For instance, Figure 1 shows a 4 × 5 array with r = 1 and s = 2 such that the two extra global parities are placed in the last stripe. The idea of a partial-MDS code (to be defined formally), is the following: looking at Figure 1, assume that a catastrophic failure occurs (that is, a whole column in the array has failed), and in addition, we have up to two hard errors anywhere in the array. Then we want the code to correct these failures (erasures in coding parlance). The situation is illustrated in Figure 2, where the hard errors are indicated with the letter 'H': the two hard errors may occur either in different stripes or in the same stripe.
A natural way of solving this problem is by using an MDS code. In our 4×5 array example, we have a total of 6 parity sectors. So, it is feasible to implement an MDS code on 20 symbols with 6 parity symbols. In other words, a [20,14,7] MDS code (like a RS code). The problem with this approach is its complexity. The case of a 4 × 5 array is given for the purpose of illustration, but more typical values of m in applications are m = 16 and even m = 32. That would give 18 or 34 parity sectors. Implementing such a code, although feasible, is complex. We want that the code, in normal operation, utilizes its underlying RAID structure based on stripes, like single parity in the case of RAID 5. The extra parities are invoked in rare occasions. So, given this constraint of an horizontal code, we want to establish an optimality criterium for codes, that we will call partial-MDS (PMDS) codes. In the case of the example of RAID 5 plus two global parities, we want the code to correct up to one erasure per stripe, and in addition, two extra erasures anywhere. For example, the code of Figure 1 is PMDS if it can correct any of the situations depicted in Figure 2. Formally, Definition 2.1 Let C be a linear [mn, m(n − r) − s] code over a field or ring such that when codewords are taken row-wise as m × n arrays, each row belongs in an [n, n − r, r + 1] MDS code. Given (s 1 , s 2 , . . . , s t ) such that each s j ≥ 1 and t j=1 s j = s, we say that C is (r; s 1 , s 2 , . . . , s t )-erasure correcting if, for any 0 ≤ i 1 < i 2 < . . . < i t ≤ m − 1, C can correct up to s j + r erasures in each row i j of an array in C. We say that C is an (r; s) partial-MDS (PMDS) code if, for every (s 1 , s 2 , . . . , s t ) such that each s j ≥ 1 and t j=1 s j = s, C is an (r; s 1 , s 2 , . . . , s t )-erasure correcting code.
In the next section we give a general construction of codes by providing their (mr +s)×mn parity-check matrices. Some of these codes are going to be PMDS. In particular, we will analize the case r = 1 in Section 4 due to its important practical value, since it extends RAID 5.

Code Construction
As stated in Section 2, our entries consist of b bits. We will assume that each entry is in a ring. The ring is defined by a polynomial f (x) of degree b, i.e., the product of two elements in the ring (taken as polynomials of degree up to b−1), is the remainder of dividing the product of both elements by f (x) (if f (x) is irreducible, the ring becomes the field GF (2 b ) [31]).
A special case that will be important in applications is f (x) = M p (x) = 1 + x + · · · + x p−1 , p a prime number. In this case, e(M p (x)) = p and f (x) may not be irreducible. In fact, it is not difficult to prove that f (x) is irreducible if and only if 2 is primitive in GF (p). So, the polynomials of degree up to p − 2 modulo M p (x) constitute a ring and not generally a field. This ring was used in [7] to construct the Blaum-Roth (BR) codes, and for the rest of the paper, we either assume that f (x) is irreducible or that f (x) = M p (x), and p will always denote a prime number.
We present next a general construction, and then we illustrate it with some examples. where, if f (α) = 0, H(n, r, i, j) is the r × n matrix Let us point out that matrices H(n, r, i, j) as given by (2), in which each row is the square of the previous one, were used in [12][14] [37] for constructing codes for which the metric is given by the rank, in [6] for constructing codes that can be encoded on columns and decoded on rows, and in [27] for constructing the so called differential MDS codes.
Let us illustrate Construction 3.1 in the next example.
So far we have not proved that Construction 3.1 provides PMDS codes. Actually, this is not true in general. The answer depends on the particular parameters and on the polynomial f (x) defining the ring or field.
We denote by (a i,j ) 0≤i≤m−1 0≤j≤n−1 the received entries from a stored array in C(m, n, r, s; f (x)), assuming that the erased ones are equal to 0. The first step to retrieve the erased entries consists of computing the rm+s syndromes. Using the parity-check matrix H(m, n, r, s; f (x)) given by (1), the syndromes are After computing the syndromes, the erasures are recovered by solving a linear system based on the parity-check matrix, provided that such a solution exists. In the next section, we study the case r = 1 and give necessary and sufficient conditions that determine whether a C(m, n, 1, s; f (x)) code is PMDS.

The case r = 1
In this section, we assume that r = 1, thus, the parity-check matrix H(m, n, 1, s) given by (1) can be written as Assume that t j=1 s j = s for integers s j ≥ 1. According to Definition 2.1, we will characterize when C(m, n, 1, s; f (x)) is (r; s 1 , s 2 , . . . , s t )-erasure correcting. We need a series of lemmas first. 1. code C(m, n, 1, s − 1; f (x)) is PMDS, and; 2. for any (s 1 , s 2 , . . . , s t ) such that t j=1 s j = s, for any 0 ≤ i 2 < i 3 < . . . < i t ≤ m − 1, and for any 1 ≤ j ≤ t and 0 ≤ l j,0 < l j,1 < · · · < l j,s j ≤ n − 1, Proof: Since f (x) is implicit, let us denote C(m, n, 1, s; f (x)) simply by C(m, n, 1, s). Consider rows 0 ≤ i 1 < i 2 < · · · < i t ≤ m − 1 such that row i j has exactly s j + 1 erasures in locations (i j , l j,0 ), (i j , l j,1 ), . . . , (i j , l j,s j ), for 0 ≤ l j,0 < l j,1 < · · · < l j,s j ≤ n − 1 and t j=1 s j = s. Assuming the erased entries to be equal to zero and computing the syndromes according to (3) and (5), we obtain The system given by (7) and (8) has a unique solution if and only if the (t + s) Therefore, the s × s matrixĉ consists of a first row w 0 followed by succesive rows w u , where each row is the square of the previous row, i.e., w u = w 2 u 0 for 1 ≤ u ≤ s − 1. Matrixĉ is invertible if and only if its determinant is invertible. The determinant of a matrix of this type is known [6]: it is the product of the XOR of all possible subsets of elements of the first row. For example, if we have a matrix . This result is proven similarly to the one of Vandermonde matrices. For the sake of completeness, we prove it in the Appendix. The first row of matrixĉ is given by where and, for 2 ≤ j ≤ t, Then, code C(m, n, 1, s) is PMDS if and only if the determinant det (ĉ) is invertible, if and only if the XOR of any subset of the elements of w 0 is invertible. Since w 0 has s elements, we may assume that if we XOR a number elements smaller than s, the result is true by induction, so assume that we take the XOR of all the s elements in w 0 . Then, code C(m, n, 1, s) is PMDS if and only if code C(m, n, 1, s − 1) is PMDS and is invertible. But (10) is invertible if and only if (6) holds. ✷ Lemma 4.2 Consider a code C(m, n, 1, s; f (x)) and let s j ≥ 1 for 1 ≤ j ≤ t such that while if s j is even, If s 1 is even, making s ′ 1 = s 1 − 1, according to (12) and (11), (10) becomes Since α l 1,1 −l 1,0 is always invertible, then, by (10) and (13), if s 1 is even, Similarly, if 2 ≤ v ≤ t and s v is even, according to (12) and (11), (10) becomes By (10) and (14), we may claim that if s v is even for some 2 ≤ v ≤ t, then, making . . , s t )-erasure correcting if and only if C(m, n, 1, s) is (s 1 + 1, s 2 + 1, . . . , s v + 1, . . . , s t + 1)-erasure correcting, completing the proof. ✷ Lemma 4.3 Consider a code C(m, n, 1, s; f (x)) and let s j ≥ 1, each s j an odd number for 1 ≤ j ≤ t such that t j=1 s j = s. Then, C(m, n, 1, s; f (x)) is (1; s 1 , s 2 , . . . , s t )-erasure correcting if and only if, for any 0 ≤ i 2 < i 3 < . . . < i t ≤ m − 1 and for any 0 ≤ l j,0 < l j,1 < . . . < l j,s j ≤ n − 1 for each 1 ≤ j ≤ t, Proof: Notice that in this case, (6) becomes (15). 1. code C(m, n, 1, s − 1; f (x)) is PMDS, and; 2. for every (s 1 , s 2 , . . . , s t ) such that t j=1 s j = s and each s j is odd, for any 0 ≤ i 2 < i 3 < . . . < i t ≤ m − 1, and for any 1 ≤ j ≤ t and 0 ≤ l j,0 < l j,1 < · · · < l j,s j ≤ n − 1, condition (15) holds. Theorem 4.1 gives us conditions to check in order to determine if a code C(m, n, 1, s; f (x)) as given by Construction 3.1 is PMDS, but by itself it does not provide us with any family of PMDS codes. Consider the ring of polynomials modulo M p (x), such that mn < e(M p (x)) = p. There are cases in which M p (x) is irreducible [7] and the ring becomes a field (equivalently, 2 is primitive in GF (p)). Notice that the polynomials in Theorem 4.1 have degree at most mn − 1 < p − 1 = deg(f (x)). Therefore, if M p (x) is irreducible then all such polynomials are relatively prime with M p (x) and the code is PMDS. Let us state this fact as a theorem, which provides a family of PMDS codes (it is not known whether the number of irreducible polynomials M p (x) is infinite): Theorem 4.2 Consider the code C(m, n, 1, s; M p (x)) given by Construction 3.1 such that M p (x) is irreducible (or equivalently, 2 is primitive in GF (p)). Then, C(m, n, 1, s; M p (x)) is PMDS.
So far we have dealt with general values of s. In the next section we examine special cases that are important in applications.

Special cases
We examine each case into a separate subsection.

5.1
The case C(m, n, 1, 1; f (x)) Notice that C(m, n, 1, 1; f (x)) is always PMDS, since by Theorem 4.1, we have to check if the binomials of type 1 + x j for 1 ≤ j ≤ n − 1 and f (x) are relatively prime. This is certainly the case when f (x) is irreducible, but also when M p (x) is reducible [7]. Let us state this result as a lemma: C(m, n, 1, 1; f (x)) is always PMDS.

5.2
The case C(m, n, 1, 2; f (x)) This case is important in applications, in particular, for arrays of SSDs. Since C(m, n, 1, 1; f (x)) is PMDS, Theorem 4.1 gives the following theorem for the case s = 2: is PMDS if and only if, for any 1 < i ≤ m − 1, and for any 0 ≤ l 1,0 < l 1,1 ≤ n − 1, 0 ≤ l 2,0 < l 2,1 ≤ n − 1 , Given the practical importance of this case, let us examine the decoding (of which the encoding is a special case) in some detail.
Consider a PMDS code C(m, n, 1, 2; f (x)), i.e., it satisfies the conditions of Theorem 5.1. Without loss of generality, assume that we either have three erasures in the same row i 0 , or two pairs of erasures in different rows i 0 and i 1 , where 0 ≤ i 0 < i 1 ≤ m − 1. Consider first the case in which the three erasures occur in the same row i 0 and in entries j 0 , j 1 and j 2 of row i 0 , 0 ≤ j 0 < j 1 < j 2 . Assuming initially that a i 0 ,j 0 = a i 0 ,j 1 = a i 0 ,j 2 = 0, using (3) and (5) ((4) is used only for r > 1), we compute the syndromes S i 0 , S m and S m+1 . Using the parity-check matrix H(m, n, 1, 2) as given by (1), we have to solve the linear system The solution to this system is This determinant is easily inverted in a field, while in the ring of elements modulo M p (x), the elements 1 ⊕ α j 1 −j 0 , 1 ⊕ α j 2 −j 0 and 1 ⊕ α j 2 −j 1 can be efficiently inverted (for details, see [7]).
The encoding is a special case of the decoding. For instance, assume that we place the two global parities in locations (m − 1, n − 3) and (m − 1, n − 2), as depicted in Figure 1. After computing the parities a i,n−1 for 0 ≤ i ≤ m − 2 using single parity, we have to compute the parities a m−1,n−3 , a m−1,n−2 and a m−1,n−1 using the method above. In particular, the Vandermonde determinant becomes (making i 0 = m − 1, j 0 = n − 3, j 1 = n − 2 and α 4 ). So, we have to invert only α 4(m+n)−15 (1 ⊕ α 4 ) for the encoding and some operations may be precalculated, making the encoding very efficient. We omit the details.
We analize next the case of two pairs of erasures in rows i 0 and i 1 , 0 ≤ i 0 < i 1 ≤ m − 1, and assume that the erased entries are a i 0 ,j 0 and a i 0 ,j 1 in row i 0 , 0 ≤ j 0 < j 1 ≤ n − 1, and a i 1 ,ℓ 0 and a i 1 ,ℓ 1 in row i 1 , 0 ≤ ℓ 0 < ℓ 1 ≤ n − 1.
Again using the parity-check matrix H(m, n, 1, 2), we have to solve the linear system of 4 equations with 4 unknowns where S i 0 and S i 1 are given by (3) and S m and S m+1 are given by (5). In order to solve this linear system, we need to invert the determinant By row operations, we can easily see that this determinant is equal to the following determinant times a power of α: Notice that this determinant corresponds to a 2 × 2 Vandermonde matrix, and it equals We have seen that the latter is easy to invert. Inverting 1 ⊕ α j 1 −j 0 ⊕ α (i 1 −i 0 )n+ℓ 0 −j 0 (1 ⊕ α ℓ 1 −ℓ 0 ), however, is not as neat as inverting binomials 1 ⊕ α j when the size b of the symbols is a large number. Since 1 + x j 1 −j 0 + x (i 1 −i 0 )n+ℓ 0 −j 0 (1 + x ℓ 1 −ℓ 0 ) and f (x) are relatively prime by Theorem 5.1, we can invert 1 + x j 1 −j 0 + x (i 1 −i 0 )n+ℓ 0 −j 0 (1 + x ℓ 1 −ℓ 0 ) modulo f (x) using Euclid's algorithm. This operation may take some computational time, but it is not done very often. When it is invoked, performance has already been degraded due in general to a catastrophic failure. The emphasis here is on data recovery and not on performance, since data loss is not acceptable.
Let us now analize some concrete PMDS codes C(m, n, 1, 2; f (x)). Consider first finite fields GF (2 b ). In Table 1, we give the value b, the irreducible polynomial f (x) (in octal notation), the exponent e(f (x)), and values m and n for which the code C(m, n, 1, 2; f (x)) is PMDS according to Theorem 5.1. We have not checked all possible irreducible polynomials, so we are not claiming that the values of m and n are maximal in each case, but it is certainly feasible to do so. For extensive tables of irreducible polynomials, see [40].
Next, consider the case of codes C(m, n, 1, 2; M p (x)). Theorem 4.2 solves the case in which M p (x) is irreducible, so assume that M p (x) is not irreducible, i.e., the ring is not a field.  Table 1: Some values of b, f (x), m and n for which codes C(m, n, 1, 2; f (x)) are PMDS This ring was considered for the BR codes [7] because it allows for efficient correction of erasures for symbols of large size without using look-up tables like in the case of finite fields. We need to check all possible cases of Theorem 5.1 for different values of m and n, mn < p.
The results are tabulated in Table 2, which gives the list of primes between 17 and 257 for which M p (x) is reducible (hence, 2 is not primitive in GF (p)), together with some values of m and n, and a statement indicating whether the code is PMDS or not. For most such primes the codes are PMDS. The only exceptions are 31, 73 and 89. The case p = 89 is particularly interesting, since for m = 8 and n = 11 as well as for m = n = 9, the codes are not PMDS. However, for m = 11 and n = 8, the code is PMDS, which illustrates the fact that a code being PMDS does not depend only on the polynomial M p (x) chosen, but also on m and n.

An alternative construction
In this section we present an alternative to Construction 3.1.  (20) where, if f (α) = 0, H (1) (n, r, i, j) is the r × n matrix and 0(n, r) is an r × n zero matrix.
Next we illustrate Construction 6.1 with some examples.

A Simplified Construction
In this section we present a construction that is an alternative to codes C(m, n, 1, s; f (x)) for 1 ≤ s ≤ 2. In the case of s = 2, the new construction can correct the situation depicted at the left of Figure 2, that is, two pairs of erasures in two different rows. It cannot correct the situation at the right of Figure 2, i.e., three erasures in the same row. This is a tradeoff, since the new construction, as we will see, uses a smaller finite field or ring. Explicitly: The following lemma is immediate: The code C (2) (m, n, 1, 1; f (x)) given by Construction 7.1 is PMDS.
Proof: Assume that we have two erasures in locations j 0 and j 1 of row i 0 and two erasures in locations ℓ 0 and ℓ 1 of row i 1 , where 0 ≤ i 0 < i 1 ≤ m − 1, 0 ≤ j 0 < j 1 ≤ n − 1 and 0 ≤ ℓ 0 < ℓ 1 ≤ n − 1. Using the parity-check matrix H (2) (m, n, 1, 2) as given in Construction 7.1, these four erasures can be recovered if and only if is invertible. By row operations, we find out that this determinant is invertible if and only if 1 ⊕ α j 1 −j 0 , 1 ⊕ α ℓ 1 −ℓ 0 and 1 ⊕ α i 1 −i 0 are invertible. But this is certainly the case if f (x) is irreducible or f (x) = M p (x), since j 1 − j 0 , ℓ 1 − ℓ 0 and i 1 − i 0 are smaller than the exponent of f (x). ✷ Lemma 7.2 is important in applications. Let us compare it with C(m, n, 1, 2; f (x)) codes that are PMDS as given in Subsection 5.2. For the sake of discussion, let us assume that max{m, n} ≤ 15, a situation that covers some practical applications. In the case of C(m, n, 1, 2; f (x)), using Table 1, if n = 15, we would need to operate on the field GF (2 16 ). If we use a code C (2) (m, n, 1, 2; f (x)), we can take the finite field GF (2 4 ) as given by a primitive polynomial, which has exponent 15. If we use GF (2 5 ) with a primitive polynomial, we can increase m to 16, a value convenient in applications. If we use rings generated by M p (x) and we want m ≤ 17, n ≤ 17, by Table 2, we may use p = 257 for a PMDS code C(m, n, 1, 2; M 257 (x)). If we just implement a (1;1,1)-erasure correcting code for the same values of m and n, we can do it with a code C (2) (m, n, 1, 2; M 17 (x)).
Using ideas similar to the ones of GC codes we can extend Construction 7.1 to codes that are (1; s 1, 1, . . . , 1)-erasure correcting (that we denote C (2) (m, n, 1, s; f (x))) as well as other combinations by using horizontal and vertical codes, but for reasons of space we omit them here. Moreover, as we will see in the next section, there is not much gain for codes C (2) (m, n, 1, s; f (x)) and s ≥ 3 with respect to codes C (2) (m, n, 1, 2; f (x)) in a mixed environment of catastrophic failures and hard errors.

Probability of Data Loss After One Disk Failure
In this section, we assume that a catastrophic device failure has occurred. We will make a number of assumptions and we will compute the probability of data loss for the different schemes presented in the paper as a function of the raw error probability p (a parameter that, as we have discussed in the Introduction, degrades with time and with the number of writes for SSDs). Specifically, we will compare (1; 2) PMDS codes and (1;1,1)-erasure correcting codes, since both have the same redundancy (but the former is implemented over a larger field). We assume that the information in each SSD is stored in pages, where each page has size 4K and there are eight 512B sectors per page. Further, we assume that each sector is protected by a t-bit error-correcting code, like a BCH code (for instance, t = 15). Each SSD device has M pages. For example, if a device has size 32 G, it has 8 million pages. We assume that stripes are rows of pages in an m × n block.
Since we assume that one of the n devices has failed, if exactly one hard error has occurred in at least three different stripes of an m-stripe block, we will have data loss. If a (1; 2) PMDS code is used, three hard errors in the same stripe will also cause data loss, while if a (1; 1, 1)-erasure correcting code is used, two hard errors in the same stripe are enough to cause data loss.
As stated above, each codeword is in a BCH code with 512B information bytes (4096 bits). The BCH code can correct up to t bit errors, so the redundancy is 13t bits, giving 195 bits for t = 15.
We want to compute first the probability P that a codeword cannot be decoded. This will occur each time t + 1 or more errors occur, and this event we assume is always detected either by the BCH code itself or by the CRC. Therefore, we have: Thus, since there are 8 sectors per page, the probability that in a page at least a codeword is not corrected (i.e., a hard error) is The probability of exactly one hard error in a stripe is The probability of more than j hard errors in a stripe is The probability of exactly one hard error in at least three of the m stripes in a block is then The probability of at least j + 1 hard errors in any of the m stripes of the block is The probability of data loss in an m-stripe block of a (1;1,1)-erasure correcting code is then given by P S (1;1,1)EC = P S m,1,3 + P S m,2,1 , while the probability of data loss in an m-stripe block of a (1,2) PMDS code is given by P S (1;2)PMDS = P S m,1,3 + P S m,3,1 .
We can now compute the probability of data loss for both a (1;1,1)-erasure correcting code and a (1;2) PMDS code. That will occur each time at least one m-stripe block has experienced data loss. Thus, since we had assumed that there are M pages per device and that each block has m stripes, there are M/m blocks (for 32G SSDs, and m = 16, M/m = 500, 000), we obtain for a (1;1,1)-erasure correcting code, Looking at the probabilities of data loss in an m-stripe block for m = 16 and 32G devices in Table 5, we can see that in general P S (1;1,1)EC is dominated by P S m,2,1 (i.e., P S (1;1,1)EC ≈ P S m,2,1 ), while P S (1;2)PMDS is dominated by P S m,1,3 (i.e., P S (1;2)PMDS ≈ P S m,1,3 ). For that reason, by increasing s, the probability of data loss of a (1; s 1, 1, . . . , 1)-erasure correcting code is basically the same for any s ≥ 2 when a whole device has failed. In particular, for s = m, we have RAID 6. Of course RAID 6 can tolerate a second device failure, but any hard error in the case of two device failures will cause data loss.
Another conclusion from Table 5 is the advantage of using a (1;2) PMDS code over a (1;1,1)-erasure correcting code, both codes having the same number of parity entries. As stated in the Introduction, as the system ages, the bit error probability p degrades. So, a natural question is, if we are monitoring p, which value allows us a reasonable expectation of not experiencing data loss? For instance, when we reach p = .0007, according to Table 5, the probability of miscorrection in case a device fails is 7.8E-5. This may be viewed as, less than one in ten thousand systems will have data loss provided a device has failed, which may be acceptable (depending on the application). However, if we used a (1;2) PMDS code, when p = .0008, the probability of data loss is 6.3E-6, more than an order of magnitude better than the (1;1,1)-erasure correcting code. So, the system is more reliable and allows further degradation of the parameter p, increasing its lifetime.

Conclusions
We have presented two constructions of codes that are suitable for a flash array type of architecture, in which hard errors co-exist with catastrophic device failures. We have presented specific codes that are useful in applications. Necessary and sufficient conditions for codes satisfying an optimality criterion were given.    The result follows from the fact that h(γ 0 ) = det(Γ) and by induction on the expression of C above. ✷