Error locator polynomial decoder and method

• US 10,461,777 B2
• Filed: 12/08/2016
• Issued: 10/29/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, Gunnam, Kiran Kumar
• Primary Examiner(s): Chung, Phung M
• Application Number:
  US15/373,313
• Publication Number:
  US 20170093433A1
• Time in Patent Office: 1,055 Days
• 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/159 Remainder calculation, e.g. for encoding and syndrome calculation

Abstract

An apparatus includes a convergence detector circuit coupled to an error locator polynomial generator circuit. The convergence detector circuit includes at least two computation circuits configured to generate at least two convergence signals based on a mutual error locator polynomial from the error locator polynomial generator circuit and on at least two different sets of syndromes. Each of the different sets of syndromes corresponds to a different one of the convergence signals.

Claims

1. A decoding apparatus comprising:

a syndrome generator circuit configured to receive data and generate at least two different sets of syndromes;

an error locator polynomial generator circuit configured to receive the at least two different sets of syndromes and generate a mutual error locator polynomial; and

a convergence detector circuit coupled to the error locator polynomial generator circuit, the convergence detector circuit including;

at least two computation circuits configured to generate at least two convergence signals based on the mutual error locator polynomial from the error locator polynomial generator circuit and on the at least two different sets of syndromes, wherein each of the different sets of syndromes corresponds to a different one of the convergence signals.

2. The apparatus of claim 1, the convergence detector circuit further including a comparator coupled to the at least two computation circuits, the comparator configured to generate a non-convergence signal indicating non-convergence from at least one of the at least two computation circuits.

3. The apparatus of claim 2, the error locator polynomial generator circuit and the convergence detector circuit included in an error correction coding (ECC) decoder that is configured to decode data according to an ECC scheme, wherein a number of the at least two computation circuits included in the convergence detector circuit substantially matches a largest number of errors that are correctable by the ECC scheme, and wherein the convergence detector circuit is configured to generate a convergence indicator in response to receiving a convergence signal indicating convergence from all of the at least two computation circuits.

4. The apparatus of claim 3, the convergence detector circuit configured to complete a convergence detection operation in a single clock cycle.

5. The apparatus of claim 2, the error locator polynomial generator circuit and the convergence detector circuit included in an error correction coding (ECC) decoder that is configured to decode data according to an ECC scheme, wherein a number of the at least two computation circuits included in the convergence detector circuit is less than a largest number of errors that are correctable by the ECC scheme.

6. The apparatus of claim 5, the convergence detector circuit configured to complete a convergence detection operation over multiple clock cycles.

7. The apparatus of claim 1, the error locator polynomial generator circuit configured to generate the mutual error locator polynomial according to a Berlekamp-Massey technique.

8. The apparatus of claim 1, the error locator polynomial generator circuit configured to generate the mutual error locator polynomial according to a modified Berlekamp-Massey technique that includes adjusting the mutual error locator polynomial based on an error parity of received data.

9. The apparatus of claim 1, wherein the at least two computation circuits includes:

a first computation circuit configured to generate a first convergence signal of the at least two convergence signals based on the mutual error locator polynomial and on a first set of syndromes; and

a second computation circuit in parallel with the first computation circuit and configured to generate a second convergence signal of the at least two convergence signals based on the mutual error locator polynomial and on a second set of syndromes that is different from the first set of syndromes.

10. The apparatus of claim 9, wherein the first computation circuit comprises:

a plurality of multipliers, each of the plurality of multipliers configured to multiply a syndrome value with a coefficient of the mutual error locator polynomial; and

an adder having inputs coupled to outputs of the plurality of multipliers.

11. A decoding apparatus comprising:

means for generating first and second sets of syndromes;

means for generating an error locator polynomial;

means for generating a first convergence signal based on the error locator polynomial and corresponding to the first set of syndromes;

means for generating, concurrently with generation of the first convergence signal, a second convergence signal based on the error locator polynomial and corresponding to the second set of syndromes; and

means for generating a non-convergence indicator in response to at least one of the first convergence signal and the second convergence signal indicating non-convergence, and generating a convergence indicator in response to all received convergence signals indicating convergence.

12. The apparatus of claim 11, further comprising means for generating a non-convergence indicator in response to at least one of the first convergence signal and the second convergence signal indicating non-convergence, and generating a convergence indicator in response to all received convergence signals indicating convergence.

13. The apparatus of claim 11, the means for generating the error locator polynomial configured to generate the error locator polynomial according to a modified Berlekamp-Massey technique that includes adjusting the error locator polynomial based on an error parity of received data.

14. A decoding apparatus comprising:

a syndrome generator circuit for receiving data and generating sets of syndromes;

an error locator polynomial generator circuit; and

a convergence detector circuit coupled to the error locator polynomial generator circuit, the convergence detector circuit including;

at least three computation circuits configured to generate at least three convergence signals based on a mutual error locator polynomial from the error locator polynomial generator circuit and on at least three different sets of syndromes, wherein each of the different sets of syndromes corresponds to a different one of the convergence signals.

15. The apparatus of claim 14, wherein the at least three computation circuits includes:

a first computation circuit configured to generate a first convergence signal of the at least three convergence signals based on the mutual error locator polynomial and on a first set of syndromes;

a second computation circuit in parallel with the first computation circuit and configured to generate a second convergence signal of the at least three convergence signals based on the mutual error locator polynomial and on a second set of syndromes that is different from the first set of syndromes; and

a third computation circuit in parallel with the first computation circuit and the second computation circuit, and configured to generate a third convergence signal of the at least three convergence signals based on the mutual error locator polynomial and on a third set of syndromes that is different from the first set of syndromes and the second set of syndromes.

16. The apparatus of claim 15, wherein the first computation circuit comprises:

a plurality of multipliers, each of the plurality of multipliers configured to multiply a syndrome value with a coefficient of the mutual error locator polynomial; and

an adder having inputs coupled to outputs of the plurality of multipliers.

17. The Apparatus of claim 15, wherein the convergence detector circuit includes a comparator coupled to the at least three computation circuits, the comparator configured to generate a non-convergence indicator in response to receiving a convergence signal indicating non-convergence from at least one of the at least three computation circuits.

18. The apparatus of claim 17, the error locator polynomial generator circuit and the convergence detector circuit included in an error correction coding (ECC) decoder that is configured to decode data according to an ECC scheme, wherein a number of the at least three computation circuits included in the convergence detector circuit substantially matches a largest number of errors that are correctable by the ECC scheme, and wherein the convergence detector circuit is configured to generate a convergence indicator in response to receiving a convergence signal indicating convergence from all of the at least three computation circuits.

19. The apparatus of claim 18, wherein the convergence detector circuit is configured to complete a convergence detection operation in a single clock cycle.

20. The Apparatus of claim 14, wherein the convergence detector circuit includes a comparator coupled to the at least three computation circuits, the comparator configured to generate a non-convergence indicator in response to receiving a convergence signal indicating non-convergence from at least one of the at least three computation circuits.