Binary BCH decoders

• US 8,335,974 B2
• Filed: 01/27/2012
• Issued: 12/18/2012
• Est. Priority Date: 02/21/2008
• Status: Active Grant

• Current Assignee: Link_A_Media Devices Corporation (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:
  US13/359,912
• Publication Number:
  US 20120131423A1
• Time in Patent Office: 326 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 subset of even-term syndromes associated with the binary BCH encoded data, wherein a subset of odd-term syndromes is associated with the subset of even-term syndromes;

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

)}(x), using a processor to load the subset of even-term syndromes into the variant error-locator polynomial at a 0^th iteration of a decoding process, {circumflex over (Ω

)}⁽⁰⁾(x), wherein an error locator polynomial at an r^th iteration of the decoding process, Λ

^(r)(x), a syndrome polynomial, S(x), an error evaluator polynomial at the r^th iteration of the decoding process, Ω

^(r)(x), and the variant error-locator polynomial at the r^th iteration of the decoding process, {circumflex over (Ω

)}^(r)(x), have the following relationship;

Λ

^(r)(x)S(x)=Ω

^(r)(x) +x^r{circumflex over (Ω

)}^(r)(x); and

excluding the subset of odd-term syndromes from the initialization of the variant error-locator polynomial at the 0^th iteration of the decoding process, {circumflex over (Ω

)}⁽⁰⁾(x).

2. The method of claim 1, wherein loading further comprises using 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. A system for processing binary Bose-Chaudhuri-Hocquenghem (BCH) encoded data, comprising:

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

an initialization module configured to;

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

)}(x), to load the subset of even-term syndromes into the variant error-locator polynomial at a 0^th iteration of a decoding process, {circumflex over (Ω

)}⁽⁰⁾(x), wherein an error locator polynomial at an r^th iteration of the decoding process, Λ

^(r)(x), a syndrome polynomial, S(x), an error evaluator polynomial at the r^th iteration of the decoding process, Ω

^(r)(x), and the variant error-locator polynomial at the r^th iteration of the decoding process, {circumflex over (Ω

)}^(r)(x), have the following relationship;

Λ

^(r)(x)S(x)=Ω

^(r)(x) +x^r{circumflex over (Ω

)}^(r)(x); and

exclude the subset of odd-term syndromes from the initialization of the variant error-locator polynomial at the 0^th iteration of the decoding process, {circumflex over (Ω

)}⁽⁰⁾(x).

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

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

.

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

.

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

11. The system of claim 6 further comprising an odd-term error-locator update module which is not left shifted.

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

obtaining a subset of even-term syndromes associated with the binary BCH encoded data, wherein a subset of odd-term syndromes is associated with the subset of even-term syndromes;

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

)}(x), loading the subset of even-term syndromes into the variant error-locator polynomial at a 0^th iteration of a decoding process, {circumflex over (Ω

)}⁽⁰⁾(x), wherein an error locator polynomial at an r^th iteration of the decoding process, Λ

^(r)(x), a syndrome polynomial, S(x), an error evaluator polynomial at the r^th iteration of the decoding process, Ω

^(r)(x), and the variant error-locator polynomial at the r^th iteration of the decoding process, {circumflex over (Ω

)}^(r)(x), have the following relationship;

Λ

^(r)(x)S(x) =Ω

^(r)(x) +x^r{circumflex over (Ω

)}^(r)(x); and

excluding the subset of odd-term syndromes from the initialization of the variant error-locator polynomial at the 0^th iteration of the decoding process, {circumflex over (Ω

)}⁽⁰⁾(x).

13. The computer program product of claim 12, wherein the computer instructions for loading further include computer instructions for using zero values in place of the subset of odd-term syndromes.

14. The computer program product of claim 12, wherein the computer instructions are performed during an iterative discrepancy calculation which outputs discrepancy values, Δ

.

15. The computer program product of claim 12, wherein the computer instructions are performed during a parallel inversionless Berlekamp process which outputs an error locator polynomial, Λ

.

16. The computer program product of claim 12 further comprising computer instructions for using an odd-term error-locator update module which is not left shifted.