Method and system utilizing quintuple parity to provide fault tolerance

Abstract

An error correction and fault tolerance method and system for an array of disks is presented. The array comprises k+5 disks, where k disks store user data and 5 disks store computed parity. The present invention further comprises a method and a system for reconstituting the original content of each of the k+5 disks, when up to 5 disks have been lost, wherein the number of disks at unknown locations is E and the number of disks wherein the location of the disks is known is Z. All combinations of faulty disks wherein Z+2×E≤4 are reconstituted. Some combinations of faulty disks wherein Z+2×E≥5 are either reconstituted, or errors are limited to a small list.

Claims

1. A method of encoding data for providing higher fault tolerance to an associated array of disks in subsequent decoding, said array storing a plurality of identically sized logical or physical blocks of data, herein referred to as stripes, said method comprising: (a) logically or physically partitioning each stripe into k≥1 identically sized strips, herein referred to as data strips, wherein each data strip stores a portion of the data blocks of an associated stripe; (b) numbering the data strips in each stripe with whole numbers 1, 2, 3, . . . , k; (c) calculating parity data comprising x parity strips and numbered k+1, k+2, k+3, k+4, . . . k+x, wherein the calculating comprises: (i) selecting k non-zero distinct elements of a Galois field GF(2.sup.m), denoted by α.sub.1, α.sub.2, . . . , α.sub.k, and (ii) calculating parity of each parity strip according to the formula $P_{j,\ell }=\underset{i=1}{\overset{k}{.Math.}}{M}_{j,i}.Math.D_{i,\ell }$  wherein j is a parity strip index, associated with parity strip numbered k+j in the associated strips, and is a stripe index of the associated stripe, and (d) extending each stripe of the plurality of stripes into an encoded strips by combining k data strips and the x parity strips and comprising a total of k+x strips to generate a plurality of encoded stripes, wherein the data strips are generated using a systematic coding of encoding data, wherein extending each stripe of the plurality of strips by combining k data strips and the x parity stripes provides an enhanced fault tolerance; and (e) storing the plurality of encoded strips in the array of disks such that each strip of the associated encoded stripe is stored in a unique disk in the array of disks, wherein each disk stores at least one strip from each encoded stripe, and wherein an order of the strips in each stripe can be optionally changed prior to storing to implement load balancing.

2. The method of claim 1 wherein the subsequent decoding of the plurality of encoded stripes of data comprises subjecting the plurality of encoded strips to an error-generating process, the error-generating process comprising storage and retrieval of data from disks and data transmission over a noisy channel, and wherein the decoding further comprises identifying and correcting combinations of errors at known and unknown locations in the plurality of encoded stripes of data, wherein most likely combinations of errors are given higher priority over less likely combinations of errors.

3. The method of claim 2 further comprising a syndrome decoding, comprising: (a) calculating a plurality of syndrome vectors s=(s.sub.j,).sub.j=1, =1, 2, . . . , L, according to formula: $s_{j,\ell }=\underset{i=1}{\overset{k}{.Math.}}{M}_{i,j}.Math.r_{i,\ell }+r_{k+j,\ell }$  wherein r.sub.i, denotes data retrieved from disk i and stripe , for i=1, 2, . . . , k+x and =1, 2, . . . , L, wherein L is the total number of stripes; (b) calculating elements of the Galois field, herein referred to as error locators, by performing arithmetic operations in the Galois field; (c) identifying error locations based on the error locators, wherein an error locator value equal to α.sub.i for some i designates data strip with index i as a faulty strip; (d) calculating error values; and (e) reconstituting lost data in each faulty strip by calculating lost data from non-faulty strips.

4. The method of claim 3, further comprising: (a) identifying at most two faulty strips of data in each stripe retrieved herein referred to as received vector, from the array of disks, wherein the identifying does not require prior knowledge of a location of content of the faulty strips in the received vector, the identifying further comprising calculating two or more syndromes and syndrome ratios for the received vector to identify the at most two faulty strips of data; and (b) reconstituting lost data in the faulty strips in the received vector by calculating said lost data from non-faulty strips comprising the associated strip, wherein the method provides fault tolerance due to a combination of at most two errors at known or unknown locations.

5. The method of claim 4, further comprising: (a) computing a location of the faulty strips with unknown locations; and (b) calculating lost data from non-faulty strips and reconstituting the lost data in the plurality of faulty strips of the received vector, wherein each stripe contained Z faulty strips at known locations and E faulty strips at unknown locations, and wherein Z and E are nonnegative whole numbers such that Z+2×E≤2×floor(x/2).

6. The method of claim 5, wherein the number of Galois field operations is independent of the number of disks in the array.

7. The method of claim 3, further comprising list decoding whereby a listing of most likely error vectors is produced for a given syndrome vector, in an order of decreasing likelihood.

8. The method of claim 7, wherein a complete listing of all of the most likely error vectors is produced for each syndrome vector, for which said complete listing of all of the most likely error vectors comprises at most two error vectors.

9. The method of claim 8, wherein the number of Galois field operations is independent of the number of disks in the array.

10. The method of claim 7, further comprising providing fault tolerance of up to 5 errors by collecting lists of most likely error vectors from multiple stripes, and using the lists to reconstitute the lost data, wherein providing the fault tolerance comprises: (a) searching for multiple stripes where the list of error vectors share a set of common error locations; (b) identifying locations of errors in said multiple stripes at the set of common error locations; and (c) reconstituting lost data in said multiple stripes.

11. The method of claim 10 wherein each stripe contains at most three faulty data strips, and none of the faulty parity strips.

12. The method of claim 3, further comprising listing up to two possible error locations for one data error at unknown location, wherein each stripe contains four faulty strips, wherein two of the faulty strips are data strips at known locations, a third strip is a data strip at an unknown location, and a fourth strip is a parity strip at a known location.

13. A method of encoding data logically or physically partitioned into a plurality of identically sized data blocks called stripes, said method comprising: (a) logically or physically partitioning each stripe into k≥1 identically sized strips, herein referred to as data strips, wherein each data strip stores a portion of the data blocks of an associated stripe; (b) numbering the data strips in each stripe with whole numbers 1, 2, 3, . . . , k; (c) calculating parity data comprising five parity strips, distinct from the data strips, and numbered k+1, k+2, k+3, k+4, . . . , k+x, wherein the calculating comprises: (i) selecting k non-zero distinct elements of a Galois field GF(2.sup.m), denoted by α.sub.1, α.sub.2, . . . , α.sub.k; and (ii) calculating parity of each parity strip according to the formula $P_{j,\ell }=\underset{i=1}{\overset{k}{.Math.}}{M}_{j,i}.Math.D_{i,\ell }$  wherein j is a parity strip index, associated with parity strip numbered k+j in the associated strips, and is a stripe index of the associated stripe, and (d) extending each stripe of the plurality of stripes into an encoded stripe by combining k data strips and the five parity strips and comprising a total of k+x strips to generate a plurality of encoded stripes, wherein the data strips are unmodified and generated using a systematic coding of encoding data.

14. A system of encoding data for providing higher fault tolerance to an associated array of disks in subsequent decoding, said array storing a plurality of identically sized logical or physical blocks of data, herein referred to as stripes, the system comprising: (i) one or more processors, and (ii) a memory coupled to the one or more processors, the memory to store computer-executable instructions that, when executed by the one or more processors, cause the one or more processors to perform operations comprising: (a) logically or physically partitioning each stripe into k≥1 identically sized strips, herein referred to as data strips, wherein each data strip stores a portion of the data blocks of an associated stripe; (b) numbering the data strips in each stripe with whole numbers 1, 2, 3, . . . , k; (c) calculating parity data comprising five parity strips, distinct from the data strips, and numbered k+1, k+2, k+3, k+4 and k+x, wherein the calculating comprises: (i) selecting k non-zero distinct elements of a Galois field GF(2.sup.m), denoted by α.sub.1, α.sub.2, . . . , α.sub.k; and (ii) calculating parity of each parity strip according to the formula $P_{j,\ell }=\underset{i=1}{\overset{k}{.Math.}}{M}_{j,i}.Math.D_{i,\ell }$  wherein j is a parity strip index, associated with parity strip numbered k+j in the associated strips, and is a stripe index of the associated stripe, and (d) extending each stripe of the plurality of stripes into an encoded stripe by combining k data strips and the five parity strips and comprising a total of k+x strips to generate a plurality of encoded stripes, wherein the data strips are unmodified and generated using a systematic coding of encoding data; and (e) storing the plurality of encoded stripes in the array of disks such that each strip of the associated encoded stripe is stored in a unique disk in the array of disks, wherein each disk stores one strip from each encoded stripe, and wherein an order of the strips in each stripe can be optionally changed prior to storing to implement load balancing, wherein the step of extending each stripe of the plurality of stripes by combining k data strips and the five parity stripes provides an enhanced fault tolerance.

