High speed hardware implementation of modified Reed-Solomon decoder

• US 7,539,927 B2
• Filed: 04/14/2005
• Issued: 05/26/2009
• Est. Priority Date: 04/14/2005
• Status: Active Grant

• Current Assignee: Industrial Technology Research Institute
• Original Assignee: Industrial Technology Research Institute
• Inventors: Shieh, Shin-Lin, Sheen, Wern-Ho, Lee, Shuenn-Gi
• Primary Examiner(s): Baker; Stephen M
• Application Number:
  US11/105,420
• Publication Number:
  US 20060236212A1
• Time in Patent Office: 1,503 Days
• Field of Search: 714/759, 714/774, 714/784
• US Class Current: 714/784
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/153 using the Berlekamp-Massey algorithm
• CPC Class Codes: H03M 13/1535 using the Euclid algorithm
• 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/155 Shortening or extension of codes

Abstract

A decoder suitable for use in a digital communications system utilizing an RS(n′, k′) code modified from an RS(n, k) code receives n′-symbol vectors each including k′ message symbols and r′=n′−k′ parity symbols and decodes the n′-symbol vectors to correct errors therein, wherein n, k, n′, and k′ are integers, and k′<n′<n, k′<k<n, and wherein the decoder stores therein one erasure locator polynomial σ₀(x). The decoder includes a syndrome calculator for receiving the n′-symbol vectors and for calculating syndromes of each n′-symbol vector, wherein the i-th syndrome S_i of one n′-symbol vector R′, (r_n′−1, r_n′−2, . . . , r₀), is S_i=R_s(αⁱ⁺¹) for i=0, 1, . . . , n−k−1, wherein R_s(x)=r_n′−1x^n′−1+r_n′−2x^n′−2+ . . . +r₀, and means for finding the locations and values of the errors in each n′-symbol vector using the syndromes thereof and the one erasure locator polynomial σ₀(x).

Claims

1. A decoder suitable for use in a digital communications system utilizing an RS(n′

, k′

) code modified from an RS(n, k) code, wherein the decoder receives n′

-symbol vectors each including k′

message symbols and r′

=n′

−

k′

parity symbols and decodes the n′

-symbol vectors to correct errors therein, wherein n, k, n′

, and k′

are integers, and k′

<

n′

<

n, k′

<

k <

n, and wherein the decoder stores one erasure locator polynomial σ

₀(x), the decoder comprising;

a syndrome calculator for receiving the n′

-symbol vectors and for calculating syndromes of each n′

-symbol vector, wherein the i-th syndrome S_i of one n′

-symbol vector R′

, (r<sub>n′

−

1</sub>, r<sub>n′

−

2</sub>, . . . , r₀), is S_i=R_s(α

ⁱ⁺¹) for i=0, 1, . . . , n−

k−

1, wherein R_s(x)=r<sub>n′

−

1</sub>x<sup>n′

−

1</sup>+r<sub>n′

−

2</sub>x<sup>n′

−

2</sup>+ . . . +r₀;

an index adjustment circuit for generating an adjusted error/erasure locator polynomial {tilde over (σ

)}(x) and an adjusted error/erasure evaluator polynomial {tilde over (ω

)}(x) based on the syndromes calculated by the syndrome calculator;

a memory device for storing the one erasure locator polynomial σ

₀(x) and a look-up table; and

means for finding the locations and values of the errors in each n′

-symbol vector based on the adjusted error/erasure locator polynomial {tilde over (σ

)}(x) and the adjusted error/erasure evaluator polynomial {tilde over (ω

)}(x), using the look-up table.

2. The decoder of claim 1, further comprising means for correcting the errors in the received n′

-symbol vectors.

3. The decoder of claim 1, wherein the decoder is suitable to decode a plurality of modified RS codes each corresponding to an erasure locator polynomial, the decoder stores the erasure locator polynomials for all of the plurality of modified RS codes, and the one erasure locator polynomial {tilde over (σ

)}₀(x) is selected from the stored erasure locator polynomials.

4. The decoder of claim 1, further comprising a modified syndrome calculator for calculating a modified syndrome polynomial S₀(x) based on the syndromes calculated by the syndromes calculator and the one erasure locator polynomial, wherein

