Hardware efficient decoding system for Bose, Ray-Chaudhuri, Hocquenghem (BCH) product codes

• US 7,774,688 B1
• Filed: 10/11/2007
• Issued: 08/10/2010
• Est. Priority Date: 10/11/2006
• Status: Active Grant

• Current Assignee: Marvell Asia Pte Limited (Marvell Technology Group Limited)
• Original Assignee: Marvell International Limited (Marvell Technology Group Limited)
• Inventors: Teng, Heng, Burd, Gregory, Yang, Xueshi, Wu, Zining
• Primary Examiner(s): Abraham; Esaw T
• Application Number:
  US11/974,141
• Time in Patent Office: 1,034 Days
• Field of Search: 714/782, 714/784, 714/785
• US Class Current: 714/782
• CPC Class Codes: H03M 13/152 Bose-Chaudhuri-Hocquenghem [BCH] codes
• CPC Class Codes: H03M 13/2909 Product codes
• CPC Class Codes: H03M 13/293 with erasure setting
• CPC Class Codes: H03M 13/3746 with iterative decoding

Abstract

A decoder that decodes Bose, Ray-Chaudhuri, Hocquenghem (BCH) codewords includes an inner decoding module that decodes inner codes of two dimensional BCH product codewords and that includes an error decoding module that computes error values, an outer decoding module that decodes outer codes of the two dimensional BCH product codewords, and an error correction module that employs the error decoding module to iteratively correct errors in the two-dimensional BCH product codewords.

Claims

1. A decoder that decodes two-dimensional Bose, Ray-Chaudhuri, Hocquenghem (BCH) codewords, the decoder comprising:

an inner decoding module that (i) decodes inner codes of the two-dimensional BCH product codewords and (ii) includes an error decoding module that computes inner error locator polynomials for the inner codes of the two-dimensional BCH product codewords;

an outer decoding module that decodes outer codes of the two-dimensional BCH product codewords; and

an error correction module that selectively iteratively corrects errors in the two-dimensional BCH product codewords, wherein while iteratively correcting errors, the error correction module employs the error decoding module to calculate outer error locator polynomials for the outer codes of the two-dimensional BCH product codewords.

2. The decoder of claim 1, wherein the error decoding module further comprises a Chien search module that calculates roots of the inner error locator polynomials.

3. The decoder of claim 1, wherein the error decoding module employs at least one of a Berlekamp-Massey algorithm, a Euclidian algorithm, and a Berlekamp-Welch decoding algorithm to compute the inner error locator polynomials.

4. The decoder of claim 1, wherein the inner decoding module marks error rows of the BCH codewords as erasures for processing by the outer decoding module.

5. The decoder of claim 1, wherein the outer decoding module comprises:

an outer BCH syndrome computation module that performs a syndrome computation on the outer codes; and

an error evaluation polynomial module that calculates error evaluation polynomials based on the outer BCH codewords.

6. The decoder of claim 5, wherein the outer decoding module further comprises an error value computation module that computes error values based on the outer BCH codewords.

7. The decoder of claim 6, wherein while selectively iteratively correcting errors, the error evaluation polynomial module and the error value computation module are idle.

8. The decoder of claim 1, wherein the error correction module comprises (i) a central processing unit and (ii) a memory that stores computer readable instructions, wherein the computer readable instructions implement the error correction module.

9. The decoder of claim 1, wherein the error decoding module calculates roots of the inner error locator polynomials.

10. The decoder of claim 9, wherein the error decoding module calculates error values corresponding to the roots of the inner error locator polynomials.

11. The decoder of claim 1, wherein while iteratively correcting errors, the error correction module employs the error decoding module to:

compute the inner error locator polynomials for the inner codes and the outer error locator polynomials for the outer codes;

calculate roots of the inner error locator polynomials and the outer error locator polynomials; and

calculate error values corresponding to the roots of the inner error locator polynomials and the roots of the outer error locator polynomials.

12. The decoder of claim 11, wherein the outer decoding module comprises:

an outer BCH syndrome computation module that performs a syndrome computation on the outer codes;

an error evaluation polynomial module that calculates error evaluation polynomials based on the outer BCH codewords; and

an error value computation module that computes error values based on the outer BCH codewords,

wherein while iteratively correcting errors, the error evaluation polynomial module and the error value computation module are idle.

13. The decoder of claim 1, wherein while iteratively correcting errors, the error correction module employs the error decoding module to decode both (i) the outer codes of the two-dimensional BCH product codewords and (ii) the inner codes of the two-dimensional BCH product codewords.

14. The decoder of claim 1, wherein the error correction module iteratively corrects errors when a number of errors from the inner decoding module exceeds an erasure capacity of the outer decoding module.

15. A method of decoding two-dimensional Bose, Ray-Chaudhuri, Hocquenghem (BCH) codewords, the method comprising:

providing an error decoding module that calculates inner error locator polynomials;

decoding inner codes of the two-dimensional BCH product codewords using the error decoding module;

providing an outer code decoding module;

decoding outer codes of the two-dimensional BCH product codewords using the outer code decoding module;

selectively performing iterative error correction; and

while the iterative error correction is being performed, using the error decoding module to calculate outer error locator polynomials to correct errors in the outer codes of the two-dimensional BCH product codewords.

16. The method of claim 15, wherein the error decoding module calculates roots of the inner error locator polynomials.

17. The method of claim 15, wherein calculating the inner error locator polynomials employs at least one of a Berlekamp-Massey algorithm, a Euclidian algorithm, and a Berlekamp-Welch decoding algorithm.

18. The method of claim 15, wherein decoding inner codes includes marking error rows of the BCH codewords as erasures.

19. The method of claim 18, wherein decoding outer codes further comprises:

performing a syndrome computation on the outer codes; and

calculating error evaluation polynomials based on the outer BCH codewords.

20. The method of claim 19, wherein decoding outer codes further comprises computing error values based on the outer BCH codewords.

21. The method of claim 15, further comprising providing (i) a central processing unit and (ii) a memory that stores computer readable instructions, wherein the computer readable instructions implement the selectively performing iterative error correction.