15. The system of claim 14, wherein the subsequent decoding of the plurality of encoded stripes of data comprises subjecting the plurality of encoded stripes to an error-generating process, the error-generating process comprising storage and retrieval of data from disks and data transmission over a noisy channel, and wherein the decoding further comprises identifying and correcting combinations of errors at known and unknown locations in the plurality of encoded stripes of data, wherein most likely combinations of errors are given higher priority over less likely errors.

16. The system of claim 15, wherein the subsequent decoding further comprises a syndrome decoding, wherein the syndrome decoding comprises: (a) calculating a plurality of syndrome vectors s=(s.sub.j,).sub.j=1.sup.x, =1, 2, . . . , L, according to formula: $s_{j,\ell }=\underset{i=1}{\overset{k}{.Math.}}{M}_{i,j}.Math.r_{i,\ell }+r_{k+j,\ell }$  wherein r.sub.i,.sub. denotes data retrieved from disk i and stripe , for i=1, 2, . . . , k+x and =1, 2, . . . , L, wherein L is the total number of stripes; (b) calculating elements of the Galois field, herein referred to as error locators, by performing arithmetic operations in the Galois field; (c) identifying error locations based on the error locators, wherein an error locator value equal to α.sub.i for some i designates data strip with index i as a faulty strip; (d) calculating error values; and (e) reconstituting lost data in each faulty strip by calculating lost data from non-faulty strips.

17. The system of claim 16, wherein the memory includes additional instructions that, when executed by the one or more processors, cause the one or more processors to perform operations comprising: (a) identifying at most two faulty strips of data in each stripe retrieved, herein referred to as received vector, from the array of disks, wherein the identifying does not require prior knowledge of a location or content of the faulty strips in the received vector, the identifying further comprising calculating two or more syndromes and syndrome ratios for the received vector to identify the at most two faulty strips of data; (b) reconstituting lost data in the faulty strips in the received vector by calculating said lost data from non-faulty strips comprising the associated strip, wherein the operation provides fault tolerance due to a combination of at most two errors at known or unknown locations; (c) computing a location of the faulty strips with unknown locations; and (d) calculating lost data from non-faulty strips and reconstituting the lost data in the plurality of faulty strips of the received vector, wherein each stripe contains Z faulty strips at known locations, and E faulty strips at unknown locations, and wherein Z and E are nonnegative whole numbers such that Z+2×E≤2×floor(x/2), wherein the number of Galois field operations is independent of the number of disks in the array.

18. The system of claim 16, wherein the memory includes additional instructions that, when executed by the one or more processors, cause the one or more processors to perform operations comprising: (a) performing list decoding comprising producing a listing of most likely error vectors for a given syndrome vector, in an order of decreasing likelihood; and (b) producing a complete listing of all of the most likely error vectors for each syndrome vector, for which said complete listing of all of the most likely error vectors comprises at most two error vectors, wherein the number of Galois field operations is independent of the number of disks in the array.

19. The system of claim 18, wherein each stripe contains several faulty data strips, and none of the faulty parity strips.

20. The system of claim 16, wherein the memory includes additional instructions that, when executed by the one or more processors, cause the one or more processors to perform operations comprising: (a) listing a plurality of possible error locations for at least one data error at an unknown location, wherein each stripe contains a plurality of faulty strips, wherein at least a portion of the faulty strips are data strips at known locations.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) The features and advantages of the present invention will become apparent from a consideration of the following detailed description presented in connection with the accompanying drawings in which:

(2) FIG. 1 is a schematic drawing of a system comprising an array of disks [17] comprising disk 1 of plurality of disks [1], disk 2 of plurality of disks [2], . . . , disk 15 of plurality of disks [15], managed by an RAID array controller [16] and attached to a computer [20], further comprising the following: encoder [18], decoder [19], computer system bus [21], RAID controller bus [22], RAID controller interface [23].

(3) FIG. 2 is a schematic drawing of a communication system comprising communications controller [24] attached to a computer [31], transmitter [27] and a receiver [28], further comprising the following: encoder [25], decoder [26], transmitter antenna [29], receiver antenna [30], computer system bus [32], controller interface [33].

(4) FIG. 3 is a schematic drawing of a storage array comprising stripes, strips and disks. A schematic drawing of a storage array logically or physically partitioned into N disks and L stripes, with N strips of data per stripe, and L strips of data per disk. The bottom drawing names the data in the strip Strip.sub.i . . . e, by D.sub.i.e, where i is the disk index and /J is the stripe index, /J=1, 2, . . . , L. When disks are divided into k data disks and 5 parity disks, an alternative name, P.sub.i . . . e, instead of D.sub.k+1,e, is defined for i=1, 2, 3, 4, 5.

(5) FIG. 4 is the diagram showing the invented error correcting code comprising parity matrix [34], generator matrix [35], and parity check matrix [36].

(6) FIG. 5 is a schematic flow diagram of a method of creating the quintuple parity code, in particular, a subset a of the Galois field used in creating the parity matrix, the generator matrix and the parity check matrix, comprising the code cre-ation starting step [37], input of the number of data disks k and the parameter m defining the Galois field GF (2.sup.m) step [38], assignment of the number of roots of the quadratic equation to n step [39], comparison of the number of roots of the quadratic equation n to 0 step [40], assignment of the empty set to the set of excluded roots of unity X step [41], assignment of a set consisting of a single root to the set of excluded roots X step [42], assignment of the set of selected elements of the Galois field GF (2.sup.m) to variable a step [43], output of the set of the selected elements of the Galois field a and the set of excluded roots of unity X step [44], end of the method of creating of the quintuple parity code step [45].

(7) FIG. 6 is a schematic flow diagram of the steps of the main method which decodes combinations of known erasures and errors at unknown locations, comprising the following steps: initial step [46], input of syndromes step [47], choice of parity error indices J and data error number r step [48], lookup of constraints f and non-uniqueness conditions Y step [49], test of consistency constraints step [50], test of non-uniqueness conditions step [51], list decoding branch step [52], solving a system of linear equations for error values step [53], output of error vector step [54], end of the steps of the method [55].

(8) FIG. 7 is a schematic flow diagram of a method to locate 1 failed data and 1 failed parity drive. The flow diagram implements the assignment
(j,ρ,x,y)←LocateFailedParityAndData(s,X),
comprising initial step [56], input of syndromes and excluded roots step [57], initial-ization of variables comprising position of failed parity drive j, Galois field element ρ associated with failed data drive, data error value x, parity error value y and aux-iliary parity index m step [58], comparison of two consecutive syndromes s.sub.m and s.sub.m+1 to zero step [59], assignment of the ratio of consecutive syndromes s.sub.m and s.sub.m+1 to ρ and constructing a vector P based on ρ step [60], checking membership of ρ in the set X of excluded roots of unity step [61], assignment of x followed by initializing failure count failcount to 0 and initializing loop counter t to 1 step [62], checking loop counter t and syndrome s.sub.t for consistency with assumptions made step [63], incrementing failure count failcount and updating failed parity drive position j step [64], incrementing of loop counter t step [65], testing whether loop counter t is in range step [66], comparison of failure count with 0 step [67], compar-ison of failure count with 1 step [68], assignment of invalid value 6 to failed parity disk position j step [69], assignment of invalid value 0 to the failed parity disk po-sition j step [70], assignment of the parity error value y step [71], comparison of auxiliary parity index m with value 1 step [72], assignment of value 3 to the auxiliary parity index m step [73], output of failed parity disk position j, Galois field element ρ associated with failed data disk position, data error value x and the parity error value y step [74], and end of the method to locate 1 failed data and 1 failed parity drive step [75].

(9) FIG. 8 is a schematic flow diagram of a method to correct error given 1 failed data and 1 failed parity drive. The flow diagram implements the assignment
(e,status)←RecoverFailedParityAndData(α,s),
comprising start of the method to correct error given 1 failed data and 1 failed parity drive step [76], input of the set of Galois field elements α and the syndrome vector s step [77], assignment of the set of excluded roots of unity to variable X step [78], initialization of error vector e step [79], initialization of the data drive count k step [80], initialization of logical variable status step [81], initialization of the failed parity drive position j, the Galois element p associated with the failed data drive, the data error x, and the parity error y step [82], comparison of the failed parity drive position j to invalid value 0 step [83], lookup of the failed data drive position based on the Galois field element p step [84], testing failed data drive position i for invalid value 0 step [85], assignment of data error value x to the element of the error vector e.sub.i step [86], testing validity of the failed parity drive position j step [87], assignment of parity error value y to the element of the error vector e.sub.k+j [88], assignment of true value to the status variable step [89], output of error vector e and status variable status step [90], and end of method to correct error given 1 failed data and 1 failed parity drive step [91].

