Multiple protection group codes having maximally recoverable property

• US 7,904,782 B2
• Filed: 03/09/2007
• Issued: 03/08/2011
• Est. Priority Date: 03/09/2007
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Chen, Minghua, Huang, Cheng, Li, Jin
• Primary Examiner(s): RIZK, SAMIR WADIE
• Application Number:
  US11/684,589
• Publication Number:
  US 20080222481A1
• Time in Patent Office: 1,460 Days
• Field of Search: 714/752, 714/755, 714/758, 714/786, 714/801
• 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/2703 the interleaver involving at least two directions
• 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

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 constructing a Multiple Protection Group (MPG) code having a Maximally Recoverable (MR) property for coding data having n total chunks, k number of data chunks, and m parity chunks, wherein m=n−

k, comprising;

using a computing device to perform the following;

organizing the data chunks into multiple protection groups;

assigning at least one of the m parity chunks to each of the multiple protection groups;

constructing a n×

k generator matrix, wherein the generator matrix has n rows and k columns and rank k corresponding to every recoverable erasure pattern;

assigning each row vector of the generator matrix to one of the protection groups;

filling the generator matrix in a deterministic manner; and

encoding the data using the constructed MPG code having the MR property.

2. The method of claim 1, wherein filling the generator matrix in a deterministic manner further comprises:

starting from a lock identity matrix and then adding one row at a time to the generator matrix;

defining a g_m row vector as a (k+m)^th row of the generator matrix and corresponding to a m^th parity chunk;

defining G_m as a truncated generator matrix of a top (k+i) row, wherein i ranges from 1 to k; and

identifying a non-zero position of the g_m row vector.

3. The method of claim 2, wherein a g_m row vector corresponding to the m^th parity chunk is defined by:

setting the an entry to non-zero for each entry in the generator matrix corresponding to data chunks in a same protection group; and

setting the entry equal to zero for each entry in the generator matrix not corresponding to data chunks in a same protection group.

4. The method of claim 2, further comprising constructing a null space matrix that contains null space vectors formed from a submatrix in the truncated generator matrix, wherein the submatrix has rank k−

1 and can be combined with the g_m row vector to form a generator submatrix having full rank k.

5. The method of claim 4, further comprising finding a new g_m row vector such that for a null space matrix row vector in the null space matrix the dot product of the null space matrix row vector and the g_m row vector is not equal to zero.

6. The method of claim 5, further comprising finding a row vector 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.

7. A computer-implemented process for decoding data encoded using Multiple Protection Group (MPG) code having a Maximally Recoverable (MR) property, comprising:

using the computer to perform the following;

constructing a square decoding matrix having full rank that corresponds to the optimal decoding matrix;

finding an atomic assignment using a configuration that represents a structural relationship between data symbols and parity symbols; and

using the atomic assignment and decoding matrix to decode the encoded data.

8. The computer-implemented process of claim 7, further comprising constructing a partial configuration having a minimum possible number of data symbols, wherein the partial configuration is a portion of the configuration.

9. The computer-implemented process of claim 8, further comprising searching over all possible combinations of the partial configuration by taking additional protection groups into consideration.

10. The computer-implemented process of claim 9, further comprising:

constructing an initial set of atom sets by going over all atomic assignments of parity symbols in set of possible parity symbols that can be used to recover erasures in an atom set;

constructing a second set of atom sets containing encoded data symbols that are protected by assign parity symbols;

determining whether the initial set equals the second set;

if so, then concluding that the current configuration is sufficient and decoding the data using the current configuration;

if not, augmenting the initial set equal to have the initial set equal the second set.

determining whether atomic assignments have been found for all atom sets in the augmented initial set;

if so, then repeating the process above; and

if not, then processing a next available atomic assignments.

11. A method for decoding data, comprising:

using a computing device to perform the following;

determining that the data was encoded using a Multiple Protection Group (MPG) code having a Maximally Recoverable (MR) property and that there are multiple decoding techniques that may be used to recover failed data chunks of the data; and

finding a minimum decoding cost; and

selecting a decoding technique from the multiple decoding techniques having the minimum decoding cost to decode the data.

12. The method of claim 11, further comprising using a Tanner graph to find the minimum decoding cost by finding a minimum recovery path for access of a single failed data chunk.

13. The method of claim 12, wherein the minimum recovery path uses the same number of parities and data chunks to recover all failed data chunks and all failed parity chunks.

14. The method of claim 12, further comprising finding a minimum overall recovery cost that corresponds to the minimum recovery path to decode all failed data chunks and to reconstruct all failed parity chunks.

15. The method of claim 14, wherein finding a minimum overall recovery cost further comprises:

finding a plurality of subsets of parities;

selecting a subset of parities for a given erasure pattern such that a size of each subset equals the number of data erasures; and

examining each of the plurality of subsets of parities.

16. The method of claim 15, wherein examining each of the plurality of subsets of parities further comprises:

determining whether a full size matching exists in the Tanner graph, wherein a full size matching is a matching having a size equal to a number of failed data chunks corresponding to a number of data nodes in the Tanner graph;

if a full size matching exists in the Tanner graph, then determine a recovery cost of recovering the failed data chunks and the failed parity chunks; and

if full size matching does not exists, then skipping the selected subset and selecting another subset.

17. The method of claim 11, further comprising finding a minimum read access overhead of a particular failed data chunk.

18. The method of claim 17, wherein finding a minimum read access overhead further comprises:

performing a breadth search starting at a first node in the Tanner graph;

if the search encounters a left node in the Tanner graph corresponding to a data erasure, then following a link in the matching to a corresponding right node in the Tanner graph.

19. The method of claim 18, further comprising if the search encounters a right node in the Tanner graph, then following a link in the matching to all left nodes in the Tanner graph that have not been visited previously.

20. The method of claim 19, further comprising continuing the search until a set of right nodes already visited become large enough to recover a set of left nodes already visited.