Method for efficiently calculating syndromes in reed-solomon decoding, and machine-readable storage medium storing instructions for executing the method

• US 8,042,026 B2
• Filed: 07/30/2007
• Issued: 10/18/2011
• Est. Priority Date: 06/06/2007
• Status: Expired due to Fees

• Current Assignee: Lite-On Technology Corporation
• Original Assignee: Lite-On Technology Corporation
• Inventors: Hsu, Matthew
• Primary Examiner(s): RIZK, SAMIR WADIE
• Application Number:
  US11/878,956
• Publication Number:
  US 20080307289A1
• Time in Patent Office: 1,541 Days
• Field of Search: 714/759, 714/784
• US Class Current: 714/784
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/157 Polynomial evaluation, i.e. determination of a polynomial sum at a given value
• CPC Class Codes: H03M 13/6561 Parallelized implementations
• CPC Class Codes: H03M 13/6569 Implementation on processors, e.g. DSPs, or software implementations

Abstract

A method for efficiently calculating syndromes in Reed-Solomon decoding is adapted to be implemented in a processor having a parallel processing instruction set. The method includes: (a) initializing a syndrome vector; (b) obtaining a symbol from a Reed-Solomon block code; (c) finding a lookup index based on the symbol; (d) using the parallel processing instruction set, obtaining a finite field product vector corresponding to the lookup index from a finite field vector multiplication table that includes at least one finite field product vector; (e) using the parallel processing instruction set, performing vector finite field addition on the finite field product vector corresponding to the lookup index and the syndrome vector, thereby obtaining an updated syndrome vector; and (f) outputting the updated syndrome vector.

Claims

1. A method for efficiently calculating syndromes in Reed-Solomon coding, which is adapted to be implemented in a processor having a parallel processing instruction set, the method comprising the following steps:

(a) configuring the processor to initialize a syndrome vector;

(b) configuring the processor to obtain a symbol from a Reed-Solomon block code;

(c) configuring the processor to find a lookup index based on the symbol;

(d) configuring the processor to use the parallel processing instruction set, to obtain a finite field product vector corresponding to the lookup index from a finite field vector multiplication table that includes at least one finite field product vector in which the finite field product vector may be expressed as [γ

_j×

(α

¹)^j,γ

_j×

(α

²)^j,γ

_j×

(α

³)^j, . . . , γ

_j×

(α

^2t)^j], where 0<

j<

n, γ

_j represents the j^th symbol obtained from the Reed-Solomon block code, t represents the maximum number of correctable errors, α

is a known constant, n represents the total number of symbols of the Reed-Solomon block code, and both γ

_j and α

are finite field elements;

(e) configuring the processor to use the parallel processing instruction set to perform vector finite field addition on the finite field product vector corresponding to the lookup index and the syndrome vector, thereby obtaining an updated syndrome vector; and

(f) configuring the processor to output the updated syndrome vector.

2. The method according to claim 1, further comprising, between steps (e) and (f), a step (g) of repeating steps (b) to (e).

3. The method according to claim 1, wherein γ

_j,α

ε

GF(2^m), and 2^m represents the total number of corresponding elements in a Galois field.

4. The method according to claim 3, wherein the lookup index is calculated using the following equation:

(j−

1)×

2t×

2^m+γ

_j×

2t.

5. A machine-readable tangible recording medium, which stores a plurality of machine executable instructions, the instructions being used to execute the following steps in a processor having a parallel processing instruction set:

(a) initializing a syndrome vector;

(b) obtaining a symbol from a Reed-Solomon block code;

(c) finding a lookup index based on the symbol;

(d) using the parallel processing instruction set, obtaining a finite field product vector corresponding to the lookup index from a finite field vector multiplication table that includes at least one finite field product vector, wherein the finite field product vector may be expressed as [γ

_j×

(α

¹)^j,γ

_j×

(α

²)^j,γ

_j×

(α

³)^j, . . . , γ

_j×

(α

^2t)^j], where 0<

j<

n, γ

_j represents the j^th symbol obtained from the Reed-Solomon block code, t represents the maximum number of correctable errors, α

is a known constant, n represents the total number of symbols of the Reed-Solomon block code, and both γ

_j and α

are finite field elements;

(e) using the parallel processing instruction set, performing vector finite field addition on the finite field product vector corresponding to the lookup index and the syndrome vector, thereby obtaining an updated syndrome vector; and

(f) outputting the updated syndrome vector.

6. The machine-readable recording medium according to claim 5, wherein the instructions are further used to execute a step (g) of repeating steps (h) to (e) between steps (e) and (f).

7. The machine-readable recording medium according to claim 5, wherein γ

_j,α

ε

GF(2^m), and 2^m represents the total number of corresponding elements in a Galois field.

8. The machine-readable recording medium according to claim 7, wherein the lookup index is calculated using the following equation:

(j−

1)×

2t×

2^m+γ

_j×

2t.