Error correction for data communication
View Patent ↗Generating a check matrix includes defining a generator function operable to yield check bits associated with a word. A set of primitive elements is calculated from the generator function. A set of check matrix columns is generated, where each check matrix column includes a matrix having a subset of the set of primitive elements. A check matrix is generated from a subset of the set of check matrix columns, where the check matrix yields a syndrome that comprises an error pattern for the word. The check matrix is reported.
1. A method for generating a check matrix, comprising:
defining a generator function operable to yield a plurality of check bits associated with a word;
calculating a set of primitive elements from the generator function;
generating a set of check matrix columns, each check matrix column comprising a matrix comprising a subset of the set of primitive elements;
generating a check matrix from a subset of the set of check matrix columns, the check matrix operable to yield a syndrome that comprises an error pattern for the word; and
reporting the check matrix.
2. The method of claim 1 , wherein each check matrix column comprises an identity matrix and a zero matrix.
3. The method of claim 1 , further comprising repeating the following for a number of iterations:
generating a plurality of subsets of the set of check matrix columns; and
generating a check matrix from a subset of the set of check matrix columns.
4. The method of claim 1 , further comprising repeating the following until a weight condition is satisfied:
generating a plurality of subsets of the set of check matrix columns;
generating a check matrix from a subset of the set of check matrix columns; and
determining a weight of the check matrix.
5. The method of claim 1 , further comprising repeating the following for a number of iterations:
generating a plurality of subsets of the set of check matrix columns;
generating a check matrix from a subset of the set of check matrix columns, the check matrix comprising a plurality of submatrices, the submatrices being members of a set of valid submatrices;
determining that the check matrix is not valid;
determining one or more invalid submatrices of the check matrix; and
removing the one or more invalid submatrices from the set of valid submatrices.
6. The method of claim 1 , further comprising:
defining a check matrix rule; and
generating a check matrix that satisfies the check matrix rule.
7. A system for generating a check matrix, comprising:
a database operable to store a generator function operable to yield a plurality of check bits associated with a word;
a primitive element generator coupled to the database and operable to calculate a set of primitive elements from the generator function; and
a check matrix generator coupled to the database and operable to:
generate a set of check matrix columns, each check matrix column comprising a matrix comprising a subset of the set of primitive elements;
generate a check matrix from a subset of the set of check matrix columns, the check matrix operable to yield a syndrome that comprises an error pattern for the word; and
report the check matrix.
8. The system of claim 7 , wherein each check matrix column comprises an identity matrix and a zero matrix.
9. The system of claim 7 , wherein the check matrix generator is further operable to repeat the following for a number of iterations:
generating a plurality of subsets of the set of check matrix columns; and
generating a check matrix from a subset of the set of check matrix columns.
10. The system of claim 7 , wherein the check matrix generator is further operable to repeat the following until a weight condition is satisfied:
generating a plurality of subsets of the set of check matrix columns;
generating a check matrix from a subset of the set of check matrix columns; and
determining a weight of the check matrix.
11. The system of claim 7 , wherein the check matrix generator is further operable to repeat the following for a number of iterations:
generating a plurality of subsets of the set of check matrix columns;
generating a check matrix from a subset of the set of check matrix columns, the check matrix comprising a plurality of submatrices, the submatrices being members of a set of valid submatrices;
determining that the check matrix is not valid;
determining one or more invalid submatrices of the check matrix; and
removing the one or more invalid submatrices from the set of valid submatrices.
12. The system of claim 7 , wherein the check matrix generator is further operable to:
define a check matrix rule; and
generate a check matrix that satisfies the check matrix rule.
13. A logic for generating a check matrix, the logic encoded in a medium and operable to:
define a generator function operable to yield a plurality of check bits associated with a word;
calculate a set of primitive elements from the generator function;
generate a set of check matrix columns, each check matrix column comprising a matrix comprising a subset of the set of primitive elements;
generate a check matrix from a subset of the set of check matrix columns, the check matrix operable to yield a syndrome that comprises an error pattern for the word; and
report the check matrix.
14. The logic of claim 13 , wherein each check matrix column comprises an identity matrix and a zero matrix.
15. The logic of claim 13 , wherein the logic is further operable to repeat the following for a number of iterations:
generating a plurality of subsets of the set of check matrix columns; and
generating a check matrix from a subset of the set of check matrix columns.
16. The logic of claim 13 , wherein the logic is further operable to repeat the following until a weight condition is satisfied:
generating a plurality of subsets of the set of check matrix columns;
generating a check matrix from a subset of the set of check matrix columns; and
determining a weight of the check matrix.
17. The logic of claim 13 , wherein the logic is further operable to repeat the following for a number of iterations:
generating a plurality of subsets of the set of check matrix columns;
generating a check matrix from a subset of the set of check matrix columns, the check matrix comprising a plurality of submatrices, the submatrices being members of a set of valid submatrices;
determining that the check matrix is not valid;
determining one or more invalid submatrices of the check matrix; and
removing the one or more invalid submatrices from the set of valid submatrices.
18. The logic of claim 13 , wherein the logic is further operable to:
define a check matrix rule; and
generate a check matrix that satisfies the check matrix rule.
19. A method for generating a check matrix, comprising:
means for defining a generator function operable to yield a plurality of check bits associated with a word;
means for calculating a set of primitive elements from the generator function;
means for generating a set of check matrix columns, each check matrix column comprising a matrix comprising a subset of the set of primitive elements;
means for generating a check matrix from a subset of the set of check matrix columns, the check matrix operable to yield a syndrome that comprises an error pattern for the word; and
means for reporting the check matrix.
20. A method for generating a check matrix, comprising:
defining a generator function operable to yield a plurality of check bits associated with a word;
calculating a set of primitive elements from the generator function;
repeating the following until a weight condition is satisfied:
generating a set of check matrix columns, each check matrix column comprising a matrix comprising a subset of the set of primitive elements, each check matrix column comprising an identity matrix and a zero matrix;
generating a check matrix from a subset of the set of check matrix columns, the check matrix operable to yield a syndrome that comprises an error pattern for the word; and
determining a weight of the check matrix;
repeating the following for a number of iterations:
generating a check matrix comprising a plurality of submatrices, the submatrices being members of a set of valid submatrices;
determining that the check matrix is not valid;
determining one or more invalid submatrices of the check matrix; and
removing the one or more invalid submatrices from the set of valid submatrices; and
reporting the check matrix.