Forward error correction apparatus and methods

• US 6,725,416 B2
• Filed: 02/04/2003
• Issued: 04/20/2004
• Est. Priority Date: 09/10/1999
• Status: Expired due to Term

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: LSI Logic Corporation (Broadcom, Inc.)
• Inventors: Dadurian, Tan C.
• Primary Examiner(s): Chung, Phung M.
• Application Number:
  US10/358,022
• Publication Number:
  US 20030126544A1
• Time in Patent Office: 441 Days
• Field of Search: 714/785, 714/784, 714/746, 714/781, 714/782, 714/763
• US Class Current: 714/785
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/154 Error and erasure correction, e.g. by using the error and erasure locator or Forney polynomial
• 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/158 Finite field arithmetic processing

Abstract

Forward error correction apparatus and methods are described. A forward errro correction method includes: (a) computing syndromes values; (b) computing an erasure location polynomial based upon one or more erasure locations; (c) computing modified syndromes based upon the computed erasure location polynomial and the computed syndrome values; (d) computing coefficients of an error location polynomial based upon the computed modified syndromes; (e) computing a composite error location polynomial based upon the computed coefficients of the error location polynomial; (f) computing a Chien polynomial based upon the computed composite error location polynomial; (g) performing a redundant Chien search on the computed composite error location polynomial to obtain error location values; and (h) evaluating the computed Chien polynomial based upon the error location values to obtain error and erasure values. A forward erro correction system includes: first and second simultaneously accessible memory locations; first, second and third register banks; and a micro-sequencer configured to choreograph a method of correcting errors and erasures by coordinating the flow of data into the first and second memory locations and the first, second and third register banks.

Claims

1. A system for correcting errors and erasures in a data signal, comprising:

first, second, third and fourth simultaneously accessible memory locations;

first, second and third register banks each capable of storing a plurality of polynomial coefficients; and

a micro-sequencer configured to correct the errors and erasures by (i) executing a decoding process and (ii) coordinating a flow of the polynomial coefficients among the first, second, third and fourth memory locations and the first, second and third register banks.

2. The system of claim 1, wherein the micro-sequencer is configured to perform the following sequence of steps:

(a) compute syndromes values;

(b) compute an erasure location polynomial based upon one or more erasure locations;

(c) compute modified syndromes based upon the computed erasure location polynomial and the computed syndrome values;

(d) compute coefficients of an error location polynomial based upon the computed modified syndromes;

(e) compute a composite error location polynomial based upon the computed coefficients of the error location polynomial;

(f) compute a Chien polynomial based upon the computed composite error location polynomial;

(g) perform a redundant Chien search on the computed composite error location polynomial to obtain error location values; and

(h) evaluate the computed Chien polynomial based upon the error location values to obtain error and erasure values.

3. The system of claim 2, wherein the coefficients of the error location polynomial are computed based upon a Berlakamp error correction algorithm.

4. The system of claim 3, wherein:

the coefficients of the error location polynomial are computed using eighteen registers.

5. The system of claim 3, wherein:

the coefficients of the error location polynomial are computed in response to one or more hardware instructions.

6. The system of claim 2, wherein the computed syndrome values are stored in the first memory locations.

7. The system of claim 6, wherein the computed erasure location polynomial is stored in the first register bank.

8. The system of claim 7, wherein the modified syndromes are stored in the second memory locations.

9. The system of claim 8, wherein the computed coefficients of the error location polynomial are stored in the second register bank.

10. The system of claim 9, wherein the computed composite error location polynomial is stored in the first register bank.

11. The system of claim 10, wherein the computed Chien polynomial is stored in the third register bank.

12. The system of claim 11, wherein the computed error location values are stored in the second memory locations.

13. The system of claim 2, wherein:

the redundant Chien search is performed using sixteen registers.

14. The system of claim 1, wherein (i) the first, second, third and fourth memory locations, (ii) the first, second and third register banks and (iii) the micro-sequencer are part of an error corrector circuit configured to generate corrected error and erasure values in response to syndromes.

15. The system of claim 14, further comprising:

a memory interface configured to (i) read one or more error correction code (ECC) blocks from a memory and (ii) generate the syndromes in response to the ECC blocks.

16. The system of claim 15, further comprising:

a processor configured to generate the ECC blocks in response to the data signal and write the ECC blocks to the memory, wherein the processor performs synchronization, demodulation and deinterleaving of the data signal.

17. The system of claim 15, wherein:

the memory interface is further configured to write the corrected error and erasure values to the memory at corresponding error and erasure locations.

18. The system of claim 17, wherein:

the memory interface is further configured to (i) descrammble data corrected in response to the corrected error and erasure values, (ii) check the corrected data for errors and (iii) store the corrected data to a track buffer.

19. The system of claim 1, wherein:

the micro-sequencer is further configured to issue instructions configured to (i) execute the decoding process and (ii) coordinate the flow of the polynomial coefficients.

20. The system of claim 1, wherein the first, second, third and fourth simultaneously accessible memory locations comprise random access memory (RAM).