Binary BCH decoders

• US 8,132,081 B1
• Filed: 02/21/2008
• Issued: 03/06/2012
• Est. Priority Date: 02/21/2008
• Status: Active Grant

• Current Assignee: SK Hynix Memory Solutions Incorporated (SK Hynix Inc.)
• Original Assignee: Link_A_Media Devices Corporation (SK Hynix Inc.)
• Inventors: Wu, Yingquan
• Primary Examiner(s): Baderman, Scott
• Assistant Examiner(s): PATEL, JIGAR P
• Application Number:
  US12/070,892
• Time in Patent Office: 1,475 Days
• Field of Search: 714/782
• US Class Current: 714/782
• 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/6561 Parallelized implementations

Abstract

Binary Bose-Chaudhuri-Hocquenghem (BCH) encoded data is processed by obtaining a set of syndromes associated with the binary BCH encoded data, including a subset of odd-term syndromes and a subset of even-term syndromes. During initialization of a variant error-locator polynomial, {circumflex over (Ω)}(x), the subset of even-term syndromes, but not the subset of odd-term syndromes, are loaded into the variant error-locator polynomial, {circumflex over (Ω)}⁽⁰⁾(x).

Claims

1. A method for processing binary Bose-Chaudhuri-Hocquenghem (BCH) encoded data, comprising:

obtaining a set of syndromes associated with the binary BCH encoded data, including a subset of odd-term syndromes and a subset of even-term syndromes; and

during initialization of a variant error-locator polynomial, {circumflex over (Ω

)}(x), loading the subset of even-term syndromes, but not the subset of odd-term syndromes, into a processor which is configured to store the variant error-locator polynomial, {circumflex over (Ω

)}⁽⁰⁾(x), wherein there is a 2<sup>−

(f+1)m</sup> probability that a proper result will not be generated, where m is a finite field dimension and f is a design parameter.

2. The method of claim 1, wherein loading further comprises loading zero values in place of the subset of odd-term syndromes.

3. The method of claim 1, wherein the process is performed during an iterative discrepancy calculation which outputs discrepancy values, Δ

.

4. The method of claim 1, wherein the process is performed during a parallel inversionless Berlekamp process which outputs an error locator polynomial, Λ

.

5. The method of claim 1 further comprising using an odd-term error-locator update module which is not left shifted.

6. The method of claim 1 further comprising determining the design parameter, f, based at least in part on a desired probability.

7. A system for processing binary Bose-Chaudhuri-Hocquenghem (BCH) encoded data, comprising:

an interface configured to obtain a set of syndromes associated with the binary BCH encoded data, including a subset of odd-term syndromes and a subset of even-term syndromes;

an initialization module configured during initialization of a variant error-locator polynomial, {circumflex over (Ω

)}(x), to load the subset of even-term syndromes, but not the subset of odd-term syndromes, into the variant error-locator polynomial, {circumflex over (Ω

)}⁽⁰⁾(x); and

an odd-term error-locator update module which is not left shifted, wherein the system includes at least t+1 systolic units of a first type and at least

8. The system of claim 7, wherein the initialization module is further configured to load zero values in place of the subset of odd-term syndromes.

9. The system of claim 7, wherein the system is included in an iterative discrepancy calculation system which outputs discrepancy values, Δ

.

10. The system of claim 7, wherein the system is included in a parallel inversionless Berlekamp system which outputs an error locator polynomial, Λ

.

11. The system of claim 7, wherein the system includes at least 2t+1 systolic units, where t is an error correction capability.

12. A system for processing binary Bose-Chaudhuri-Hocquenghem (BCH) encoded data, comprising:

an interface configured to obtain a set of syndromes associated with the binary BCH encoded data, including a subset of odd-term syndromes and a subset of even-term syndromes; and

an initialization module configured during initialization of a variant error-locator polynomial, {circumflex over (Ω

)}(x), to load the subset of even-term syndromes, but not the subset of odd-term syndromes, into the variant error-locator polynomial, {circumflex over (Ω

)}⁽⁰⁾(x), wherein there is a 2<sup>−

(f+1)m</sup> probability that a proper result will not be generated, where m is a finite field dimension and f is a design parameter.

13. The system of claim 12, wherein the design parameter, f, of the system is determined based at least in part on a desired probability.

14. The system of claim 12, wherein the system includes t+f systolic units, where t is an error correction capability.

15. The system of claim 12, wherein the initialization module is further configured to load zero values in place of the subset of odd-term syndromes.

16. The system of claim 12, wherein the system is included in an iterative discrepancy calculation system which outputs discrepancy values, Δ

.

17. The system of claim 12, wherein the system is included in a parallel inversionless Berlekamp system which outputs an error locator polynomial, Ε

.

18. The system of claim 12, wherein the system includes at least 2t+1 systolic units, where t is an error correction capability.

19. A computer program product for processing binary Bose-Chaudhuri-Hocquenghem (BCH) encoded data, the computer program product being embodied in a computer readable storage medium and comprising computer instructions for:

obtaining a set of syndromes associated with the binary BCH encoded data, including a subset of odd-term syndromes and a subset of even-term syndromes; and

during initialization of a variant error-locator polynomial, {circumflex over (Ω

)}(x) , loading the subset of even-term syndromes, but not the subset of odd-term syndromes, into the variant error-locator polynomial, {circumflex over (Ω

)}⁽⁰⁾(x) wherein there is a 2<sup>−

(f+1)m</sup> probability that a proper result will not be generated, where m is a finite field dimension and f is a design parameter.