(10) FIG. 9 is a schematic flow diagram of a method to locate 2 failed data drives. The flow diagram implements the assignment
(u,v,x,y)←LocateTwoFailedDataDrives(s),
comprising start of the method to locate 2 failed data drives step [92], input of the syndrome vector s step [93], initialization of Galois field elements u and v associated with failed data drive positions and the corresponding error values x and y step [94], parity consistency check step [95], computing determinants associated with a linear system step [96], comparison of determinants associated with a linear system to zero step [97], computing symmetric polynomial values σ.sub.1 and σ.sub.2 of the Galois field elements u and v step [98], computing values u and v associated with failed drive positions by solving a quadratic equation step [99], computing error values x and y step [100], output of Galois field elements u and v associated with failed drive positions and the corresponding error values x and y step [101], and end of method to locate 2 failed data drives step [102].

(11) FIG. 10 is a schematic flow diagram of a method to correct errors, given that two data drives failed. The flow diagram implements the assignment
(e,status)←RecoverFailedParityAndData(α,s),
comprising the following steps: start of the method to correct errors, given that two data drives failed step [103], input of the set of Galois field elements α and the syndrome vector s step [104], computing Galois field elements u and v associated with two drive failures and corresponding error values x and y step [105], assignment of the number of elements of a to variable k step [106], assignment of the locations of the failed data drives to variables i and j step [107], initialization of the error vector e and the status variable status step [108], testing validity of i and j step [109], assignment of error values x and y to the elements of the error vector i and j, and setting status to true as indication of success step [110], output of the error vector e and status variable status step [111], and end of method to correct errors, given that two data drives failed step [112].

(12) FIG. 11 is a schematic flow diagram of the steps of the method of correct-ing up to two errors at unknown locations, and overall flow control of the decoder, comprising the following steps: start of the method step [113], input of the set of elements of Galois field a and the received vector r step [114], initialization of error vector e to 0 step [115], assignment of parity check matrix to variable H step [116], computation of the syndrome vector s step [117], locating non-zero elements in the syndrome vector s and assignment to the list lst step [118], assignment of the number of non-zero syndromes to the count of non-zero element nz step [119], comparison of the count of non-zero elements nz to 0 step [120], comparison of the count of non-zero elements nz to 1 step [121], comparison of the count of non-zero elements nz to 2 step [122], assignment of the first element of the list lst to position of the first failed parity drive i step [123], assignment of the second element of the list lst to position of the second failed parity drive j step [124], assignment of the single element of the list lst to position of the single failed parity drive j step [125], as signment of syndrome s to the error vector element e.sub.k+i step [126], assignment of syndrome s.sub.i to the error value of the first parity drive stored in vector element e.sub.k+i step [127], assignment of syndrome s.sub.i to the error value of the second parity drive stored in vector element e.sub.k+j step [128], computing the error vector e and status value status assuming failure of not more than one parity and not more than one data drive step [129], testing successful recovery under the assumption that not more than one parity and not more than one data drive failed step [130], comput-ing the error vector e and status value status assuming failure of no-parity and not more than two data drive step [131], testing successful recovery under the assump-tion that no parity and not more than two data drives failed step [132], computing the recovered vector t step [133], output the recovered vector t and status variable status [134], and end of the method step [135].

(13) FIG. 12 is a table listing the formulae for correcting a 3-error combination, one data and 2 parity errors at positions j, l (i.e. locations k+j, k+l), j, l=1, 2, 3, 4, 5, j<l. The equations (polynomials required to be 0) in the third column contain the data error locator p. The fourth column contains a constraint obtained by eliminating p from equations in column 2. The fifth column contains a non-uniqueness condition, which is the condition to have multiple 3-error combinations matching the syndromes s.sub.i, j=1, 2, 3, 4, 5. As is clear, the non-uniqueness condition is satisfied only if the syndromes at positions other than j, l are zero. Therefore non-uniqueness is only possible when the syndromes match a 2-parity error.

(14) FIG. 13 is a table listing the formulae for correcting a 3-error combination, consisting of 2 data errors and 1 parity error at position j (i.e. location k+j) j=1, 2, 3, 4, 5, occurs. The equations (polynomials required to be 0) in the second column are expressed in terms of symmetric polynomials σ.sub.1=u.sub.1+u.sub.2 and σ.sub.2=u.sub.1.Math.u.sub.2, where u.sub.1 and u.sub.2 are the error locators of the 2 data errors.

(15) FIG. 14 is a table listing the formulae for correcting a 4-error combination, consisting of 3 data errors and 1 parity error at position j (i.e. location k+j) j=1, 2, 3, 4, 5, occurs. The equation in the second column (a polynomial required to be 0) is a condition on the syndromes s.sub.j and data error locators u.sub.1, u.sub.2 and u.sub.3 to have a solution with one parity error at position j, written in terms of the elementary symmetric polynomials σ.sub.1=u.sub.1+u.sub.2+u.sub.3 and σ.sub.2=u.sub.1 u.sub.2+u.sub.1 u.sub.3+u.sub.2 u.sub.3.

(16) FIG. 15 is a table listing the formulae for correcting a 4-error combination, consisting of 2 data errors and 2 parity errors at positions j and l (i.e. locations k+j and k+l) j, l=1, 2, 3, 4, 5. The equation in the third column (a polynomial required to be 0) is a condition on the syndromes s.sub.j to have a solution with error locators u.sub.1 and u.sub.2 and parity errors at position j and l, written in terms of the symmetric polynomials σ.sub.1=u.sub.1+u.sub.2 and σ.sub.2=u.sub.1 u.sub.2. The degeneracy condition (not to be confused with non-uniqueness condition) in the last column is a condition for the equation expressing conditions to have more than 2 solutions. It should be note there are no non-uniqueness conditions, i.e. non-uniqueness is automatic for such a combination of errors (Y=ø).

(17) FIG. 16 A schematic flow diagram of the method for decoding 3 data errors at unknown locations, using multiple syndrome vectors computed from dis-tinct stripes having the same 3 data error locations, comprising start of the method step [136], input of 3 syndrome vectors and list of data locators step [137], test-ing of non-singularity of the coefficient matrix step [138], solving a linear equation step [139], solving a cubic equation for data error locators step [140], lookup of error locations step [141], output of data error locations step [142], and end of the the method step [143].

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

(18) Referring now to FIGS. 1-16, the present invention features a method for providing fault tolerance to an array of disks storing a plurality of stripes, where a stripe comprises a block of data. In some embodiments, each disk may be partitioned with several identically sized data partitions known as strips. Generally, each strip represents a fixed quantity of data. The data does not need to be binary, but it must be possible to interpret the content of every strip as an element of a Galois field GF (2.sup.m), where m is a whole, positive number, and not depending on the disk index or stripe index.

(19) The drawing in FIG. 1 shows an exemplary arrangement of a preferred embodiment, comprising the RAID array controller [16] connected to the computer system bus [21] of the computer [20], and connected to an array of disks, comprising the array of disks [17] consisting of disk 1 of plurality of disks [1], disk 2 of plurality of disks [2], . . . , disk 15 of plurality of disks [15], wherein the number of disks is chosen as an example and can be changed to any number of disks at least equal to or greater than 6. The invention focuses on two processes, generally known as encoding and decoding. Said encoding comprises sending data from the computer [20] through the computer system bus [21] and through the RAID controller interface [23] to the encoder [18], wherein the data is processed in blocks called stripes, further divided into strips. The encoder adds 5 parity strips to the data stripe, thus forming the encoded stripe, and transmits said encoded stripe by means of the RAID controller bus [22] to the disks comprising the array, wherein the encoded stripe is divided into 15 strips by demuxing (demultiplexing), so that individual strips are stored on distinct disks. Said decoding comprises sending a request for data from the computer [20] to the RAID array controller [16], and to the disks in an array of disks [17]. The disks forward the requested data and the associated parity data to the decoder, wherein they are combined by multiplexing data strips coming from distinct disks into encoded stripes. The decoder [19] corrects the errors in encoded stripes, discards the parity data and transmits the data portion of the decoded and error-corrected stripe to the computer [20].

(20) The drawing in FIG. 2 shows an exemplary arrangement of a preferred em-bodiment, comprising the communications controller [24] connected to the computer system bus [32] of the computer [31], wherein the communications controller [24] is connected to the transmitter [27] and to the receiver [28]. Said exemplary arrange-ment is a modification of the exemplary arrangement in FIG. 1, wherein the RAID controller bus [22] and the array of disks [17] were replaced with the transmitter [27] connected to encoder [25], and the receiver [28] connected to the decoder [26]. No multiplexing or demultiplexing of the data is required, i.e. what is being transmitted is a stream of data comprising stripes of data. Having at least two instances of the apparatus shown in FIG. 2 allows bidirectional, fault tolerant communications, wherein the signal originated by computer [31] and transmitted by transmitter an-tenna [29] in the first instance of the apparatus is subsequently received by receiver antenna [30] in the second instance of the apparatus, subsequently decoded in the decoder [26] and received by computer [31] in the second instance of the apparatus. A variant may replace the transmitter antenna [29] and the receiver antenna [30] with any type of stream- or packet-oriented communication channel, such as a wired connection.

