Efficient Chien search method and system in Reed-Solomon decoding

• US 8,060,809 B2
• Filed: 10/25/2007
• Issued: 11/15/2011
• Est. Priority Date: 08/24/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): BRITT, CYNTHIA H
• Application Number:
  US11/976,473
• Publication Number:
  US 20090055716A1
• Time in Patent Office: 1,482 Days
• Field of Search: 714/759, 714/779, 714/780, 714/781, 714/784
• US Class Current: 714/784
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• 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/6561 Parallelized implementations

Abstract

An efficient Chien search method in Reed-Solomon decoding is adapted for use in a processor having a parallel processing instruction set. The method includes the following steps: (a) if an error location polynomial that has been found matches a preset condition, finding at least one error symbol location directly through table lookup; (b) if the error location polynomial does not match the preset condition, executing steps (c) to (e); (c) calculating an error evaluation value; (d) if the error evaluation value is equal to 0, storing an error symbol location in an error location memory; and (e) if the error evaluation value is not equal to 0, the flow returning to step (c).

Claims

1. A Chien search method in Reed-Solomon decoding, which is suitable for use in a processor having a parallel processing instruction set, the method comprising the following steps:

(a) if an error location polynomial that has been found matches a preset condition, finding at least one error symbol location according to the error location polynomial directly through table lookup, when a length of the error location polynomial is equal to a first predetermined value, looking up a pre-constructed first error location table to find said at least one error symbol location, wherein the number of said at least one error symbol location is equal to the first predetermined value;

(b) if the error location polynomial does not match the preset condition, executing steps (c) to (e);

(c) calculating an error evaluation value according to the error location polynomial;

(d) if the error evaluation value is equal to 0, storing an error symbol location in an error location memory; and

(e) if the error evaluation value is not equal to 0, the flow returning to step (c).

2. The Chien search method according to claim 1, wherein the first predetermined value in step (a) is 1.

3. The Chien search method according to claim 2, wherein, the error location polynomial having the length of 1 is expressed as Λ

(α

ⁱ)=λ

₀, where λ

₀ε

GF(2^m) and 2^m represents a total number of corresponding elements in the Galois field, corresponding content in the first error location table in step (a) is P(k), and 0≦

k<

2^m, P(k) representing the error symbol location previously found when λ

₀=k.

4. The Chien search method according to claim 1, wherein step (a) further includes:

if when the length of the error location polynomial is equal to a second predetermined value, looking up a pre-constructed second error location table to find said at least one error symbol location, wherein the number of said at least one error symbol location is equal to the second predetermined value.

5. The Chien search method according to claim 4, wherein the second predetermined value in step (a) is 2.

6. The Chien search method according to claim 5, wherein, the error location polynomial having the length of 2 is expressed as Λ

(α

ⁱ)=λ

₀+λ

₁α

ⁱ, where λ

₀,λ

₁ε

GF(2^m) and 2^m represents a total number of corresponding elements in the Galois field, corresponding content in the second error location table in step (a) is P₀(k₀,k₁) and P₁(k₀,k₁), and 0≦

k₀,k₁<

2^m, P₀(k₀,k₁) and P₁(k₀,k₁) respectively representing two error symbol locations previously found when λ

₀=k₀,λ

₁=k₁.

7. An Chien search system for Reed-Solomon decoding, which is suitable for use in a processor having a parallel processing instruction set, said Chien search system comprising:

a first determining module for determining whether an error location polynomial that has been found matches a preset condition;

a table look-up module for finding at least one error symbol location according to the error location polynomial directly through table lookup when said first determining module determines a match with the preset condition;

an error evaluation module for calculating an error evaluation value according to the error location polynomial when said first determining module determines no match with the preset condition;

a second determining module for determining whether the error evaluation value is equal to 0;

a memory write module for storing an error symbol location in an error location memory when the error evaluation value is determined by said second determining module to be equal to 0; and

a pre-constructed first error location table;

wherein, when said first determining module determines that the error location polynomial has a length equal to a first predetermined value, said table lookup module finds said at least one error symbol location from said first error location table, the number of said at least one error symbol location being equal to the first predetermined value.

8. The Chien search system according to claim 7, wherein the first predetermined value is 1.

9. The Chien search system according to claim 8, wherein, the error location polynomial having the length of 1 is expressed as Λ

(α

ⁱ)=λ

₀, where λ

₀ε

GF(2^m) and 2^m represents a total number of corresponding elements in the Galois field, corresponding content in said first error location table is P(k), 0≦

k<

2^m, P(k) representing the error symbol location previously found when λ

₀=k.

10. The Chien search system according to claim 7, further comprising a pre-constructed second error location table, and wherein, when said first determining module determines that the error location polynomial has a length equal to a second predetermined value, said table lookup module finds said at least one error symbol location from said second error location table, wherein the number of said at least one error symbol location is equal to the second predetermined value.

11. The Chien search system according to claim 10, wherein the second predetermined value is 2.

12. The Chien search system according to claim 11, wherein, the error location polynomial having the length of 2 is expressed as Λ

(α

ⁱ)=λ

₀+λ

₁α

ⁱ, where λ

₀,λ

₁ε

GF(2^m) and 2^m represents a total number of corresponding elements in the Galois field, corresponding content in said second error location table is P₀(k₀,k₁) and P₁(k₀,k₁), and 0≦

k₀,k₁<

2^m, P₀(k₀,k₁) and P₁(k₀,k₁) respectively representing two error symbol locations previously found when λ

₀=k₀,λ

₁=k₁.