$S_0$

( x ) = S ⁡

( x ) ⁢

σ

0 ⁡

( x ) $\mathrm{and}$ $S<br><br>\left(x\right)=\underset{i=1}{\overset{n-k-1}{\sum <br><br>}}<br><br>S_i<br><br>x^i.$

5. The decoder of claim 4, further comprising a key equation solver for solving a key equation to generate an error/erasure locator polynomial σ

(x) and an error/erasure evaluator polynomial ω

(x), wherein the key equation is S₀(x)σ

₁(x)=ω

(x) mod x<sup>n−

k</sup>, and σ

(x)=σ

₀(x)σ

₁(x), and wherein σ

₁(x) is an error locator polynomial.

6. The decoder of claim 5, wherein the key equation solver comprises a modified Euclidean algorithm processor (ME processor) including a modified Euclidean divider for computing the error/erasure evaluator polynomial ω

(x), a modified Euclidean multiplier for computing the error locator polynomial σ

₁(x), and an error/erasure locator polynomial calculator for calculating the error/erasure locator polynomial σ

(x).

7. The decoder of claim 5, wherein the index adjustment circuit is configured to generate the adjusted error/erasure locator polynomial {tilde over (σ

)}(x) and the adjusted error/erasure evaluator polynomial {tilde over (ω

)}(x) based on the error/erasure locator polynomial σ

(x) and the error/erasure evaluator polynomial ω

(x).

8. The decoder of claim 7, wherein the means for finding the locations and values of the errors comprises a Chien search block for evaluating the adjusted error/erasure locator polynomial {tilde over (σ

)}(x) and {tilde over (σ

)}′

(x) for x =α

⁰, α

¹, . . . , α

<sup>n′

−

1</sup>, and a Forney algorithm block for evaluating the adjusted error/erasure evaluator polynomial {tilde over (ω

)}(x) for x =α

⁰, α

¹, . . . , α

<sup>n′

−

1</sup>, wherein {tilde over (σ

)}′

(x) is a derivative of σ

(x), wherein RS(n′

, k′

) and RS(n, k) are defined over a Galois field GF( 2^m), m being an integer, and α

is a primitive element of GF(2^m).

9. The decoder of claim 7, wherein, as a result of the index adjustment circuit, an order in which the errors in each n′

-symbol vector are output by the means for finding the locations and values of the errors is the same as an order in which symbols corresponding to the errors appear in the corresponding n′

-symbol vector.

10. A digital communications system utilizing an RS(n′

, k′

) code modified from an RS(n, k) code, wherein n, k, n′

, and k′

are integers, and k′

<

n′

<

n, k′

<

k <

n, comprising;

a channel for data transmission;

a transmitter for encoding k′

-symbol message blocks into n-symbol codewords and transmitting n′

-symbols of each codeword into the channel; and

a receiver for receiving and decoding n′

-symbol vectors each corresponding to the n′

symbols of one codeword transmitted by the transmitter, the receiver comprising

a memory device having stored therein one erasure locator polynomial σ

₀ (x) and look-up tables,

a syndrome calculator for receiving the n′

-symbol vectors and for calculating syndromes of each n′

-symbol vector, wherein the i-th syndrome S_i of one n′

-symbol vector R′

, (r<sub>n′

−

1</sub>, r<sub>n′

−

2</sub>, . . . , r₀), is S_i=R_s(α

ⁱ⁺¹) for i=0, 1, . . . , n−

k−

1, wherein R_s(x)=r<sub>n′

−

1</sub>x<sup>n′

−

1</sup>+r<sub>n′

−

2</sub>x<sup>n′

−

2</sup>+ . . . +r₀, and

means for finding the locations and values of the errors in each n′

-symbol vector using the syndromes thereof and the one erasure locator polynomial σ

₀(x).

11. The system of claim 10, wherein the encoder encodes each k′

-symbol message block by adding k−

k′

0'"'"'s to the beginning of the k′

symbols, which results in a k-symbol sequence, generating n−

k parity symbols corresponding to the resultant k-symbol sequence, which results in the corresponding n-symbol codeword including the k-symbol sequence followed by the n−

