OPTIMIZING XOR-BASED CODES

• US 20090164762A1
• Filed: 12/20/2007
• Published: 06/25/2009
• Est. Priority Date: 12/20/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 8,209,577 B2
• Time in Patent Office: Days
• US Class Current: 712/223
• CPC Class Codes: H03M 13/033 Theoretical methods to calculate these checking codes
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• 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
• CPC Class Codes: H03M 13/611 Specific encoding aspects, e.g. encoding by means of decoding
• CPC Class Codes: H03M 13/6502 Reduction of hardware complexity or efficient processing

Abstract

A “code optimizer” provides various techniques for optimizing arbitrary XOR-based codes for encoding and/or decoding of data. Further, the optimization techniques enabled by the code optimizer do not depend on any underlining code structure. Therefore, the optimization techniques provided by the code optimizer are applicable to arbitrary codes with arbitrary redundancy. As such, the optimized XOR-based codes generated by the code optimizer are more flexible than specially designed codes, and allow for any desired level of fault tolerance. Typical uses of XOR-based codes include, for example, encoding and/or decoding data using redundant data packets for data transmission real-time communications systems, encoding and/or decoding operations for storage systems such as RAID arrays, etc.

Claims

1. A method for optimizing a coding operation of arbitrary erasure correcting codes, comprising using a computing device for:

receiving an erasure correcting code;

determining all XOR operations required to compute all required erasure correcting code outputs from two or more code inputs;

evaluating the XOR operations to identify a set of one or more shared XOR operations, where each shared XOR operation represents an XOR operation performed on two or more common code inputs which is used for computing two or more different erasure correcting code outputs;

computing a result of each shared XOR operation of the set of one or more shared XOR operations; and

constructing an optimized version of the erasure correcting code by using the computed result of each shared XOR operation to replace all corresponding XOR operations for computing the two or more different erasure correcting code outputs.

2. The method of claim 1 wherein determining all XOR operations required to compute all required erasure correcting code outputs from the code inputs further comprises:

transforming the coding operations of the erasure correcting code into a matrix format; and

evaluating the matrix to identify XOR operations of two or more of the code inputs that are common to two or more of the outputs.

3. The method of claim 2, wherein a set of commonly occurring erasure patterns are pre-computed, and wherein a resulting matrix of each corresponding decode operation of each of the erasure patterns is optimized and cached in memory.

4. The method of claim 1 further comprising constructing a graph having nodes and edges between two or more of the nodes;

wherein each node represents a different one of the code inputs;

wherein each edge corresponds to an XOR operation of the inputs represented by the node on each end of the edge; and

further comprising assigning an edge counter value to each edge, said edge counter value representing a number times that the corresponding XOR operation is required to compute all required erasure correcting code outputs.

5. The method of claim 4 wherein evaluating the XOR operations to identify the set of one or more shared XOR operations further comprises:

removing all edges from the graph having an edge counter value that is less than a maximum of the all edge counter values of the graph;

evaluating the remaining edges and identifying one or more maximal matchings of edges in the graph;

selecting one of the identified maximal matchings of edges; and

identifying XOR operations corresponding to all of the edges in the selected maximal matching of edges as the set of one or more shared XOR operations.

6. The method of claim 5 further comprising:

for each node, counting a total number of edges entering each node prior to removal of the edges; and

after removal of the edges, assigning an edge weight to each remaining edge as a function of a sum of the total number of edges that entered each of the two nodes on either end of each corresponding edge.

7. The method of claim 6 wherein selecting one of the identified maximal matchings of edges further comprises selecting the maximal matching of edges having a highest total weight based on a sum of the corresponding edge weights.

8. A process for reducing a total number of XOR operations in an arbitrary erasure correcting code, comprising steps for:

receiving a binary matrix representing an erasure correcting code, said matrix including a non-zero value in each corresponding location of the matrix whenever a particular matrix input is required to compute a particular matrix output;

wherein computing each of the matrix outputs involves performing an XOR operation between all matrix inputs having a corresponding non-zero value in the matrix for the particular matrix output being computed;

searching the matrix to identify a set of one or more shared XOR operations wherein a shared XOR operation is an XOR operation between any two common matrix inputs that is required to compute two or more different matrix outputs; and

