Methods and apparatus for coding and decoding data using reed-solomon codes

• US 20050149832A1
• Filed: 12/12/2003
• Published: 07/07/2005
• Est. Priority Date: 12/12/2003
• Status: Active Grant

• Current Assignee: Analog Devices, Inc.
• Original Assignee: Analog Devices, Inc.
• Inventors: Liberol, Boris, Lee, Yoon Yung
• Granted Patent: US 7,162,679 B2
• Time in Patent Office: Days
• US Class Current: 714/781
• CPC Class Codes: H03M 13/158 Finite field arithmetic processing
• CPC Class Codes: H03M 13/159 Remainder calculation, e.g. for encoding and syndrome calculation
• CPC Class Codes: H03M 13/6505 Memory efficient implementations
• CPC Class Codes: H03M 13/6569 Implementation on processors, e.g. DSPs, or software implementations

Abstract

Methods and apparatus are provided for encoding data. The method includes (a) providing a first table of first component values multiplied by code generator coefficients and a second table of second component values multiplied by the code generator coefficients, (b) determining a Galois field element based on a message symbol and a high order remainder symbol, (c) separating the Galois field element into first and second components, (d) using the first component and a generator coefficient index to access one or more first table values in the first table and using the second component and the generator coefficient index to access one or more second table values in the second table, (e) determining a current remainder symbol based on first and second table values having equal generator coefficient indices, and a previous remainder symbol, (f) performing step (e) for each generator coefficient of the code generator to provide a set of remainder symbols, and (g) performing steps (b)-(f) for each message symbol in a codeword to provide a set of final remainder symbols which constitute check symbols to be transmitted with the message symbols of the codeword.

Claims

1. A method for encoding data, comprising:

(a) providing a first table of first component values multiplied by code generator coefficients and a second table of second component values multiplied by the code generator coefficients;

(b) determining a Galois field element based on a message symbol and a high order remainder symbol;

(c) separating the Galois field element into first and second components;

(d) using the first component and a generator coefficient index to access one or more first table values in the first table and using the second component and the generator coefficient index to access one or more second table values in the second table,

(e) determining a current remainder symbol based on first and second table values having equal generator coefficient indices, and a previous remainder symbol;

(f) performing step (e) for each generator coefficient of the code generator to provide a group of remainder symbols; and

(g) performing steps (b)-(f) for each message symbol in a codeword to provide a group of final remainder symbols which constitute check symbols to be transmitted with the message symbols of the codeword.

2. A method as defined in claim 1, wherein step (b) comprises an exclusive OR operation on the message symbol and the high order remainder symbol.

3. A method as defined in claim 2, wherein step (e) comprises an exclusive OR operation on the first and second table values to provide an intermediate value, and an exclusive OR operation on the intermediate value and the previous remainder symbol to provide the current remainder symbol.

4. A method as defined in claim 1, wherein the first and second components comprise high and low halfwords, respectively, of the Galois field element.

5. A method as defined in claim 1, wherein the message symbols of the codeword comprise message bytes.

6. A method as defined in claim 5, wherein step (g) produces 16 check symbols for correcting up to eight errors in the codeword.

7. A method as defined in claim 1, wherein step (d) comprises accessing two or more sets of first and second table values in parallel and wherein step (e) comprises determining two or more current remainder symbols in parallel.

8. A method as defined in claim 1, wherein separating the Galois field element into first and second components comprises ANDing the Galois field element with first and second masks.

9. A method as defined in claim 1, wherein step (d) comprises accessing w sets of first and second table values in parallel, wherein w represents a word width of a processor performing encoding in units of the Galois field element, and wherein step (e) comprises determining w current remainder symbols in parallel.

10. A method as defined in claim 1, wherein step (a) comprises generating, during operation, the table values in the first and second tables for prescribed code parameters.

11. A method as defined in claim 1, wherein step (g) comprises providing a number of check symbols equal to the number of generator coefficients.

12. A method as defined in claim 1, wherein step (g) comprises providing a number of check symbols less than the number of generator coefficients.

13. Apparatus for encoding data, comprising:

a first lookup table containing first component values multiplied by code generator coefficients;

a second lookup table containing second component values multiplied by the code generator coefficients; and

a processor comprising means for determining a Galois field element based on a message symbol and a high order remainder symbol, means for separating the Galois field element into first and second components, means, using the first component and a generator coefficient index, for accessing one or more first table values in the first lookup table, means, using the second component and the generator coefficient index, for accessing one or more second table values in the second table; and

means for determining a current remainder symbol, based on first and second table values having equal generator coefficient indices, and a previous remainder symbol, for each generator coefficient of the code generator to provide a group of remainder symbols, wherein each message symbol of a codeword is processed to provide a group of final remainder symbols which constitute check symbols to be transmitted with the message symbols of the codeword.

14. Apparatus as defined in claim 13, wherein the means for determining a Galois field element comprises means for performing an exclusive OR operation on the message symbol and the high order remainder symbol.

15. Apparatus as defined in claim 13, wherein the means for determining a current remainder symbol comprises means for performing an exclusive OR operation on the first and second table values to provide an intermediate value and means for performing an exclusive OR operation on the intermediate value and the previous remainder symbol to provide the current remainder symbol.

16. Apparatus as defined in claim 13, wherein the first and second components comprise high and low halfwords, respectively, of the Galois field element.

17. Apparatus as defined in claim 13, wherein the message symbols of the codeword comprise message bytes.

18. Apparatus as defined in claim 13, wherein the processor is configured to produce 16 check symbols for correcting up to eight errors in the codeword.

19. Apparatus as defined in claim 13, wherein the means for accessing first and second table values comprises means for accessing two or more sets of first and second table values in parallel, and wherein the means for determining a current remainder symbol comprises means for determining two or more current remainder symbols in parallel.

20. Apparatus as defined in claim 13, wherein the means for separating the Galois field element into first and second components comprises means for ANDing the Galois field element with first and second masks.

21. Apparatus as defined in claim 13, wherein the means for accessing first and second table values comprises means for accessing w sets of first and second table values in parallel, wherein w represents a word width of the processor in units of the Galois field element, and wherein the means for determining a current remainder symbol comprises means for determining w current remainder symbols in parallel.

22. Apparatus as defined in claim 13, wherein the processor further comprises means for generating, during operation, the table values in the first and second lookup tables for prescribed code parameters.

23. Apparatus as defined in claim 13, wherein each message symbol of the codeword is processed to provide a number of check symbols equal to the number of generator coefficients.

24. Apparatus as defined in claim 13, wherein each message symbol of the codeword is processed to provide a number of check symbols less than the number of generator coefficients.