k parity symbols, and puncturing the last (n−

k)−

(n′

−

k′

) parity symbols, and wherein the n′

symbols of the corresponding codeword transmitted into the channel include the k′

symbols of the corresponding message block and the remaining n′

−

k′

parity symbols.

12. The system of claim 10, wherein the system is suitable to use any of a plurality of modified RS codes each corresponding to an erasure locator polynomial, the memory device stores the erasure locator polynomials for all of the plurality of modified RS codes, and the one erasure locator polynomial σ

₀(x) is selected from the stored erasure locator polynomials.

13. The system of claim 10, wherein the receiver further comprises means for correcting the errors in the received n′

-symbol vectors.

14. The system of claim 10, further comprising a modified syndrome calculator for calculating a modified syndrome polynomial S₀(x) based on the syndromes calculated by the syndromes calculator and the one erasure locator polynomial σ

₀(x), wherein

$S_0<br><br>\left(x\right)=S<br><br>\left(x\right)<br><br>{\mathrm{\sigma <br><br>}}_0<br><br>\left(x\right)$ $\mathrm{and}$ $S<br><br>\left(x\right)=\underset{i=0}{\overset{n-k-1}{\sum <br><br>}}<br><br>S_i<br><br>x^i.$

15. The system of claim 14, wherein the receiver further comprises a key equation solver for solving a key equation to generate an error/erasure locator polynomial σ

(x) and an error/erasure evaluator polynomial ω

(x), wherein the key equation is S₀(x)σ

₁(x)=ω

(x) mod x<sup>n−

k</sup>, and σ

(x)=σ

₀(x)σ

₁(x), and wherein σ

₁(x) is an error locator polynomial, wherein the key equation solver uses one of the look-up tables stored in the memory device.

16. The system of claim 15, wherein the key equation solver comprises a modified Euclidean algorithm processor (ME processor) including a modified Euclidean divider for computing the error/erasure evaluator polynomial ω

(x), a modified Euclidean multiplier for computing the error locator polynomial σ

₁(x), and an error/erasure locator polynomial calculator for calculating the error/erasure locator polynomial σ

(x).

17. The system of claim 15, wherein the receiver further comprises an index adjustment circuit for generating an adjusted error/erasure locator polynomial {tilde over (σ

)}(x) and an adjusted error/erasure evaluator polynomial {tilde over (ω

)}(x).

18. The system of claim 17, wherein an order in which the errors in each n′

-symbol vector are output by the means for finding the locations and values of the errors is the same as an order in which symbols corresponding to the errors appear in the corresponding n′

-symbol vector.

19. The system of claim 17, wherein the means for finding the locations and values of the errors comprises a Chien search block for evaluating the adjusted error/erasure locator polynomial {tilde over (σ

)}(x) and {tilde over (σ

)}′

(x) for x=α

⁰, α

¹, . . . , α

<sup>n′

−

1</sup>, and a Forney algorithm block for evaluating the adjusted error/erasure evaluator polynomial {tilde over (ω

)}(x) for x=α

⁰, α

¹, . . . , α

<sup>n′

−

1</sup>, wherein {tilde over (σ

)}′

(x) is a derivative of σ

(x), wherein RS(n′

, k′

) and RS(n, k) are defined over a Galois field GF(2^m), m being an integer, and α

is a primitive element of GF(2^m).

20. A method performed by a decoder for decoding an RS( n′

, k′

) code modified from an RS( n, k) code, wherein n, k, n′

, and k′

are integers, and k′

<

n′

<

n, k′

<

k <

n, the method comprising;

storing one erasure locator polynomial σ

₀(x) in a memory device in the decoder;

receiving n′

-symbol vectors each corresponding to a k′

-symbol message block; and

decoding each n′

-symbol vector R′

, (r<sub>n′

−

1</sub>, r<sub>n′

−

2</sub>, . . . , r₀), including

calculating syndromes of R′

, wherein the i-th syndrome S_i is S_i=R_s(α

ⁱ⁺¹) for i=0, 1, . . . , n−

k−

1, wherein R_s(x)=r<sub>n′

