Method and decoder to adjust an error locator polynomial based on an error parity

• US 10,572,189 B2
• Filed: 11/04/2016
• Issued: 02/25/2020
• Est. Priority Date: 11/04/2016
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Inventors: Ilani, Ishai
• Primary Examiner(s): Chung, Phung M
• Application Number:
  US15/343,866
• Publication Number:
  US 20180129564A1
• Time in Patent Office: 1,208 Days
• CPC Class Codes: G06F 11/1012 using codes or arrangements adapted for a specific type of error G06F11/1048 takes precedence
• CPC Class Codes: G06F 3/0673 Single storage device
• 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/1525 Determination and particular use of error location polynomials
• CPC Class Codes: H03M 13/153 using the Berlekamp-Massey algorithm
• CPC Class Codes: H03M 13/155 Shortening or extension of codes
• CPC Class Codes: H03M 13/157 Polynomial evaluation, i.e. determination of a polynomial sum at a given value
• CPC Class Codes: H03M 13/1575 Direct decoding, e.g. by a direct determination of the error locator polynomial from syndromes and subsequent analysis or by matrix operations involving syndromes, e.g. for codes with a small minimum Hamming distance
• CPC Class Codes: H03M 13/6502 Reduction of hardware complexity or efficient processing
• CPC Class Codes: H03M 13/6561 Parallelized implementations

Abstract

A method of operation of a decoder includes receiving first data at the decoder. The method further includes generating second data at the decoder based on the first data. The second data is generated by adjusting an error locator polynomial based on an error parity of the first data.

Claims

1. A method of operation of a decoder, the method comprising:

receiving, with the decoder, an error parity of a first data;

receiving, with the decoder, the first data; and

generating, with the decoder, second data by adjusting a length of an error locator polynomial based on the error parity of the first data,

wherein the adjusting the length of the error locator polynomial reduces at least one of decoding latency or power consumption of the decoder.

2. The method of claim 1, wherein the adjusting the length of the error locator polynomial includes increasing the length of the error locator polynomial by a value of two.

3. The method of claim 2, wherein the length of the error locator polynomial is increased in a single iteration of a decoding process to decode the first data.

4. The method of claim 1, further comprising;

generating a syndrome polynomial based on the first data; and

adjusting coefficients of the error locator polynomial based on the syndrome polynomial.

5. The method of claim 1, further comprising identifying a number of logic one values included in the first data, wherein the error parity corresponds to a difference between the number of logic one values and a codeword parity that is associated with each codeword of an encoding scheme used to encode the first data.

6. The method of claim 5, further comprising setting the error parity to a logic zero value in response to determining that the number of logic one values included in the first data is even.

7. The method of claim 5, wherein the adjusting the length of the error locator polynomial includes increasing the length of the error locator polynomial by a value of two if the error parity is equal to a parity of the error locator polynomial.

8. The method of claim 5, further comprising setting the error parity to a logic one value in response to determining that the number of logic one values included in the first data is odd.

9. The method of claim 5, wherein the adjusting the length of the error locator polynomial includes increasing the length of the error locator polynomial by a value of one if the error parity is not equal to a parity of the error locator polynomial.

10. The method of claim 1, further comprising:

generating a syndrome polynomial based on the first data;

determining that the error locator polynomial is correct based on a product of the error locator polynomial and the syndrome polynomial;

determining one or more error locations of the first data based on the error locator polynomial; and

adjusting values of the first data based on the one or more error locations.

11. The method of claim 10, wherein the determining of the one or more error locations includes determining a set of roots of the error locator polynomial.

12. The method of claim 1, wherein the first data is encoded in accordance with a Bose-Chaudhuri-Hocquenghem (BCH) code.

13. The method of claim 12, wherein each codeword included in a codebook of the BCH code including an even number of logic one values.

14. The method of claim 1, wherein generating the second data includes decoding the first data in accordance with an improved Berlekamp-Massey (BM) technique that is capable of performing two iterations of a decoding process in parallel.

15. The method of claim 1, wherein generating the second data includes decoding the first data in accordance with an improved Peterson-Gorenstein-Zierler (PGZ) technique that is capable of performing two iterations of a decoding process in parallel.

16. An apparatus comprising:

a circuit configured to determine an error parity of first data; and

a decoder coupled to the circuit, the decoder configured to generate second data by adjusting a length of an error locator polynomial of the decoder based on the error parity of the first data,

wherein the adjusting the length of the error locator polynomial reduces at least one of decoding latency or power consumption of the decoder.

17. The apparatus of claim 16, further comprising an encoder configured to generate a set of codewords, each having an even number of logic one values.

18. The apparatus of claim 17, wherein the encoder is further configured to encode the first data using a generator polynomial having a factor selected to cause each codeword of the set of codewords to have the even number of logic one values.

19. The apparatus of claim 16, wherein the circuit is further configured to determine the error parity based on whether the first data indicates an even number of logic one values or an odd number of logic one values.

20. The apparatus of claim 16, wherein the decoder is further configured to receive an indication of the error parity from the circuit.

21. The apparatus of claim 16, further comprising:

a controller that includes the circuit and the decoder; and

a memory coupled to the controller.

22. An apparatus comprising:

a first circuit configured to receive first data and to perform a set of decoding operations based on the first data by adjusting a length of a first error locator polynomial based on an even error parity of the first data;

a second circuit configured to receive the first data and to perform the set of decoding operations by adjusting a length of a second error locator polynomial based on an odd error parity of the first data; and

a third circuit coupled to the first circuit and to the second circuit, the third circuit configured to select an output of the first circuit or the second circuit to provide a second data,

wherein adjusting the length of the first error locator polynomial reduces at least one of decoding latency or power consumption of the first circuit, and

wherein adjusting the length of the second error locator polynomial reduces at least one of decoding latency or power consumption of the second circuit.

23. The apparatus of claim 22, wherein the first circuit and the second circuit are configured to perform two iterations of a Berlekamp-Massey (BM) decoding process in parallel.

24. The apparatus of claim 22, wherein the first data includes a set of symbols encoded in accordance with a Reed-Solomon (RS) code or a Bose-Chaudhuri-Hocquenghem (BCH) code.

25. The apparatus of claim 24, wherein the third circuit is further configured to select the output of the first circuit or the second circuit in response to detecting that the output satisfies convergence criteria associated with the RS code.

26. The apparatus of claim 22, wherein the set of decoding operations is performed in accordance with a Berlekamp-Massey (BM) technique.