Low density parity check decoder with miscorrection handling
View Patent ↗A data processing system includes a decoder circuit, syndrome calculation circuit and hash calculation circuit. The decoder circuit is operable to apply a decoding algorithm to a decoder input based on a first portion of a composite matrix to yield a codeword. The syndrome calculation circuit is operable to calculate a syndrome based on the codeword and on the first portion of the composite matrix. The hash calculation circuit is operable to calculate a hash based on a second portion of the composite matrix. The decoder circuit is also operable to correct the codeword on the hash when the syndrome indicates that the codeword based on the first portion of the composite matrix is correct but a second test indicates that the codeword is miscorrected.
1. A data processing system comprising:
a decoder circuit operable to apply a decoding algorithm to a decoder input based on a first portion of a composite matrix to yield a codeword;
a syndrome calculation circuit operable to calculate a syndrome based on the codeword and on the first portion of the composite matrix; and
a hash calculation circuit operable to calculate a hash based on a second portion of the composite matrix, wherein the decoder circuit is operable to correct the codeword based at least in part on the hash when the syndrome indicates that the codeword based on the first portion of the composite matrix is correct but a second test indicates that the codeword is miscorrected.
2. The data processing system of claim 1 , wherein the decoder circuit comprises a low density parity check decoder and the composite matrix comprises a parity check matrix.
3. The data processing system of claim 1 , further comprising a miscorrection handling circuit operable to cause the decoder circuit to correct the codeword by reapplying the decoding algorithm to the decoder input based on the entire composite matrix.
4. The data processing system of claim 1 , wherein the second test comprises comparing the hash with an expected value.
5. The data processing system of claim 1 , wherein the second test comprises a cyclic redundancy check comparing cyclic redundancy check bits calculated based on the codeword with source cyclic redundancy check bits in the decoder input.
6. The data processing system of claim 1 , further comprising a miscorrection handling circuit operable to correct the codeword with the decoder circuit by searching for a sub-codeword using the hash and combining the sub-codeword with the codeword.
7. The data processing system of claim 6 , wherein the miscorrection handling circuit is operable to search for the sub-codeword in a lookup table of sub-codeword and hash value pairs using the hash.
8. The data processing system of claim 6 , wherein the miscorrection handling circuit is operable to determine whether combining the sub-codeword with the codeword corrects the miscorrected codeword by comparing a resulting codeword from combining the sub-codeword with the codeword with an expected value.
9. The data processing system of claim 6 , wherein the miscorrection handling circuit is operable to determine whether combining the sub-codeword with the codeword corrects the miscorrected codeword using a cyclic redundancy check.
10. The data processing system of claim 1 , further comprising a low density parity check encoder circuit operable to encode input data based on a parity generator matrix corresponding to the composite matrix.
11. The data processing system of claim 10 , further comprising a pattern constraint encoder operable to encode the input data to preclude unwanted data patterns, wherein the decoder input is derived from an output of the low density parity check encoder, wherein the low density parity check encoder circuit is operable to generate parity bits corresponding to the second portion of the composite matrix, and wherein the parity bits are provided to the decoder circuit without passing through the pattern constraint encoder.
12. The data processing system of claim 1 , wherein parity bits in the decoder input corresponding to the second portion of the composite matrix satisfy a linearity property.
13. The data processing system of claim 1 , wherein the data processing system is implemented as part of a device selected from a group consisting of a storage device and a receiving device.
14. The data processing system of claim 1 , wherein the data processing system is implemented as an integrated circuit.
15. A method of decoding data, comprising:
applying a decoding algorithm in a decoder circuit to the data based on a first portion of a composite matrix to yield a codeword;
multiplying the codeword and the first portion of the composite matrix in a syndrome calculation circuit to yield a syndrome;
applying the decoding algorithm in the decoder circuit to the data based on a second portion of the composite matrix to yield a second codeword;
multiplying the second codeword and the second portion of the composite matrix in a hash calculation circuit to yield a hash; and
correcting the codeword based at least in part on the hash when the syndrome indicates that the codeword is correct but a second test indicates that the codeword is miscorrected.
16. The method of claim 15 , wherein the codeword is corrected by reapplying the decoding algorithm to the data based on the entire composite matrix when the syndrome indicates that the codeword is correct but a second test indicates that the codeword is miscorrected.
17. The method of claim 15 , wherein the codeword is corrected by searching for a sub-codeword in a lookup table of sub-codeword and hash value pairs using the hash and combining the sub-codeword with the codeword in an exclusive OR operation.
18. The method of claim 17 , further comprising testing the corrected codeword with a cyclic redundancy check.
19. The method of claim 15 , wherein the second test comprises comparing the hash with an expected value.
20. A storage system comprising:
a storage medium;
a head assembly disposed in relation to the storage medium and operable to provide a sensed signal corresponding to information on the storage medium;
a data processing system comprising:
an analog to digital converter circuit operable to sample an analog signal derived from the sensed signal to yield a series of digital samples;
an equalizer circuit operable to equalize the digital samples to yield a data set;
a data detector circuit operable to apply a data detection algorithm to the data set to yield a detected output; and
a data decoding circuit including:
a decoder operable to apply a decoding algorithm to the detected output based on a first portion of a composite matrix to yield a codeword;
a syndrome calculation circuit operable to calculate a syndrome based on the codeword and on the first portion of the composite matrix; and
a hash calculation circuit operable to calculate a hash based on a second portion of the composite matrix, wherein the decoder is operable to correct the codeword based at least in part on the hash when the syndrome indicates that the codeword based on the first portion of the composite matrix is correct but a second test indicates that the codeword is miscorrected.