ERASURE-RESILIENT CODES HAVING MULTIPLE PROTECTION GROUPS

• US 20080222480A1
• Filed: 03/09/2007
• Published: 09/11/2008
• Est. Priority Date: 03/09/2007
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Li, Jin, Chen, Minghua, Huang, Cheng
• Granted Patent: US 7,930,611 B2
• Time in Patent Office: Days
• US Class Current: 714/752
• CPC Class Codes: H03M 13/1191 Codes on graphs other than LDPC codes
• CPC Class Codes: H03M 13/15 Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes H03M13/17 takes precedence
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/27 using interleaving techniques
• CPC Class Codes: H03M 13/2906 using block codes H03M13/2957 takes precedence
• CPC Class Codes: H03M 13/2909 Product codes
• CPC Class Codes: H03M 13/2918 with error correction codes in three or more dimensions, e.g. 3-dimensional product code where the bits are arranged in a cube
• CPC Class Codes: H03M 13/2921 wherein error correction coding involves a diagonal direction
• CPC Class Codes: H03M 13/373 with erasure correction and erasure determination, e.g. for packet loss recovery or setting of erasures for the decoding of Reed-Solomon codes

Abstract

A multiple protection group (MPG) erasure-resilient coding method for constructing MPG codes for encoding and decoding data. The MPG codes constructed herein protect data chunks of data in multiple protection groups and subgroups. In general, the MPG erasure-resilient codes are constructed by locating data chunks into multiple protection groups and assigning at least one parity chunk to each protection group. Basic MPG codes are constructed from existing Maximum Distance Separable (MDS) codes by splitting at least some of the parity chunks into local parities for each of the multiple protection groups and projecting local parities onto each of the groups. Generalized MPG codes have a Maximally Recoverable property that can be used to determine whether an erasure pattern is recoverable or unrecoverable. Generalized MPG codes can recover any erasure pattern that is recoverable.

Claims

1. A method of coding and decoding data, comprising:

organizing a plurality of data chunks of the data into multiple protection groups;

encoding the data chunks and generating parity chunks in each of the multiple protection groups;

assigning one parity chunk to each protection group to protect the data in that protection group; and

decoding upon demand failed data chunks or failed parity chunks from available data chunks and available parity chunks from at least one of the multiple protection groups to recover any failed data chunks or failed parity chunks.

2. The method of claim 1, wherein organizing the multiple protection groups further comprises:

organizing in a hierarchical way that one global protection group contains several local protection groups, each of which may contain sub-local protection groups; and

encoding further comprises splitting at least some of the plurality of parity chunks in the global protection group into local parities for each of the multiple local protection groups.

3. The method of claim 2, further comprising calculating local parity chunks by projecting each of the parity chunks onto each of the local protection groups.

4. The method of claim 2, wherein decoding further comprises:

examining a level of a plurality of hierarchical levels in the encoded data to determine whether a number of failed data chunks in a level is less than or equal to a number of available parity chunks; and

decoding the failed data chunks from the available parity chunks when the number of failed data chunks is less than or equal to the number of available parity chunks.

5. The method of claim 4, further comprising:

concluding that there are additional failed data chunks when a number of failed data chunks is greater than the number of available parity chunks;

examining the next higher level of the plurality of hierarchical levels;

combining local parity chunks back into a global parity chunk; and

determining whether the additional failed data chunks can be recovered.

6. The method of claim 1, wherein encoding further comprises forming a generator matrix by:

identifying a non-zero position of a row vector corresponding to one of the parity chunks; and

constructing a null space matrix to hold all null space vectors.

7. The method of claim 6, further comprising forming the generator matrix row by row such that each row vector is formed such that for every element in the null space matrix the dot product of the element and the row vector is not equal to zero.

8. The method of claim 1, wherein decoding further comprises:

constructing a first atom set;

going over all atomic assignments of parity symbols;

constructing a second atom set containing encoded data symbols;

determining whether the first set equals the second set; and

determining that a current configuration is sufficient when the first set equals the second set; and

processing the next available atomic assignments until all recoverable data has been decoded.

9. The method of claim 8, further comprising augmenting the first atom set to equal the second atom set when the first atom set does not initially equal the second atom set.

10. A computer-implemented process for constructing a basic Multiple Protection Group (MPG) Code for erasure encoding data having k original data chunks starting from a (n,k) Maximum Distance Separable (MDS) erasure code having n total chunks and (n−

k) original parity chunks, comprising;

organizing the k original data chunks into L number of protection groups, wherein L is greater than one;

assigning the (n−

k) original parity chunks into a global parity group and a local parity group;

splitting each of the original parity chunks in the local parity group into L number of local parities to generate the basic MPG Code; and

encoding the data using the basic MPG Code.

11. The computer-implemented process of claim 10, further comprising projecting each of the L number of local parities onto each of the L number of protection groups.

12. The computer-implemented process of claim 10, further comprising assigning each of the original parity chunks in the global parity group to protect the k original data chunks from the L number of protection groups.

13. The computer-implemented process of claim 10, wherein the L number of protection groups are disjoint groups such that none of the protection groups have common elements.

14. The computer-implemented process of claim 10, wherein each of the protection groups forms an MDS code.

15. A method for decoding data encoded using a basic Multiple Protection Group (MPG) Code having a plurality of hierarchical levels, comprising:

determining at a bottom level of the plurality of hierarchical levels whether a first number of lost data chunks is smaller than or equal to a first number of available parity chunks;

if the first number of lost data chunks is smaller than or equal to the first number of available parity chunks, then decoding each of the lost data chunks and available parity chunks;

designating each of the decoded lost data chunks and each of the decoded parity chunks as available;

otherwise, if the first number of lost data chunks is greater than the first number of available parity chunks, then concluding that there are additional lost data chunks; and

examining a next higher level of the plurality of hierarchical levels to see whether the lost data chunks can be recovered.

16. The method of claim 15, wherein examining a next higher level of the plurality of hierarchical levels further comprises:

designating the next higher level of the plurality of hierarchical levels as a current level;

examining each group at the current level to determine whether parities at a level below the current level can be combined into parities at the current level;

determining at the current level whether a second number of lost data chunks is smaller than or equal to a second number of available parity chunks;

if the second number of lost data chunks is smaller than or equal to the second number of available parity chunks, then decoding each of the lost data chunks and available parity chunks; and

designating each of the decoded lost data chunks and each of the decoded parity chunks as available.

17. The method of claim 16, further comprising:

if the second number of lost data chunks is greater than the second number of available parity chunks, then concluding that there are additional lost data chunks; and

examining a next higher level above the current level to determine whether the lost data chunks can be recovered.

18. The method of claim 17, further comprising repeating the process until each level of the plurality of hierarchical levels has been examined or until each of the lost data chunks has been recovered.

19. The method of claim 18, further comprising finding that subgroup parities at a same position or column in a group are available.

20. The method of claim 19, further comprising:

finding that each of the parities at one particular position in a group are available; and

combining each of the parities at the one particular position into a single group parity.