constructing an optimized coding matrix by replacing each shared XOR operation with a corresponding result of a single computation of each corresponding shared XOR operation.

9. The process of claim 8 further comprising steps for constructing a graph having nodes and edges between two or more of the nodes;

wherein each node represents a different one of the matrix inputs;

wherein each edge corresponds to an XOR operation of the matrix inputs represented by the node on each end of the edge; and

further comprising assigning an edge counter value to each edge, said edge counter value representing a number times that the corresponding XOR operation is required to compute all of the matrix outputs.

10. The process of claim 9 wherein searching the matrix to identify the set of one or more shared XOR operations further comprises steps for:

removing all edges from the graph having an edge counter value that is less than a maximum of the all edge counter values of the graph;

evaluating the remaining edges and identifying one or more maximal matchings of edges in the graph;

selecting one of the identified maximal matchings of edges; and

identifying XOR operations corresponding to all of the edges in the selected maximal matching of edges as the set of one or more shared XOR operations.

11. The process of claim 10 further comprising:

for each node, counting a total number of edges entering each node prior to removal of the edges; and

after removal of the edges, assigning an edge weight to each remaining edge as a function of a sum of the total number of edges that entered each of the two nodes on either end of each corresponding edge.

12. The process of claim 11 wherein selecting one of the identified maximal matchings of edges further comprises selecting the maximal matching of edges having a highest total weight based on a sum of the corresponding edge weights.

13. The process of claim 8 wherein an erasure encoding operation is performed, and wherein:

matrix inputs represent data packets of a distributed data storage node; and

matrix outputs represent erasure coded data packets that are coded using the optimized coding matrix.

14. The process of claim 8 wherein:

the optimized coding matrix represents a decoding matrix for a particular one of a set of all possible erasure patterns of the erasure correcting code; and

wherein a separate optimized coding matrix is constructed for each desired erasure pattern from the set of all possible erasure patterns of the erasure correcting code.

15. A computer-readable medium having computer executable instructions stored thereon for optimizing an XOR based code, comprising instructions for:

receiving a binary coding matrix representing XOR operations of erasure correcting code inputs for applying an erasure correcting code to the inputs to produce erasure correcting code outputs;

evaluating the binary coding matrix to identify all shared XOR operations; and

constructing an optimized binary coding matrix by replacing all shared XOR operations with a single computation of a corresponding one of the shared XOR operations.

16. The computer-readable medium of claim 15 wherein evaluating the binary coding matrix to identify all shared XOR operations comprises:

constructing a graph having nodes and edges between two or more of the nodes;

wherein each node represents a different one of the inputs;

wherein each edge corresponds to an XOR operation of the inputs represented by the node on each end of the edge; and

further comprising assigning an edge counter value to each edge, said edge counter value representing a number times that the corresponding XOR operation is required to compute all erasure correcting code outputs.

17. The computer-readable medium of claim 16 wherein evaluating the binary coding matrix to identify all shared XOR operations further comprises:

removing all edges from the graph having an edge counter value that is less than a maximum of the all edge counter values of the graph;

evaluating the remaining edges and identifying one or more maximal matchings of edges in the graph;

selecting one of the identified maximal matchings of edges; and

identifying XOR operations corresponding to all of the edges in the selected maximal matching of edges as all of the shared XOR operations.

18. The computer-readable medium of claim 17 further comprising:

for each node, counting a total number of edges entering each node prior to removal of the edges; and

after removal of the edges, assigning an edge weight to each remaining edge as a function of a sum of the total number of edges that entered each of the two nodes on either end of each corresponding edge.

19. The computer-readable medium of claim 18 wherein selecting one of the identified maximal matchings of edges further comprises selecting the maximal matching of edges having a highest total weight based on a sum of the corresponding edge weights.

20. The computer-readable medium of claim 16 the optimized binary coding matrix represents a decoding matrix for a particular one of a set of all possible erasure patterns of the erasure correcting code;

and

wherein a separate optimized coding matrix is constructed for each desired erasure pattern from the set of all possible erasure patterns of the erasure correcting code.