Multiple protection group codes having maximally recoverable property
First Claim
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 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 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. - View Dependent Claims (2, 3, 4, 5, 6)
- k, comprising;
-
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. - View Dependent Claims (8, 9, 10)
-
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. - View Dependent Claims (12, 13, 14, 15, 16, 17, 18, 19, 20)
Specification