Error locator polynomial decoder and method

• US 10,439,644 B2
• Filed: 11/22/2017
• Issued: 10/08/2019
• Est. Priority Date: 07/14/2015
• Status: Active Grant

• Current Assignee: JP Morgan Chase Bank, N.A. (JP Morgan Chase & Co)
• Original Assignee: Western Digital Technologies Incorporated (Western Digital Corporation)
• Inventors: Ilani, Ishai
• Primary Examiner(s): Chung, Phung M
• Application Number:
  US15/821,382
• Publication Number:
  US 20180097528A1
• Time in Patent Office: 685 Days
• CPC Class Codes: G11C 29/52 Protection of memory contents; Detection of errors in memory contents
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/152 Bose-Chaudhuri-Hocquenghem [BCH] codes
• CPC Class Codes: H03M 13/153 using the Berlekamp-Massey algorithm
• CPC Class Codes: H03M 13/1545 Determination of error locations, e.g. Chien search or other methods or arrangements for the determination of the roots of the error locator polynomial
• CPC Class Codes: H03M 13/157 Polynomial evaluation, i.e. determination of a polynomial sum at a given value
• CPC Class Codes: H03M 13/3746 with iterative decoding

Abstract

A decoder configured to decode a representation of the codeword includes an error locator polynomial generator circuit. The error locator polynomial circuit is configured to generate an error locator polynomial based on a decode operation that includes iteratively adjusting values of a first polynomial, a second polynomial, a third polynomial, and a fourth polynomial. The error locator polynomial circuit is also configured to initialize the third polynomial based on even-indexed coefficients of a syndrome polynomial and initialize the fourth polynomial based on odd-indexed coefficients of the syndrome polynomial.

Claims

1. An apparatus comprising:

an interface configured to receive a representation of a codeword; and

a decoder coupled to the interface and configured to decode the representation of the codeword, the decoder comprising an error locator polynomial generator circuit configured to;

generate an error locator polynomial based on a decode operation that includes iteratively adjusting values of a first polynomial, a second polynomial, a third polynomial, and a fourth polynomial; and

initialize the third polynomial based on even-indexed coefficients of a syndrome polynomial and initialize the fourth polynomial based on odd-indexed coefficients of the syndrome polynomial.

2. The apparatus of claim 1, wherein the error locator polynomial generator circuit includes:

a first set of storage elements to store first coefficients of the first polynomial;

a second set of storage elements to store second coefficients of the second polynomial;

a third set of storage elements to store third coefficients of the third polynomial; and

a fourth set of storage elements to store fourth coefficients of the fourth polynomial.

3. The apparatus of claim 2, wherein the syndrome polynomial includes a first number of terms, and wherein each of the first set of storage elements, the second set of storage elements, the third set of storage elements, and the fourth set of storage elements is configured to store a second number of terms, the second number substantially half of the first number.

4. The apparatus of claim 2, further comprising a polynomial initializer configured to:

copy the even-indexed coefficients of the syndrome polynomial into the third set of storage elements; and

copy the odd-indexed coefficients of the syndrome polynomial into the fourth set of storage elements.

5. The apparatus of claim 1, wherein the error locator polynomial generator circuit is further configured to determine the error locator polynomial in accordance with a Berlekamp-Massey (BM) technique.

6. The apparatus of claim 1, further comprising a syndrome generator circuit of the decoder, the syndrome generator circuit coupled to an input of the error locator polynomial generator circuit and configured to determine the syndrome polynomial based on the representation of the codeword.

7. The apparatus of claim 1, further comprising an error corrector circuit of the decoder, the error corrector circuit coupled to an output of the error locator polynomial generator circuit and configured to identify one or more error locations of the representation of the codeword based on the error locator polynomial.

8. The apparatus of claim 1, further comprising:

a controller that includes the interface and the decoder; and

a non-volatile memory coupled to the controller.

9. A method comprising:

receiving, with an error locator polynomial generator circuit, a syndrome polynomial corresponding to a representation of data;

initializing, with the error locator polynomial generator circuit, a first polynomial, a second polynomial, a third polynomial, and a fourth polynomial, wherein the third polynomial is initialized based on even-indexed coefficients of the syndrome polynomial and the fourth polynomial is initialized based on odd-indexed coefficients of the syndrome polynomial;

performing, with the error locator polynomial generator circuit, an iterative decoding operation to generate an error locator polynomial based on iteratively adjusting values of the first polynomial, the second polynomial, the third polynomial, and the fourth polynomial; and

outputting, with the error locator polynomial generator circuit, the error locator polynomial to an error corrector circuit.

10. The method of claim 9, wherein:

initializing the first polynomial includes copying a first value into a first set of storage elements;

initializing the second polynomial includes copying a second value into a second set of storage elements;

initializing the third polynomial includes copying the even-indexed coefficients of the syndrome polynomial into a third set of storage elements; and

initializing the fourth polynomial includes copying the odd-indexed coefficients of the syndrome polynomial into a fourth set of storage elements.

11. The method of claim 10, wherein the syndrome polynomial includes a first number of terms, and wherein each of the first set of storage elements, the second set of storage elements, the third set of storage elements, and the fourth set of storage elements is configured to store a second number of terms, the second number substantially half of the first number.

12. The method of claim 9, wherein the error locator polynomial is determined in accordance with an iterative Berlekamp-Massey (BM) technique.

13. The method of claim 9, further comprising determining the syndrome polynomial.

14. The method of claim 9, further comprising identifying one or more error locations of the representation of the data based on the error locator polynomial.

15. The method of claim 14, wherein the one or more error locations are identified using a Chien search technique.

16. An apparatus comprising:

means for generating a syndrome polynomial corresponding to a representation of a codeword, the syndrome polynomial having a first number of coefficients;

means for generating an error locator polynomial based on a decoding operation that includes iteratively adjusting values of a first polynomial, a second polynomial, a third polynomial, and a fourth polynomial, each of the first polynomial, the second polynomial, the third polynomial, and the fourth polynomial having a second number of coefficients, the second number substantially half of the first number; and

means for initializing the third polynomial based on even-indexed coefficients of the syndrome polynomial and for initializing the fourth polynomial based on odd-indexed coefficients of the syndrome polynomial.

17. The apparatus of claim 16, further comprising:

means for storing first coefficients of the first polynomial;

means for storing second coefficients of the second polynomial;

means for storing third coefficients of the third polynomial; and

means for storing fourth coefficients of the fourth polynomial.

18. The apparatus of claim 16, wherein the means for generating the error locator polynomial is further configured to determine the error locator polynomial in accordance with a Berlekamp-Massey (BM) technique.

19. The apparatus of claim 16, further comprising means for identifying one or more error locations of the representation of the codeword based on the error locator polynomial.