(21) We now turn again to FIG. 1. Conceptually distributed across the array of disks [17] in rows, the identically sized partitioned strips form a data stripe across the entire array of disks. Therefore, the array contains stripes of data distributed as rows in the array, wherein each disk is partitioned into strips of identically partitioned data and only one strip of data is associated with each stripe in the array. Each of the plurality of strips may be indexed by both disk and stripe. The data in strip Strip.sub.i,.sub. will be called D.sub.i,, where i is the disk index, and is the stripe index. When a process operates on a single stripe, is fixed, and it may be dropped for the reason of simplicity of notation. Thus

(22) $\mathrm{Data}\mathrm{in}\mathrm{stripe}{\mathrm{Stripe}}_{\ell }=\left(D_{1,\ell },D_{2,\ell },.Math.,D_{N,\ell }\right)=\left(D_1,D_2,.Math.,D_N\right)=\left[\begin{array}{c}{D}_{1,\ell }\\ D_{2,\ell }\\ .Math.\\ D_{N,\ell }\end{array}\right]=\left[\begin{array}{c}{D}_1\\ D_2\\ .Math.\\ D_N\end{array}\right]$
where N is the number of disks in the array, and the second notation is preferred when the stripe index is obvious. The data in the stripe Strip is understood as a column vector in the N-dimensional vector space over the Galois field GF (2m). In the present invention, each stripe of the plurality of stripes is extended such that each stripe comprises the block of data associated with said stripe and a set of parity data comprising five parity strips. The array of disks may be divided into k data disks, to which data is written unmodified, and 5 parity disks, to which the computed parity data is written. For this reason, the last 5 disks are distinguished as parity disks, and refer to the data in their strips as P.sub.i,.sub. instead of D.sub.k+1,, for i=1, 2, 3, 4, 5. The parity of each parity strip is calculated according to

(23) $\begin{array}{cc}{P}_{j,\ell }=\underset{i=1}{\overset{k}{.Math.}}{M}_{j,i}.Math.D_{i,\ell },j=1,2,3,4,5,& \left(2\right)\end{array}$
where j is the parity disk index and f is the stripe index, and where
M.sub.j,i=α.sub.i.sup.j−1
for j=1, 2, 3, 4, i=1, 2, . . . , k, and where,
M.sub.5,i=α.sub.i.Math.(α.sub.i+1),i=1,2, . . . ,k.
The equivalent form of equation (2) is
s=H.Math.r  (3)
and it represents s as a matrix product of the parity matrix [34] and vector r=(D.sub.1 . . . , D.sub.2 . . . . . . , D.sub.k+5,) called the received vector, and containing the data of stripe numbered . The term “sent vector” refers to data that were most recently written to the same locations. The sent vector r=(D′.sub.1,, D′.sub.2,, . . . , D′.sub.k+5,), which may be different from the received vector due to errors. The differencee=r−r is henceforth called the “error vector”.

(24) The flowchart in FIG. 5 clarifies the method of selecting elements α.sub.1, α.sub.2, . . . , α.sub.k from the Galois field GF (2.sup.m), satisfying all aforementioned requirements.

(25) In additional embodiments, a method of recovering data in at most 5 faulty strips of data in each stripe retrieved (“received vector”) from the array of disks is presented, said method further comprising a method for identifying at most two faulty strips, wherein said identification method does not require prior knowledge of a location or content of a faulty strip in the received vector, the identification method comprises calculating two or more syndromes and syndrome ratios for the received vector to identify the at most two faulty strips of data, wherein each syndrome, s, is calculated from:

(26) 0$\begin{array}{cc}{s}_{j,\ell }=\underset{i=1}{\overset{k}{.Math.}}{M}_{i,j}.Math.r_{i,\ell }+r_{k+j,\ell }& \left(4\right)\end{array}$
wherein r.sub.i . . . e denotes data retrieved from disk i and stripe , for i=1, 2, . . . , k+5 and =1, 2, . . . , L, wherein L is the total number of stripes. Equation (4) is consistent with equations (2) and (3).

(27) The drawing in FIG. 4 shows an exemplary arrangement of a preferred embodiment. In FIG. 4 one sees the parity matrix [34] which is the object of the current invention. Using the parity matrix [34], two additional matrices may be represented: the generator matrix [35] and the parity check matrix [36], related to the parity matrix by arranging parity matrix [34] and the identity matrices l.sub.k×k and l.sub.5×5 by either stacking them together, or placing them side by side, as indicated by the following abbreviated equations:

(28) $\begin{array}{cc}G=\left[\frac{I_{k\times k}}{P_{5\times k}}\right],H=\left[P_{5\times k}.Math.I_{5\times 5}\right].& \left(5\right)\end{array}$
The subscripted, Greek symbols α.sub.1, α.sub.2, . . . , α.sub.k represent member elements of the Galois field GF (2m), where m is any whole number, such as 1, 2, and so on. The whole number k represents the number of data disks comprising the RAID array. The elements α.sub.j must be distinct and non-zero. As the Galois field has 2m elements, usually numbered 0, 1, 2, . . . , 2.sup.m−1, this imposes a requirement that 1≤k≤2.sup.m−1. Furthermore, we require that at most one of the elements α.sub.j satisfies the quadratic equation
ζ.sup.2+ζ+1=0  (6)
with an unknown quantity ζ, ranging over the Galois field GF (2.sup.m). Depending on m, either equation (6) has no solutions or it has two roots, which we call ζ.sub.1 and ζ.sub.2. Vieta's equations imply that ζ.sub.1+ζ.sub.2=1 and ζ.sub.1.Math.ζ.sub.2=1. Hence, both ζ.sub.1 and ζ.sub.2 are non-zero and distinct. Additionally, the roots of equation 6 are also the roots of the equation ζ.sup.3=1, also called the cubic roots of unity. It follows that k may be further limited to the range 1≤k≤2.sup.m−2. As an example, in GF (256), i.e. when m=8, 1≤k≤254.

(29) The flowchart in FIG. 6 shows the steps of a preferred method of decoding a received vector and reconstituting data in the sent vector. In input of syndromes step [47] we use the equation s=H.Math.r, wherein H is the parity-check matrix and wherein r is the received vector. The steps of the method are focused on solving the system of linear equation H.Math.e=s to determine the error vector e of minimum weight. The system H.Math.e=s is rewritten in terms of the parity matrix as
P.Math.e.sub.data+e.sub.parity=s  (7)
where e.sub.data=(e.sub.1, e.sub.2, . . . , e.sub.k) is the data segment of the error vector, e.sub.parity=(e.sub.k+1, e.sub.k+2, e.sub.k+3, e.sub.k+4, e.sub.k+5) is the parity segment of the error vector. Let l be the set of indices i≤k such that e.sub.i≠0. Let J be the set of indices j∈{1, 2, 3, 4, 5} such that e.sub.k+j≠0. Let P be the submatrix obtained from the parity-check matrix P.sub.5+k by keeping only the columns with indices i∈l. Then
P.sup.l.Math.e.sup.l+e.sub.parity=s  (8)
The non-zero entries in the parity vector play the role of slack variables, in the following sense: we satisfy a maximal subset of equations of the system
P.sup.l.Math.e.sup.l=s.  (9)
By setting slack variables according to the equation:
e.sub.parity=s−P.sup.l.Math.e.sup.l=s−P.Math.e.sub.data
we satisfy the remaining equations. If we drop the rows in both sides with indices j∈J, we obtain the simplified equation:
P.sup.J,l.Math.e.sup.l=s.sup.j  (10)
where P.sup.J,l is obtained from P.sup.l by deleting rows with indices j∈J, e.sup.l=e.sup.l is the vector obtained by keeping entries of e with indices i∈l and s.sup.J is obtained from s by deleting entries with indices j where j∈J. There may be many solutions to the equation H.Math.e=s for a given syndrome vector s. According to maximum likelihood or minimal distance decoding, the solution to the decoding problem for the syndrome vector s is the vector e of minimum weight (i.e. with the minimum number of non-zero entries). The majority of steps of the error correcting method of the invention is directed towards finding such an error vector. The last step of the decoding process is computing the decoded vector r=r−e, where r is the most likely codeword (i.e. a vector in the column space of the generator matrix G), resulting in received vector r, and is also called the sent vector. It will be useful to have (10) in a more explicit form. Let u.sub.1, u.sub.2, . . . , u.sub.r be variables which in the invention are called data error locators. The steps of the decoding method will set u.sub.v=α.sub.iv. Let x.sub.μ be variables denoting data error values. The steps of the decoding process will set x.sub.μ=e.sub.iμ for i=1, 2, . . . , k. The matrix equation (10) can be then expressed as a subsystem obtained from

