Efficient Chien search method and system in Reed-Solomon decoding

• US 20090055716A1
• Filed: 10/25/2007
• Published: 02/26/2009
• Est. Priority Date: 08/24/2007
• Status: Active Grant

• Current Assignee: Lite-On Technology Corporation
• Original Assignee: Lite-On Technology Corporation
• Inventors: Hsu, Yueh-Teng
• Granted Patent: US 8,060,809 B2
• Time in Patent Office: Days
• 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. An efficient Chien search method in Reed-Solomon decoding, which is adapted 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;

(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 efficient Chien search method according to claim 1, wherein step (a) includes a sub-step:

(a-1) if 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.

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

4. The efficient Chien search method according to claim 3, wherein, supposing 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 sub-step (a-1) is P(k), and 0≦

k<

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

₀=k.

5. The efficient Chien search method according to claim 2, wherein step (a) further includes a sub-step:

(a-2) if 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.

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

7. The efficient Chien search method according to claim 6, wherein, supposing 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 sub-step (a-2) 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₁.

8. An efficient Chien search system for Reed-Solomon decoding, which is adapted for use in a processor having a parallel processing instruction set, said efficient 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; and

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.

9. The efficient Chien search system according to claim 8, further comprising a pre-constructed first error location table, and wherein, if 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, wherein the number of said at least one error symbol location is equal to the first predetermined value.

10. The efficient Chien search system according to claim 9, wherein the first predetermined value is 1.

11. The efficient Chien search system according to claim 10, wherein, supposing 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.

12. The efficient Chien search system according to claim 9, further comprising a pre-constructed second error location table, and wherein, if 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.

13. The efficient Chien search system according to claim 12, wherein the second predetermined value is 2.

14. The efficient Chien search system according to claim 13, wherein, supposing 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₁.