Erasure-resilient codes having multiple protection groups
First Claim
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 using a computing device 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 Assignments
0 Petitions
Accused Products
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.
-
Citations
20 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 using a computing device 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
-
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;assigning one of the original parity chunks to each one of the protection groups to protect the data; 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 using the computer to encode the data using the basic MPG Code. - View Dependent Claims (11, 12, 13, 14)
- k) original parity chunks, comprising;
-
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 using a computing device to decode 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. - View Dependent Claims (16, 17, 18, 19, 20)
-
Specification