(30) $\begin{array}{cc}\left[\begin{array}{cccc}1& 1& .Math.& 1\\ u_1& u_2& .Math.& u_r\\ u_1^2& u_2^2& .Math.& u_r^2\\ u_1^3& u_2^3& .Math.& u_r^3\\ u_1^2+u_1& u_2^2+u_2& .Math.& u_r^2+u_r\end{array}\right]\left[\begin{array}{c}{x}_1\\ x_2\\ .Math.\\ x_r\end{array}\right]=\left[\begin{array}{c}{s}_1\\ s_2\\ s_3\\ s_4\\ s_5\end{array}\right]& \left(11\right)\end{array}$
by deleting rows with numbers j∈J. For example, for J={2, 4} the deletion of rows step results in the system:

(31) $\begin{array}{cc}\left[\begin{array}{cccc}1& 1& .Math.& 1\\ u_1^2& u_2^2& .Math.& u_r^2\\ u_1^2+u_1& u_2^2+u_2& .Math.& u_r^2+u_r\end{array}\right]\left[\begin{array}{c}{x}_1\\ x_2\\ .Math.\\ x_r\end{array}\right]=\left[\begin{array}{c}{s}_1\\ s_3\\ s_5\end{array}\right]& \left(12\right)\end{array}$
In symbolic form this system can be written as a system of algebraic equations

(32) $\begin{array}{cc}\underset{i=1}{\overset{r}{.Math.}}{f}_j\left(u_i\right)x_i=b_j,j=1,2,.Math.,t& \left(13\right)\end{array}$
wherein {1, 2, . . . , 5}\J={j.sub.1, j.sub.2, . . . , j.sub.t} is the complement of the set J (thus t=5−|J| is the count of elements in the complement of J, wherein |J| denotes the number of elements of the set J, and “\” represents set difference) in the set of all parity indices, and f.sub.v(u)=g.sub.jv(u), wherein

