Techniques for reducing latency in the detection of uncorrectable codewords
Devices, systems, and methods that reduce the latency of detecting that a codeword is uncorrectable are disclosed and described. Such devices, systems, and methods allow the determination that a codeword is uncorrectable prior to determining error locations in the codeword, thus eliminating the need for such an error location search.
1. An error correction device, comprising:
a memory controller configured to:
receive a codeword from a memory device, wherein the codeword is configured to correct a predetermined number (t) of errors or less;
generate an error locator polynomial from the codeword;
determine if the codeword includes more than the predetermined number of errors (t+1 or greater) from the error locator polynomial; and
output an indication of an uncorrectable codeword when the error locator polynomial indicates that the codeword includes more than the predetermined number of errors without determining error locations.
2. The device of claim 1 , wherein, when the error locator polynomial indicates that the codeword includes the predetermined number of errors or less, the memory controller is further configured to:
determine one or more locations of errors in the codeword from the error locator polynomial; and
correct one or more errors in the codeword at the one or more determined error locations.
3. The device of claim 2 , wherein, to determine the one or more locations of errors in the codeword from the error locator polynomial, the memory controller is further configured to determine roots of the error locator polynomial using a Chien Search.
4. The device of claim 1 , wherein, to generate the error locator polynomial from the codeword, the memory controller is further configured to:
calculate a syndrome for the codeword, wherein the codeword is a Bose-Chaudhure-Hocquenghem codeword; and
generate the error locator polynomial by applying a Berlekamp-Massey Algorithm (BMA) to the syndrome.
5. The device of claim 4 , wherein, in determining if the codeword includes more than the predetermined number of errors (t+1 or greater), the memory controller is further configured to:
determine a degree of the error locator polynomial; and
determine that the codeword includes more than the predetermined number of errors (t+1 or greater) when the degree of the error locator polynomial is greater than the predetermined number of errors.
6. The device of claim 1 , wherein, to generate the error locator polynomial from the codeword, the memory controller is further configured to:
receive, along with the codeword from the memory device, a plurality (2*t+1) of parity symbols for correcting the predetermined number (t) of errors or less;
calculate a plurality (2*t+1) of partial syndromes for the codeword; and
generate the locator polynomial from the plurality (2*t+1) of partial syndromes over multiple iterations.
7. The device of claim 6 , wherein, to determine if the codeword includes more than the predetermined number of errors (t+1 or greater), the memory controller is further configured to:
determine if a final discrepancy for the error locator polynomial is a zero or non-zero value; and
output the indication of an uncorrectable codeword when the final discrepancy for the error locator polynomial is a non-zero value without determining error locations, wherein the codeword is a Reed-Solomon codeword.
8. The device of claim 6 , wherein, to generate the error locator polynomial from the plurality (2*t+1) of partial syndromes, the memory controller is further configured to generate the error locator polynomial using a Berlekamp-Massey Algorithm (BMA) on the plurality (2*t+1) of partial syndromes; and
to determine if a final discrepancy for the error locator polynomial is a zero or non-zero value, the memory controller is further configured to determine if a result of a last iteration of the BMA on the plurality (2*t+1) of partial syndromes is zero or non-zero.
9. A computing system, comprising:
a host processor;
a memory device;
a memory controller communicatively coupled to the host processor and the memory device, the memory controller configured to:
receive a codeword from the memory device in response to a read request from the host processor, wherein the codeword is configured to correct a predetermined number (t) of errors or less;
generate an error locator polynomial from the codeword;
determine if the codeword includes more than the predetermined number of errors (t+1 or greater) from the error locator polynomial; and
output an indication of an uncorrectable codeword when the error locator polynomial indicates that the codeword includes more than the predetermined number of errors without determining error locations.
10. The system of claim 9 , wherein, when the error locator polynomial indicates that the codeword includes the predetermined number of errors or less, the memory controller is further configured to:
determine one or more locations of errors in the codeword from the error locator polynomial; and
correct one or more errors in the codeword at the one or more determined error locations.
11. The system of claim 10 , wherein, to determine the one or more locations of errors in the codeword from the error locator polynomial, the memory controller is further configured to determine roots of the error locator polynomial using a Chien Search.
12. The system of claim 9 , wherein, to generate the error locator polynomial from the codeword, the memory controller is further configured to:
calculate a syndrome for the codeword, wherein the codeword is a Bose-Chaudhure-Hocquenghem codeword; and
generate the error locator polynomial from the syndrome by applying a Berlekamp-Massey Algorithm (BMA) to the syndrome.
13. The system of claim 12 , wherein, in determining if the codeword includes more than the predetermined number of errors (t+1 or greater), the memory controller is further configured to:
determine a degree of the error locator polynomial; and
determine that the codeword includes more than the predetermined number of errors (t+1 or greater) when the degree of the error locator polynomial is greater than the predetermined number of errors.
14. The system of claim 9 , wherein, to generate the error locator polynomial from the codeword, the memory controller is further configured to:
receive, along with the codeword from the memory device, a plurality (2*t+1) of parity symbols for correcting the predetermined number (t) of errors or less;
calculate a plurality (2*t+1) of partial syndromes for the codeword; and
generate the locator polynomial from the plurality (2*t+1) of partial syndromes over multiple iterations.
15. The system of claim 14 , wherein, to determine if the codeword includes more than the predetermined number of errors (t+1 or greater), the memory controller is further configured to:
determine if a final discrepancy for the error locator polynomial is a zero or non-zero value; and
output the indication of an uncorrectable codeword when the final discrepancy for the error locator polynomial is a non-zero value, without determining error locations, wherein the codeword is a Reed-Solomon codeword.
16. The system of claim 14 , wherein, to generate the error locator polynomial from the plurality (2*t+1) of partial syndromes, the memory controller is further configured to generate the error locator polynomial using a Berlekamp-Massey Algorithm (BMA) on the plurality (2*t+1) of partial syndromes; and
to determine if a final discrepancy for the error locator polynomial is a zero or non-zero value, the memory controller is further configured to determine if a result of a last iteration of the BMA on the plurality (2*t+1) of partial syndromes is zero or non-zero.
17. A method of reducing detection latency of uncorrectable errors in read data, comprising:
receiving a codeword at a memory controller from a memory device, wherein the codeword is configured to correct a predetermined number (t) of errors or less;
generating, in an error decoder of the memory controller, an error locator polynomial from the codeword;
determining, in the error decoder, if the codeword includes more than the predetermined number of errors (t+1 or greater) from the error locator polynomial;
outputting, from the memory controller, an indication of an uncorrectable codeword when the error locator polynomial indicates that the codeword includes more than the predetermined number of errors without determining error locations; and
receiving a subsequent copy of the codeword at the memory controller from the memory device in response to the indication of an uncorrectable codeword.
18. The method of claim 17 , wherein, when the error locator polynomial indicates that the codeword includes the predetermined number of errors or less, the method further comprises:
determining one or more locations of errors in the codeword from the error locator polynomial; and
correcting one or more errors in the codeword at the one or more determined error locations.
19. The method of claim 18 , wherein, in determining the one or more locations of errors in the codeword from the error locator polynomial, the method further comprises determining roots of the error locator polynomial using a Chien Search.
20. The method of claim 17 , wherein, to generate the error locator polynomial from the codeword, the method further comprises:
calculating a syndrome for the codeword, wherein the codeword is a Bose-Chaudhure-Hocquenghem codeword; and
generating the error locator polynomial from the syndrome by applying a Berlekamp-Massey Algorithm (BMA) to the syndrome.
21. The method of claim 20 , wherein, in determining if the codeword includes more than the predetermined number of errors (t+1 or greater), the method further comprises:
determining a degree of the error locator polynomial; and
determining that the codeword includes more than the predetermined number of errors (t+1 or greater) when the degree of the error locator polynomial is greater than the predetermined number of errors.
22. The method of claim 17 , wherein, to generate the error locator polynomial from the codeword, the method further comprises:
receiving, along with the codeword from the memory device, a plurality (2*t+1) of parity symbols for correcting the predetermined number (t) of errors or less;
calculating a plurality (2*t+1) of partial syndromes for the codeword; and
generating the locator polynomial from the plurality (2*t+1) of partial syndromes over multiple iterations.
23. The method of claim 22 , wherein, to determine if the codeword includes more than the predetermined number of errors (t+1 or greater), the method further comprises:
determining if a final discrepancy for the error locator polynomial is a zero or non-zero value; and
outputting, from the memory controller, the indication of an uncorrectable codeword when the final discrepancy for the error locator polynomial is a non-zero value, without determining error locations, wherein the codeword comprises a Reed-Solomon codeword.
24. The method of claim 22 , wherein, to generate the error locator polynomial from the plurality (2*t+1) of partial syndromes, the method further comprises generating the error locator polynomial using a Berlekamp-Massey Algorithm (BMA) on the plurality (2*t+1) of partial syndromes; and
to determine if a final discrepancy for the error locator polynomial is a zero or non-zero value, the method further comprises determining if a result of a last iteration of the BMA on the plurality (2*t+1) of partial syndromes is zero or non-zero.