Very low complexity SECDED codes
A data storage device has a controller that is configured to generate SECDED codes based on a plurality (at least 2) of codes, where each of the constituent codes is a cyclic code over a finite field of size 2 m for some integer m. Any 2 constituent codes are associated with 2 m1 and 2 m2 , where m1 and m2 are coprime (i.e., gcd(m1,m2)=1) where gcd is the greatest common divisor. In such a case, it is possible to generate a cyclic code of length (2 m1 −1)*(2 m2 −1), which will be a long code, but enjoy the complexity, in encoding and decoding, of the small fields of the constituent codes.
1. A data storage device, comprising:
a memory device; and
a controller coupled to the memory device, the controller configured to:
retrieve a codeword from the memory device;
determine a first Galois Field GF(2 m1 ) and a second Galois Field GF(2 m2 ) for the codeword, wherein m1+m2+1=m and m is an integer;
generate a single error correcting cyclic code of a first length;
generate a SECDED cyclic code of a second length, wherein the second length is different from the first length;
generate a first binary matrix corresponding to the single error correcting cyclic code;
generate a second binary matrix corresponding to the SECDED cyclic code;
generate a parity check matrix;
rotate the single error correcting cyclic code of the first length until either an error is present in the parity check matrix or a first number of rotations has occurred, wherein the first number of rotations corresponds to a number of parity bits of the parity check matrix divided by a number of bits of data of the single error cyclic code;
rotate the SECDED cyclic code of the second length until either the error is present in the parity check matrix or a second number of rotations has occurred, wherein the second number of rotations corresponds to the number of parity bits of the parity check matrix divided by a number of bits of data of the SECDED cyclic code; and
upon determining a location of the error, flip a bit corresponding to the location.
2. The data storage device of claim 1 , wherein the rotating the single error correcting cyclic code of the first length rotates by a rotation amount equal to m1.
3. The data storage device of claim 1 , wherein rotating the SECDED cyclic code of the second length rotates by a rotation amount equal to m2+1.
4. The data storage device of claim 1 , wherein m is equal to a number of parity bits for the codeword.
5. The data storage device of claim 1 , wherein the parity check matrix is shortened by discarding a number of columns that is equal to a length of the codeword plus m.
6. The data storage device of claim 1 , wherein the first length is equal to 2 m1 −1.
7. The data storage device of claim 6 , wherein the second length is equal to 2 m2 −1.
8. The data storage device of claim 7 , wherein m1 and m2 are different.
9. The data storage device of claim 8 , wherein a greatest common divisor for m1 and m2 is 1.
10. A data storage device, comprising:
a memory device; and
a controller coupled to the memory device, the controller configured to:
retrieve a codeword from the memory device;
generate two constituent codes of unequal length from the codeword of a first length;
rotate at least one constituent code of the two constituent codes until either an error within the at least one constituent code is present in a parity portion or a number of rotations has occurred, wherein the number of rotations corresponds to a number of parity bits of the parity check matrix divided by a number of bits of data of the at least one constituent code;
determine a location of the error;
upon determining the location of the error, flip a bit corresponding to the location; and
decode the codeword.
11. The data storage device of claim 10 , wherein a greatest common divisor of:
a length of a first constituent code of the two constituent codes; and
a length of a second constituent code of the two constituent codes is equal to 1.
12. The data storage device of claim 10 , wherein at least one constituent code is a SECDED constituent code.
13. The data storage device of claim 10 , wherein the two constituent codes each have a length that is less than the first length.
14. The data storage device of claim 10 , wherein the controller is further configured to generate a parity matrix for a first constituent code of the at least one constituent code.
15. The data storage device of claim 14 , wherein the parity matrix has a number of rows that is equal to a number of parity bits for the first constituent code.
16. The data storage device of claim 15 , wherein the parity matrix has a number of columns that is equal to a length of the first constituent code.
17. The data storage device of claim 10 , wherein a number of parity bits for each constituent code is equal.
18. A data storage device, comprising:
a memory device;
means to retrieve codewords from the memory device;
means to generate a cyclic code with the codewords of an odd integer weight using Chinese Remainder Theorem (CRT), wherein the means to generate are coupled to the memory device;
means to determine a location of an error in the cyclic code; and
upon determining the location of the error, means to flip a bit corresponding to the location.
19. The data storage device of claim 18 , further comprising means to create a SECDED constituent code from the codewords of the odd integer weight.
20. The data storage device of claim 19 , wherein the cyclic code includes the SECDED constituent code and a second constituent code.