−

1</sub>x<sup>n′

−

1</sup>+r<sub>n′

−

2</sub>x<sup>n′

−

2</sup>+ . . . +r₀;

generating an adjusted error/erasure locator polynomial {tilde over (σ

)}(x) and an adjusted error/erasure evaluator polynomial {tilde over (ω

)}(x) based on the syndromes; and

finding the locations and values of errors in R′

based on the adjusted error/erasure locator polynomial {tilde over (σ

)}(x) and the adjusted error/erasure evaluator polynomial {tilde over (ω

)}(x), using a look-up table stored in the memory device.

21. The method of claim 20, wherein decoding each n′

-symbol vector further includes calculating a modified syndrome polynomial S₀(x) based on the syndromes thereof and the one erasure locator polynomial σ

₀(x), wherein

$S_0<br><br>\left(x\right)=S<br><br>\left(x\right)<br><br>{\mathrm{\sigma <br><br>}}_0<br><br>\left(x\right)<br><br><br><br>\mathrm{and}<br><br><br><br><br><br>S<br><br>\left(x\right)=\underset{i=0}{\overset{n-k-1}{\sum <br><br>}}<br><br>S_i<br><br>x^i.$

22. The method of claim 20, wherein decoding each n′

-symbol vector further includes correcting the errors in the received n′

-symbol vectors.

23. The method of claim 20, further comprising storing two additional erasure locator polynomials σ

₀(x) in the decoder such that the three stored erasure locator polynomials

${\mathrm{\sigma <br><br>}}_0<br><br>\left(x\right)$ $\mathrm{are}$ ${\mathrm{\sigma <br><br>}}_0<br><br>\left(x\right)=\underset{i=1}{\overset{s}{\prod <br><br>}}<br><br>\left(1-{\mathrm{\alpha <br><br>}}^{255-i}<br><br>x\right)=\underset{i=0}{\overset{s}{\sum <br><br>}}<br><br>{\mathrm{\sigma <br><br>}}_{0,i}<br><br>x^i,<br><br>\mathrm{for}$ $s=4,8,\mathrm{or}<br><br><br><br>12,$

wherein RS(n′

, k′

) and RS(n, k) are defined over a Galois field GF(2^m), m being an integer, and α

is a primitive element of GF(2^m), and wherein the one erasure locator polynomial σ

₀(x) is selected from the three stored erasure locator polynomials σ

₀(x).

24. The method of claim 20, wherein decoding each n′

-symbol vector further includes solving a key equation to generate an error/erasure locator polynomial σ

(x) and an error/erasure evaluator polynomial ω

(x), wherein the key equation is S₀(x)σ

₁(x)=ω

(x) mod x<sup>n−

k</sup>, and σ

(x)=σ

₀(x)σ

₁(x), and wherein σ

₁(x) is an error locator polynomial.

25. The method of claim 24, wherein decoding each n′

-symbol vector further includes adjusting indices of the error/erasure locator polynomial σ

(x) and the error/erasure evaluator polynomial ω

(x) to generate the adjusted error/erasure locator polynomial {tilde over (σ

)}(x) and the adjusted error/erasure evaluator polynomial {tilde over (ω

)}(x).

26. The method of claim 25, wherein finding the locations and values of the errors includes performing a Chien search to evaluate the adjusted error/erasure locator polynomial {tilde over (σ

)}(x) and {tilde over (σ

)}′

(x) for x=α

⁰, α

¹, . . . , α

<sup>n′

−

1</sup>, and performing a Forney algorithm to evaluate the adjusted error/erasure evaluator polynomial {tilde over (ω

)}(x) for x=α

⁰, α

¹, . . . , α

<sup>n′

−

1</sup>, wherein {tilde over (σ

)}′

(x) is a derivative of σ

(x), wherein RS(n′

, k′

) and RS(n, k) are defined over a Galois field GF(2^m), m being an integer, and α

is a primitive element of GF(2^m).

27. The method of claim 25, wherein finding the locations and values of the errors comprises finding the locations and values of the errors in an order that is the same as an order in which symbols corresponding to the errors appear in the corresponding n′

-symbol vector.