Encoding apparatus for RAID-6 system and tape drives
AssigneeQuantum Corporation
InventorLih-Jyh Weng
Life of this patent
Estimating the term…
Abstract
An encoding/decoding system for RAID-6 or multiple track tape systems uses one of a selected set of values for m, with m+1 prime and the field GF(2.sup.m) generated by the irreducible polynomial: g(x)=x.sup.m +x.sup.m-1 + . . . +x.sup.2 +x+1. The system performs Galois Field multiplication operations as a combination of cyclic shifting and exclusive-OR operations, and determines multiplicative inverses of weight one, two and three (m+1)-bit symbols by raising various (m+1)-bit symbols to selected powers of two. Using this system, the value of m may be chosen to be as large as or larger than the sector or tape block, and the encoding and decoding is performed once per sector or block.
Claims14
A system for encoding m-bit data symbols from k data disks to produce m-bit redundant symbols for r redundant disks by encoding corresponding symbols from each of the k data disks, the system including:
- A. means for receiving data from corresponding sectors of the k data disks;
- B. encoding means for producing (m+1)-bit redundant symbols as
- c.sub.y =.alpha..sup.y*(k-1) i.sub.k-1 +.alpha..sup.y*(k-2) i.sub.k-2 + . . . +.alpha..sup.y*(1) i.sub.1 +i.sub.0
- for y=0, 1, . . . r-1 where j.sub.j is the data from the j.sup.th data disk, and .alpha. is an (m+1)-bit representation of an element of GF(2.sup.m), with m+1 prime, said means including for each c.sub.y :
- i. a shift register for performing the multiplication operations as y-bit cyclic shifts, and
- ii. an adder for adding to the contents of the shift register the corresponding data from a next data disk;
- C. converting means for converting the (m+1)-bit redundant symbols to m-bit redundant symbols;
- and
- D. means for storing the m-bit redundant symbols in corresponding sectors of the r redundant disks.
A system for encoding m-bit data symbols from k tracks of a (k+r)-track tape to produce m-bit redundant symbols for r redundant tracks by encoding corresponding symbols from each of the k data tracks, the system including:
- A. means for receiving data from corresponding blocks of the k data tracks;
- B. encoding means for producing (m+1)-bit redundant symbols as
- c.sub.y =.alpha..sup.y*(k-1) l i.sub.k-1 +.alpha..sup.y*(k-2) i.sub.k-2 + . . . +.alpha..sup.y*(1) i.sub.1 +i.sub.0
- for y=0, 1, . . . r-1 where i.sub.j is the data from the j.sup.th data track, and .alpha. is an (m+1)-bit representation of an element of GF(2.sup.m), with m+1 prime, said means including for each C.sub.r :
- i. a shift register for performing the multiplication operations as y-bit cyclic shifts, and
- ii. an adder for adding to the contents of the shift register the corresponding data from a next data track;
- C. converting means for converting the (m+1)-bit redundant symbols to m-bit redundant symbols;
- and
- D. means for storing the m-bit redundant symbols in corresponding blocks of the r redundant tracks.
A decoder for correcting errors in corresponding sectors of k data disks using redundant symbols that are stored lorresponding sectors on r redundant disks, the decoder including:
- A. means for receiving data from the k data disks;
- B. decoding means for producing (m+1)-bit redundant symbols as
- c.sub.y .alpha..sup.y*(k-1) i.sub.k-1 +.alpha..sup.y*(k-2) i.sub.k-2 + . . . +.alpha..sup.y*(1) i.sub.1 +i.sub.0
- for y=0, 1, . . . r-1 where i.sub.j is error-free data from the j.sup.th data disk or if the data on the j.sup.th disk is erroneous all zeros, and .alpha. is an (m+1)-bit representation of an element of GF(2.sup.m), with m+1 prime, said means including for each c.sub.r :
- i. a shift register for performing the multiplication operations as y-bit cyclic shifts, and
- ii. an adder for adding to the contents of the shift register the data from a next data disk;
- C. a syndrome generator for producing syndromes S.sub.j, S.sub.j+1 . . . S.sub.j+z-1, where z is the number of disks containing erroneous data, the syndrome generator producing S.sub.j =
- (.alpha..sup.j).sup.e.spsp.0 *i'.sub.e0 +(.alpha..sup.j).sup.e1 *i'.sub.el + . . . +(.alpha..sup.j).sup.ez *i'.sub.ez
- for j=0, 1, . . . , r-1, where i'.sub.ez is the error pattern associated with the z.sup.th erroneous disk, and S.sub.j is the syndrome associated with the j.sup.th redundant disk.
- D. means for determining error values associated with the syndromes, said means including means for determining multiplicative inverses of (m+1)-bit symbols (.alpha..sup.j).sup.p with weight one as .alpha..sup.m+1-jp ;
- E. converting means for converting the (m+1)-bit error value to an m-bit error value;
- and
- F. means for correcting the erroneous m-bit symbols using the m-bit error value.
A decoder for correcting errors in corresponding blocks of k data tracks of a multiple track tape system using redundant symbols that are stored in corresponding blocks on r redundant tracks, the decoder including:
- A. means for receiving data from the k data tracks;
- B. decoding means for producing (m+1)-bit redundant symbols as
- c.sub.y =.alpha..sup.y*(k-1) i.sub.k-1 +.alpha..sup.y*(k-2) i.sub.k-2 + . . . +.alpha..sup.y*(1) i.sub.1 +i.sub.0
- for y=0, 1, . . . r-1 where i.sub.j is error-free data from the j.sup.th data track or if the data on the j.sup.th track is erroneous all zeros, and .alpha. is an (m+1)-bit representation of an element of GF(2.sup.m), with m+1 prime, said means including for each c.sub.r :
- i. a shift register for performing the multiplication operations as r-bit cyclic shifts, and
- ii. an adder for adding to the contents of the shift register the data from a next data track;
- C. a syndrome generator for producing syndromes S.sub.j, S.sub.i+1 . . . S.sub.j+z-1, where z is the number of tracks containing erroneous data, the syndrome generator producing S.sub.j =
- (.alpha..sup.j).sup.e0 *i'.sub.e0 +(.alpha..sup.j).sup.e1 *i'.sub.e1 + . . . +(.alpha..sup.j).sup.ez *i'.sub.ez
- for j=0, 1, . . . , r-1, where i'.sub.ez is the error pattern associated with the z.sup.th erroneous track, and S.sub.j is the syndrome associated with the j.sup.th redundant track.
- D. means for determining error values associated with the syndromes, said means including means for determ iing multiplicative inverses of (m+1)-bit symbols (.alpha..sup.j).sup.p with weight one as .alpha..sup.m+1-jp ;
- E. converting means for converting the (m+1)-bit error value to an m-bit error value;
- and
- F. means for correcting the erroneous m-bit symbols using the m-bit error value.
Dependencies are inferred from the claim text.