(33) $g_j\left(u\right)=\{\begin{array}{cc}{u}^{j-1},& j=1,2,3,4,\\ u^2+u,& j=5.\end{array}$
and wherein b.sub.v=s.sub.jv for v=1, 2, . . . , t. The system (13) for fixed r∈{1, 2, 3, 4, 5} and J.Math.{1, 2, 3, 4, 5} is a system of algebraic equations in variables u.sub.1, u.sub.2, . . . , u.sub.r, x.sub.1, x.sub.2, . . . , x.sub.r. Apparently the system is non-linear. However, after the data locators u.sub.i, i=1, 2, . . . , r have been found, the error values are determined from a linear system of equations. Since all variables, including the value of rand the set J, vary over finite domains, there exists a brute force method searching the entire domain. It is inconceivable that brute force search is of practical value. The invention is focused on providing an efficient method. According to some embodiments, in the invention the system is solved by finding exact algebraic solution formulae for solving the problem, requiring a fixed number of operations in the Galois field, and having low, quasi-logarithmic time complexity and quasi-linear space complexity. In solving a system of linear equations for error values step [53] we solve the system (13), which we abbreviate to
P.sup.J,rx=s.sup.J  (14)
wherein P.sup.J,r is the coefficient matrix of the system (13) of linear equations in variables x.sub.1, x.sub.2, . . . , x.sub.r and wherein s.sup.j denotes a vector obtained from the syndrome vector by deleting entries with indices j∈J. For example,

(34) $P^{\left\{2,4\right\},2}=\left[\begin{array}{cc}1& 1\\ u_1^2& u_2^2\\ u_1^2+u_1& u_2^2+u_2\end{array}\right],s^{\left\{2,4\right\}}=\left[\begin{array}{c}{s}_1\\ s_3\\ s_5\end{array}\right].$

(35) The linear system (14) is used to compute the constraints Γ which are necessary and sufficient conditions t to be consistent, by methods of linear algebra, which will be apparent to those skilled in the art. Γ is a set of polynomial equations in variables u.sub.i, i=1, 2, . . . , r, and the syndromes s.sub.j. The linear system (14) is also used to compute the non-uniqueness conditions Y which are necessary and sufficient for the system to have a non-unique solution. The set Y also consists from polynomial equations, involving only the coefficients, i.e. variables u.sub.i, i=1, 2, . . . , r. Sets Γ and Y are pre-computed and tabulated, and are used in lookup of constraints r and nonuniqueness conditions Y step [49], test of consistency constraints step [50] and test of non-uniqueness conditions step [51]. If during the test of consistency constraints step [50] it is determined that the constraints are not satisfied, we abandon the current pair (J, r) and go back to the choice of parity error indices J and data error number r step [48]. It is important that the pairs are chosen in the order of increasing number of errors, i.e. |J|+r. Also, if there are known erasures amongst parity errors, J should include them. If there are r′≤r known erasures amongst data errors, the values of u.sub.i, i=1, 2, . . . , r are set to their data locators. If during the test of non-uniqueness conditions step [51] it is determined that the non-uniqueness conditions are satisfied, we move to the list decoding branch step [52]. This step may consider all possible errors by considering multiple equiprobable error vectors (i.e. having the same weight). One application of this branch may be fast identification of failed disks, as the number of failed disk is typically narrowed substantially. Another application of the list decoding branch step [52] is disclosed in FIG. 16. If the test of consistency constraints step [50] succeeds and the test of non-uniqueness conditions step [51] succeeds, we perform the solving a system of linear equations for error values step [53]. Only the pairs (J, r) with |J|+r≤5 should be considered because up to 5 errors are tolerated. The number of such pairs is:

(36) $\underset{t=0}{\overset{5}{.Math.}}\left(\begin{array}{c}5\\ t\end{array}\right)\left(5-t\right)=80.$
This is an upper bound on the number of times that choice of parity error indices J and data error number r step [48] will be executed. A variant of the invention would process some of the pairs (J, r), and exclude others. One example is a variant limiting the number of erasures Z and errors E, wherein Z+2×E≥4. The preferred embodiment handles all syndrome vectors for which there is a unique error vector e of minimum-weight, by finding said unique error vector. Another variant of the invention handles all syndrome vectors for which at most 2 minimum-weight syndrome vectors exist, by finding a list of said error vectors.

(37) In order to further clarify the test of consistency constraints step [50] and the test of non-uniqueness conditions step [51] of FIG. 6, we turn to an example of calculating Γ and Y wherein J={2, 4} and r=2. The details differ, depending on whether u.sub.1 and u.sub.2 are known, or one of them is known, or both are unknown, i.e. the details depend on the number of data erasures. The first case is when both u.sub.1 and u.sub.2 are known (2 data erasures), the linear system (12), set up exactly for this pair (J, r), has a unique solution iff the determinant:

(38) $\left[\begin{array}{ccc}1& 1& s_1\\ u_1^2& u_2^2& s_3\\ u_1^2+u_1& u_2^2+u_2& s_5\end{array}\right]=0.$

(39) The determinant is found to be equal to:
(u.sub.2−u.sub.1)(u.sub.2s.sub.5+u.sub.1s.sub.5−u.sub.2s.sub.3−u.sub.1s.sub.3−s.sub.3−s.sub.1u.sub.1u.sub.2)
As u.sub.2≠u.sub.1 may be assumed (data locators for distinct locations are distinct), the condition of consistency is:
u.sub.2s.sub.5+u.sub.1s.sub.5−u.sub.2s.sub.3−u.sub.1s.sub.3−s.sub.3−s.sub.1u.sub.1u.sub.2=0.

(40) Furthermore, the condition can be expressed in terms of elementary symmetric poly-nomials σ.sub.1=u.sub.1+u.sub.2 and σ.sub.2=u.sub.1 u.sub.2:
σ.sub.1(s.sub.5+s.sub.3)+s.sub.1σ.sub.2+s.sub.3=0.  (15)
Therefore, when both u.sub.1 and u.sub.2 are known, Γ={σ.sub.1(s.sub.5+s.sub.3)+s.sub.1 σ.sub.2+s.sub.3}. This formula can be found in FIG. 15 in row with j=2, l=4, along with other cases of 4-error combinations, with 2 parity and 2 data errors. The formula is used in the test of consistency constraints step [50], to verify the consistency of the linear system P.sup.J,rx=s.sup.J when u.sub.1 and u.sub.2 are known, i.e. the 2 data errors are both erasures. By inspection, the solution is unique, so Y=ø. The second case is when u.sub.1 is a known locator and u.sub.2 is not known (1 data erasure). Then (15) is a linear equation for u.sub.2:
(u.sub.1+u.sub.2)(s.sub.5+s.sub.3)+s.sub.1u.sub.1u.sub.2+s.sub.3=0
The solution is non-unique iff the coefficient at u.sub.2 and the term independent of u.sub.2 are both zero:

(41) $\{\begin{array}{c}{s}_5+s_3+s_1{u}_1=0\\ s_3+\left(s_5+s_3\right)u_1=0\end{array}$
Thus, Y={s.sub.5+s.sub.3+s.sub.1 u.sub.1, s.sub.3+(s.sub.3+s.sub.5) u.sub.1}. If Y is not satisfied, we find that

(42) 0$u_2=\frac{s_3+u_1\left(s_3+s_5\right)}{s_5+s_3+s_1{u}_1}.$

(43) Thus, u.sub.2 is unique. If u.sub.2 is a valid locator we proceed to the solving a system of linear equations for error values step [53]. The third case is when u.sub.1 and u.sub.2 are both unknown (2 errors at unknown location). In this case the solution is typically non-unique and the details are omitted. This ends the walk-through of the steps of the method for J={2, 4} and r=2, and several variants of the method wherein some of the errors are known erasures.

(44) Exemplary arrangements of the preferred embodiment in FIGS. 7-11, show detailed steps to correcting all combinations of 2 errors at known or unknown locations. In one aspect, the FIGS. 7-11, implement the general steps of FIG. 6. In another aspect, they provide a complete, self-contained and very detailed method of correcting all combinations of up to 2 errors. In this case the number of known erasures Z and the number of errors at unknown location E satisfy the inequality Z+2×E≥4 thus guaranteeing the existence of a unique error vector e of minimum weight. In the FIGS. 7-11, we assume that the locations of the errors are unknown. A modification wherein one or two of the errors are erasures, will be apparent to those skilled in the art

(45) The flowchart in FIG. 7 shows the steps of a preferred method of determining the location of two failed disks, when one of the failed disks is a parity disk, numbered by an integer j in the range from 1 to 5, and the other is a data disk, numbered by an integer i, in the range from 1 to k. The first step is input of syndromes and excluded roots step [57], in which data provided comprises a syndrome vector s=(s.sub.1, s.sub.2, s.sub.3, s.sub.4, s.sub.5), comprised of elements belonging to the Galois field, and X is set to consist of some cubic roots of unity in this Galois field. The syndrome vector s is computed from the equation (3),
s=H.Math.r
where H is the parity check matrix [36] and r is the received vector. The steps leading to computing s from H and r are apparent to those skilled in the art, in particular, anyone familiar with matrix multiplication and algebra of Galois fields, and the general concept of syndrome decoding. In the initialization of variables comprising position of failed parity drive j, Galois field element ρ associated with failed data drive, data error value x, parity error value y and auxiliary parity index m step [58] we initialize j to integer value 0, Galois field values ρ, x and y to the 0 of the Galois field, and the integer counter m to integer 1, where m is generally ranging from 1 to 5, and limited by the method to values 1 and 3. In the explanation that follows, m is either 1 or 3. In the comparison of two consecutive syndromes s.sub.m and s.sub.m+1 to zero step [59] we compare syndromes s.sub.m and s.sub.m+1 to 0 in the Galois field. If both syndromes are non-zero, we use their values to calculate their ratio, which we call ρ. In the assignment of the ratio of consecutive syndromes s.sub.m and s.sub.m+1 to ρ and constructing a vector P based on ρ step [60] we then calculate a Galois vector P with 5 components, which follow the pattern of columns parity matrix, and comprised of the Galois field elements 1, ρ, ρ.sup.2, ρ.sup.3 and ρ.Math.(ρ+1). In the checking membership of ρ in the set X of excluded roots of unity step [61] a set X of excluded cubic roots of unity is provided and membership. Comparison of P.sub.4 to 1 in step the [61] detects whether ρ is a cubic root of unity. If m=1 and ρ∈X, i.e. it has been excluded, m=3 is tried, and ρ is recomputed based on different syndromes.

(46) The drawing in FIG. 12 shows an exemplary arrangement of a preferred embodiment. In the table of FIG. 12 formulae are disclosed used in some steps of the preferred embodiment. These formulae are used to correct 3 errors, wherein 1 of said errors is a data error and 2 of said errors are parity errors. The error correcting code of the invention does not allow correcting 3 errors at unknown locations, but Z=2 erasures and E=1 errors are correctable as Z+2×E=4=D−1, where D=5 is the code distance. Therefore, every row of the table of formulae is used in a plurality of steps of method of correcting 3 errors (at most 3), wherein 2 of the errors are erasures. The first two columns, with headings “j” and “l”, specify the parity errors. The column with heading “System of equations for ρ” contains a system of equations for a locator ρ of the data error. The system of equations is obtained by rewriting the matrix equation H.Math.e=s, relating error vector e to the syndrome vector s.

(47) In order to further illustrate the method of FIG. 6 using the formulae in FIG. 12, exemplary steps are presented for correcting 3 errors, wherein j=1, l=2 are two parity error positions, and both parity errors are known erasures. We focus now on the derivation of the first row of the table of FIG. 12. The equation H.Math.e=s is equivalent to the following system of equations, if the data error location is i, 1≤i≤k and α.sub.i=ρ denotes the error locator of the data error, and variables x=e.sub.i, y=e.sub.k+1, z=e.sub.k+2:

(48) $\begin{array}{cc}\{\begin{array}{c}x+y=s_1\\ \mathrm{\rho x}+z=s_2\\ {\rho }^{2}x=s_3\\ {\rho }^{3}x=s_4\\ \rho \left(\rho +1\right)x=s_5\end{array}.& \left(16\right)\end{array}$

(49) We eliminate variables y and z by simply erasing the first two equations:

(50) $\begin{array}{cc}\{\begin{array}{c}{\rho }^{2}x=s_3\\ {\rho }^{3}x=s_4\\ \rho \left(\rho +1\right)x=s_5\end{array}.& \left(17\right)\end{array}$
Elimination of x from the first two equations is attained by multiplying the first equation by ρ and adding the first two equations yields 0=ρ s.sub.3+s.sub.4. Multiplying the third equation by ρ and adding all 3 equations yields 0=ρs.sub.5+s.sub.3+s.sub.4. This is a derivation of the system of equations in the first row of the table, which is

(51) $\begin{array}{cc}\{\begin{array}{c}{s}_5\rho +s_4+s_3=0\\ s_3\rho +s_4=0\end{array}.& \left(18\right)\end{array}$
Other systems of equations in the second column of the table are obtained by a variation of the method. One must ensure equivalence of the system of equations with the original equation H.Math.e=s. The third column of the table is obtained from the above system by eliminating ρ, resulting in the equation:
s.sub.4s.sup.5+s.sub.3s.sub.4+s.sub.3.sup.2=0  (19)
which is a necessary condition for the (overdetermined) system (18) to have a solution. It should be noted that ρ may be either a locator of a known erasure or an unknown locator. If ρ is known, we must check all equations in the third column, hence Γ has 2 polynomials:
Γ={s.sub.5ρ+s.sub.4+s.sub.3,s.sub.3ρ+s.sub.4}
If ρ is unknown, the Γ={s.sub.4 s.sub.5+s.sub.3 s.sub.4+s.sup.2}. The column with the heading “Non-Uniqueness Condition” gives the condition for the system to have a non-unique so-lution. It is obtained by requiring that the coefficients at ρ in equations of the form Aρ+B=0 are both 0, and also, in equations A ρ.sup.2+B=0 must also be both 0 as the Frobenius (squaring) map φ(ρ)=ρ.sup.2 is an automorphism of the Galois field, and therefore there is only one root of the equation A ρ.sup.2+B=0 if A≠0, in a Galois field of characteristic 2. However, the full quadratic equation A ρ.sup.2+B ρ+C=0 may have 2 roots in Galois fields of characteristic 2. We determine the syndrome from the received vector and substitute into (19). If (19) is satisfied, ρ may be found by using one of the equations containing ρ, unless the non-uniqueness condition holds. It should be noted that the non-uniqueness condition in each of the rows states that the syndromes which do not correspond to the parity errors must be 0. Since the number of zero syndromes is 3, the most likely error is a pure parity error with two faulty parities j and l, with the corresponding errors e.sub.k+j=s.sub.j and e.sub.k+6=s.sub.i. Thus, they will never be satisfied if we check for 2-error failures before 3-error failures. If (19) is violated, we are certain that the syndrome vector is inconsistent with 2 parity, 1 data error with parity positions j=1, l=2, and try other rows. If all row constraints fail, we look for other types of errors which produce a match. If the data error in a 3-error failure is an erasure, ρ is known. In the exemplary steps of correcting errors with j=1, l=2, the value x is also known, e.g. x=s.sub.3/ρ.sup.2. We consider the first 2 equations of (16):

(52) $\begin{array}{cc}\{\begin{array}{c}x+y=s_1\\ \rho x+z=s_2\end{array}.& \left(20\right)\end{array}$
Thus, y and z are easily found, and the solution is:

(53) $\begin{array}{cc}\{\begin{array}{c}x=\frac{s_3}{{\rho }^2}\\ y=s_1-x\\ z=s_2=\rho x\end{array}.& \left(21\right)\end{array}$
Triple errors involving parity only are corrected by noting that the syndrome vector s has 3 non-zero and 2 zero entries, and the 3 non-zero entries are at the error positions. The error values are equal to the syndromes at the same positions.

(54) The drawing in FIG. 13 shows an exemplary arrangement of a preferred embodiment. Triple errors involving 1 parity and 2 data are corrected by a sequence of steps utilizing the table of FIG. 13. We focus now on the steps.

(55) We have now two error locators associated with data errors, which we call u.sub.1 and u.sub.2. Since there is absolute symmetry under swapping the values u.sub.1 and u.sub.2, we express the necessary and sufficient conditions to have a solution in terms of symmetric polynomials σ.sub.1=u.sub.1+u.sub.2 and σ.sub.2=u.sub.1 u.sub.2. As is apparent, all systems of equations for unknowns σ.sub.1 and σ.sub.2 are linear systems. For the system to be consistent, we need the rank of the augmented matrix to be the same as the rank of the coefficient matrix. This leads to a system of equations for certain minors of the augmented matrix. The system is simplified and the result is put in column with heading “Constraint on s”. It should be noted that in 3 cases the constraint is empty and in the remaining 2 cases it is a linear equation s.sub.2+s.sub.3+s.sub.5=0. The condition of non-uniqueness is the condition on the rank of the augmented matrix, that the rank be smaller than the number of variables, i.e. 2. Hence, the rank must be 0 or 1, i.e. the coefficient matrix is 0 or all 2×2 minors of it must vanish. This is yet another system of equations which is simplified and put in column with heading “Non-Uniqueness Condition”. In all cases, we have the possibility of a non-unique solution. However, we assumed that we have 2 erasures and 1 error at an unknown location. In this case, we know one of the data error locators u.sub.1 or u.sub.2. We may assume that the known locator is u.sub.1 and solve for u.sub.2. After both data error locators are found, we solve a non-singular linear system to find the error values. It should be noted that we know in advance that there exists a unique solution as long as the number of erasures is Z=2 and the number of errors is E=1, by the inequality Z+2×E≤D−1=4. As an example illustrating the steps of the method, let us consider correcting a 3-error failure with 2 data errors and 1 parity error, where the parity has j=4. The second row of the table yields necessary condition s.sub.2+s.sub.3+s.sub.5=0, which must be satisfied to proceed with the following steps. We have a system of equations

(56) $\{\begin{array}{c}{s}_2{\sigma }_1+s_2{\sigma }_1=s_3\\ u_1+u_2={\sigma }_1\\ u_1{u}_2={\sigma }_2\end{array}$
where the first equation is obtained by substituting s.sub.5+s.sub.3 with s.sub.2 using a form of the constraint s.sub.2=s.sub.3+s.sub.5. Since a is known, we have a linear equation for b only after eliminating σ.sub.1 and σ.sub.2:
s.sub.2(u.sub.1+u.sub.2)+s.sub.1u.sub.1u.sub.2=s.sub.3
Therefore, (s.sub.2+s.sub.1 u.sub.1) u.sub.2=s.sub.3+s.sub.2 u.sub.1 and formally:

(57) $u_2=\frac{s_3+s_2{u}_1}{s_2+s_1{u}_1}$

(58) The solution is non-unique and non-zero (only non-zero data locators are allowed) iff s.sub.2+s.sub.1 u.sub.1=s.sub.3+s.sub.2 u.sub.1=0 which implies that either s.sub.1=s.sub.2=s.sub.3 or

(59) $u_1=\frac{s_2+s_3}{s_1+s_2}$
If s.sub.1=s.sub.2=s.sub.3, the constraint implies that s.sub.5=0. If s.sub.1=0 then s.sub.1=s.sub.2=s.sub.3=s.sub.5=0 and the error is matched by a single parity error at position j=2 which is more likely and is handled elsewhere, in an earlier step of the method. Hence, we may assume s.sub.1≠0. The equation for σ.sub.1 and σ.sub.2 becomes s.sub.1(σ.sub.2+σ.sub.2)=s.sub.1 in view of s.sub.1=s.sub.2=s.sub.3 and s.sub.1≠0 implies σ.sub.1+σ.sub.2=1, or u.sub.1+u.sub.2+u.sub.1u.sub.2=1. Hence, u.sub.1(1+u.sub.2)=u.sub.1+1. If u.sub.1=1, u.sub.2 is arbitrary (non-unique solution); if u.sub.1≠1 then u.sub.2=1. Hence, a non-unique solution only exists if we have erasure at position with locator 1. We may assume u.sub.1=1. We have s.sub.5=0. Hence u.sub.1(u.sub.1+1)=0 and u.sub.2 (u.sub.2+1) y=s.sub.5=0, where y is the error value for error locator u.sub.2. As u.sub.2 (u.sub.2+1)≠0, we have y=0. In particular, the error has only 1 failed data and 1 failed parity, and was considered elsewhere as a 2-error failure and was considered elsewhere. This ends the sequence of exemplary steps for correcting 3 errors, wherein 2 of the errors are known erasures, with some portions of analogous steps omitted, as they will be apparent to those skilled in the art.

(60) The drawings in FIG. 14 and FIG. 13 show exemplary arrangements of a preferred embodiment. Combinations of 4 errors involving 2 data errors and 2 parity errors are corrected by a sequence of steps utilizing the table of FIG. 13. Combinations of 4 errors involving 3 data errors and 1 parity error are corrected by a sequence of steps utilizing the table of FIG. 14. For Z erasures and E errors at unknown locations, statifying the inequality Z+2×E≥4 the number E=0, i.e. all errors must be erasures. Therefore, equation (13) is linear and is used only to find error values x.sub.i. In one case, all solutions can be found when Z+2×E=5, when we have 2 data errors at known locations (known erasures), 1 data error at unknown location, and 1 parity error at a known location. Using the consistency condition in the second column one shows that at most two locations of the data error at an unknown location are consistent with any syndrome vector s which is not consistent with a 3-error combination.

(61) The steps in FIG. 6 can be used to correct some combinations of 5 errors (|J|+r=5). Only combinations of 5 errors wherein all errors are known erasures can be corrected. The equation (13) is used in its linear form to correct 5 errors, because the data locators u.sub.j, j=1, 2, 3, . . . , r are known. According to some embodiments, the method of the invention provides error tolerance of a significant fraction of 5 simultaneous erasures. One combination of 5 errors which cannot be corrected is a combination consisting of 5 data erasures, because the coefficient matrix of (13) is singular. Another combination of 5 erasures which cannot be corrected is a combi-nation of 2 parity erasures at parity positions 1 and 4, and 3 data errors (J={1, 4}, r=3 in FIG. 6). All other combinations of 5 known erasures can be corrected. The fraction of such quintuples comprising a particular pair of parity strips is:

(62) $\frac{\left(\begin{array}{c}N-2\\ 3\end{array}\right)}{\left(\begin{array}{c}N\\ 5\end{array}\right)}=\frac{20}{N\times \left(N-1\right)}.$
The fraction of such quintuples consisting of 5 data symbols is:

(63) 0$\frac{\left(\begin{array}{c}N-5\\ 5\end{array}\right)}{\left(\begin{array}{c}N\\ 5\end{array}\right)}=\underset{J=0}{\overset{4}{.Math.}}\left(1-\frac{5}{N-J}\right).$
For example, when N=20, the probability of uncorrectable quintuple of erasures is 1/19≈5% plus 1001/5168≈19%, i.e. approximately ¼ of quintuple errors are not correctable. However, with N large the fraction of uncorrectable quintuple errors approaches 100%.

(64) The drawings in FIG. 16 show an exemplary arrangement of a preferred embodiment, directed towards correcting a combination of 3 errors at unknown lo-cations, using list decoding, by collecting the syndrome vectors and possible error vectors obtained during processing of multiple stripes. The steps of the exemplary arrangements are suitable to be incorporated into the list decoding branch step [52] of FIG. 6. The system (13) is:

(65) $\begin{array}{cc}\left[\begin{array}{ccc}1& 1& 1\\ u_1& u_2& u_3\\ u_1^2& u_2^2& u_3^2\\ u_1^3& u_2^3& u_3^3\\ u_1^2+u_1& u_2^2+u_2& u_3^2+u_3\end{array}\right]\left[\begin{array}{c}{x}_1\\ x_2\\ x_3\end{array}\right]=\left[\begin{array}{c}{s}_1\\ s_2\\ s_3\\ s_4\\ s_5\end{array}\right].& \left(22\right)\end{array}$
One necessary condition for system (22) to be consistent is s.sub.2+s.sub.3=s.sub.5, as the last equation is dependent. Another necessary condition is that the determinant:

(66) $\begin{array}{cc}\left[\begin{array}{cccc}1& 1& 1& s_1\\ u_1& u_2& u_3& s_2\\ u_1^2& u_2^2& u_3^2& s_3\\ u_1^3& u_2^3& u_3^3& s_4\end{array}\right]=0.& \left(23\right)\end{array}$

(67) Those skilled in the art will check that this determinant equals

(68) $\underset{j=1}{\overset{3}{.Math.}}{\left(-1\right)}^{j-1}{s}_{4-j}{\sigma }_j$
where σ.sub.1=u.sub.1+u.sub.2+u.sub.3, σ.sub.2=.sub.1 u.sub.2+u.sub.1u.sub.3+u.sub.2u.sub.3 and σ.sub.3=u.sub.1u.sub.2 u.sub.3 are the elementary symmetric polynomials. Therefore, the consistency conditions for J=ø and r=3 in FIG. 6 are

(69) $\Gamma =\{s_2+s_3+s_{5^{\prime }}\underset{j=1}{\overset{3}{.Math.}}{\left(-1\right)}^{j-1}{s}_{4-j}{\sigma }_j.$
When u.sub.1, u.sub.2 and u.sub.3 are unknown, we typically have more than one solution to (22), thus in FIG. 6 the list decoding branch step [52] will be executed. The steps of the exemplary arrangement are directed towards recovering lost data due to 3 data errors at unknown locations, using multiple syndrome vectors obtained from at least 3 distinct stripes sharing the 3 data error locations and having no parity errors. It will be apparent to those skilled in the art how to incorporate the steps of the exemplary arrangement into the list decoding branch step [52]. We focus now on the steps of FIG. 16. In the input of 3 syndrome vectors and list of data locators step [137] 3 syndromes are input obtained by collecting lists of multiple error vectors from multiple faulty stripes. Thus, it is assumed that there exists a subset l.Math.{1, 2, . . . }, wherein |l|=3, of data positions such that the 3 received vectors r.sup.(1), r.sup.(2) and, r.sup.(3) admit 3 error vectors e.sup.(1), e.sup.(2) and e.sup.(3) such that H e.sup.(t)=s.sup.(t) for t=1, 2, 3, and such that e.sup.(t)=0 unless j∈l. In the output of data error locations step [142] we output the set l={i.sub.1, i.sub.2, i.sub.3}. In solving a linear equation step [139] we solve a system of linear equations obtained by applying the consistency conditions to the 3 syndrome vectors. In solving a cubic equation for data error locators step [140] we obtain the values of u.sub.1, u.sub.2 and u.sub.3 by solving a cubic equation. In the lookup of error locations step [141] we check whether the values u.sub.1, u.sub.2 and u.sub.3 are valid data error locators by looking them up in the set α. In the output of data error locations step [142] we output the set l for further processing, e.g. finding the three error vectors e.sup.(t), t=1, 2, 3 and correcting all errors in the 3 faulty stripes. Furthermore, it will be apparent to those skilled in the art that if 4 linearly independent syndromes are found with the same set l, then |l|≥4, hence the method can exclude the possibility of 3 data errors in 3 stripes occurring at the same locations. It will be apparent to those skilled in the art how to modify the exemplary method to look for any combination of known and unknown error locations which repeats in multiple stripes. One application of the method is to identify small sets of multiple faulty disks, or disk controllers, or other computer components, which systematically generate errors at the same locations.

(70) Supplementary embodiments of the present invention feature a method for reconstituting data lost via faulty strips in the received vector by calculating said lost data from non-faulty strips comprising the associated stripe. Each stripe may contain Z+E faulty strips where Z is the number of faulty strips at known locations and E is the number of faulty strips at unknown locations, wherein Z and E are any whole, non-negative numbers satisfying the inequality Z+2×E≥4. Further details of the data recovery method are described in the appendix section of U.S. Provisional Patent Application No. 66/449,920 filed on Jan. 24, 2017, which is/are incorporated here in their entirety by reference. Additional further details of this data recovery method are featured in the appended document: (Efficient Error Correcting Codes for Dual-Disk Corruption, Moussa and Rychlik 2018).

(71) It will thus be seen that the objects set forth above, among those made apparent from the preceding description, are efficiently attained and, because certain changes may be made in carrying out the above method and in the construction(s) set forth without departing from the spirit and scope of the invention, it is intended that all matter contained in the above description and shown in the accompanying drawings shall be interpreted as illustrative and not in a limiting sense.

(72) It is also to be understood that the following claims are intended to cover all of the generic and specific features of the invention herein described and all statements of the scope of the invention which, as a matter of language, might be said to fall therebetween.

(73) Various modifications of the invention, in addition to those described herein, will be apparent to those skilled in the art from the foregoing description. Such modifications are also intended to fall within the scope of the appended claims. Each reference cited in the present application is incorporated herein by reference in its entirety.

(74) Although there has been shown and described the preferred embodiment of the present invention, it will be readily apparent to those skilled in the art that modifications may be made thereto which do not exceed the scope of the appended claims. Therefore, the scope of the invention is only to be limited by the following claims. Reference numbers recited in the claims are exemplary and for ease of review by the patent office only, and are not limiting in any way. In some embodiments, the figures presented in this patent application are drawn to scale, including the angles, ratios of dimensions, etc. In some embodiments, the figures are representative only and the claims are not limited by the dimensions of the figures. In some embodi-ments, descriptions of the inventions described herein using the phrase “comprising” includes embodiments that could be described as “consisting of”, and as such the written description requirement for claiming one or more embodiments of the present invention using the phrase “consisting of” is met.

(75) The reference numbers recited in the below claims are solely for ease of examination of this patent application, and are exemplary, and are not intended in any way to limit the scope of the claims to the particular features having the corresponding reference numbers in the drawings.

REFERENCES

(76) Anderson, M. H. and S. Mann (2014). Accelerated erasure coding system and method. U.S. Pat. No. 8,683,296. url: https://www.google.com/patents/U.S. Pat. No. 8,683,296. Anvin, Peter H. (2009). The Mathematics of RAID-6. url: https://www.kernel. org/pub/linux/kemel/people/hpa/raid6.pdf. Bairavasundaram, Lakshmi N. et al. (2008). “An Analysis of Data Corruption in the Storage Stack”. In: Trans. Storage 4.3, 8:1-8:28. issn: 1553-3077. doi: 10.1145/1416944.1416947. url: http://doi.acm.org/10.1145/1416944.1416947. Grigoriev, D. (2013). “Polynomial Complexity of Solving Systems of Few Algebraic Equations with Small Degrees”. In: LECTURE NOTES IN COMPUTER SCI-ENCE 1.8136, 136-139. url: http://www.ingentaconnect. com/content/ssam/03029743/2013/00000001/00008136/art00011. Leventhal, Adam (2009). “Triple-Parity RAID and Beyond”. In: Queue 7.11, 30:30-30:39. issn: 1542-7730. doi: 10.1145/1661785.1670144. url: http://doi.acm.org/10.1145/1661785.1670144. Mann, Sarah Edge (2013). The Original View of Reed-Solomon Coding and the Welch-Berlekamp Decoding Algorithm. url: http://hdl.handle.net/10150/301533. Moon, Todd K. (2005). “Linear Block Codes”. In: Error Correction Coding. John Wiley & Sons, Inc., 83-112. isbn: 9780471739210. doi: 10.1002/0471739219. ch3. url: http://dx.doi.org/10.1002/0471739219.ch3. Moussa, Mohamad and Marek Rychlik (2018). Efficient Error Correcting Codes for Dual-Disk Corruption. Submitted to USPTO as a document accompanying the non-provisional utility patent on Jan. 19, 2018; extended and updated version of the paper submitted on Jan. 24, 2017 with the provisional patent applica-tion. Plank, James S. (1997). “A Tutorial on Reed-Solomon Coding for Fault-Tolerance in RAID-like Systems”. In: Software—Practice & Experience 27.9, 995-1012. Plank, James S. and Y. Ding (2005). “Note: Correction to the 1997 Tutorial on Reed-Solomon Coding”. In: Software—Practice & Experience 35.2, 189-194. Rozier, Eric W. D. et al. (2009). “Evaluating the impact of Undetected Disk Errors in RAID systems”. English. In: 83-92. isbn: 9781424444229; 1424444225; Schönhage, Arnold and Volker Strassen (1971). “Schnelle Multiplikation groller Zahlen.” In: Computing 7.3-4, 281-292. url: http://dblp.uni-trer.de/db/joumals/computing/computing7.html#SchonhageS71.