Efficient chien search method in reed-solomon decoding, and machine-readable recording medium including instructions for executing the method

• US 7,984,366 B2
• Filed: 08/15/2007
• Issued: 07/19/2011
• Est. Priority Date: 06/23/2007
• Status: Expired due to Fees

• Current Assignee: Lite-On Technology Corporation
• Original Assignee: Lite-On Technology Corporation
• Inventors: Hsu, Yueh-Teng
• Primary Examiner(s): CHAUDRY, MUJTABA M
• Application Number:
  US11/839,045
• Publication Number:
  US 20080320371A1
• Time in Patent Office: 1,434 Days
• Field of Search: 714/784, 714/774
• US Class Current: 714/784
• 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/6569 Implementation on processors, e.g. DSPs, or software implementations

Abstract

An efficient Chien search method in Reed-Solomon decoding is adapted to be implemented in a processor having a parallel processing instruction set. The method includes the following steps: (a) calculating an error evaluation value; (b) subjecting the error evaluation value to mapping processing so as to find an index adjusting value; (c) storing a symbol index into an error location memory corresponding to a location index; (d) updating the location index according to the index adjusting value; (e) updating the symbol index; and (f) repeating steps (a) to (e) a particular number of times. The method primarily aims to reduce program flow branching so as to enhance the computation efficiency of the Chien search process.

Claims

1. An efficient Chien search method in Reed-Solomon decoding, which is adapted to be implemented in a processor having a parallel processing instruction set, the efficient Chien search method comprising the following steps:

(a) calculating an error evaluation value;

(b) subjecting the error evaluation value to mapping processing so as to find an index adjusting value;

(c) storing a symbol index into an error location memory corresponding to a location index;

(d) updating the location index according to the index adjusting value;

(e) updating the symbol index; and

(f) repeating steps (a) to (e) a particular number of times.

2. The efficient Chien search method according to claim 1, wherein the particular number of times is determined by a total number of symbols in a received Reed-Solomon block code.

3. The efficient Chien search method according to claim 2, wherein, in step (b), the index adjusting value is 1 if the error evaluation value is 0, and the index adjusting value is 0 if otherwise.

4. The efficient Chien search method according to claim 3, wherein, in step (d), the index adjusting value is added to the location index so as to update the location index.

5. The efficient Chien search method according to claim 1, wherein, in step (b), the error evaluation value is subjected to mapping processing by means of the parallel processing instruction set so as to find the index adjusting value.

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

(a) calculating an error evaluation value;

(b) subjecting the error evaluation value to mapping processing so as to obtain an index adjusting value;

(c) storing a symbol index into an error location memory corresponding to a location index;

(d) updating the location index according to the index adjusting value;

(e) updating the symbol index; and

(f) repeating steps (a) to (e) a particular number of times.

7. The machine-readable recording medium according to claim 6, wherein the particular number of times is determined by a total number of symbols in a received Reed-Solomon block code.

8. The machine-readable recording medium according to claim 7, wherein, in step (b), the index adjusting value is 1 if the error evaluation value is 0, and the index adjusting value is 0 if otherwise.

9. The machine-readable recording medium according to claim 8, wherein, in step (d), the index adjusting value is added to the location index so as to update the location index.

10. The machine-readable recording medium according to claim 6, wherein, in step (b), the error evaluation value is subjected to mapping processing by means of the parallel processing instruction set so as to find the index adjusting value.