Systolic Reed-Solomon decoder

• US 6,571,368 B1
• Filed: 02/02/2000
• Issued: 05/27/2003
• Est. Priority Date: 02/02/2000
• Status: Expired due to Term

• Current Assignee: Macronix International Co., Ltd.
• Original Assignee: Macronix International Co., Ltd.
• Inventors: Chen, Yen-Hao
• Primary Examiner(s): Baker, Stephen M.
• Application Number:
  US09/496,564
• Time in Patent Office: 1,210 Days
• Field of Search: 714/784, 714/785
• US Class Current: 714/784
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/1535 using the Euclid algorithm
• CPC Class Codes: H03M 13/158 Finite field arithmetic processing
• CPC Class Codes: H03M 13/159 Remainder calculation, e.g. for encoding and syndrome calculation

Abstract

The present invention includes a method and device useful for decoding a Reed-Solomon (N, K) encoded message of m-bit symbols and corresponding syndromes, where N<=2^m−1 and N−K=2t. Systolic calculation cells are used, organized to minimize complexity and computation time. Aspects of the invention include designs for syndrome calculation, division of polynomials over a Galois field, applying Euclid'"'"'s algorithm, partitioning calculation cell arrays to reduce storage requirements, complexity and computation time, and evaluating an error location and polynomial and an error evaluator polynomial.

Claims

1. A syndrome calculation device for decoding Reed-Solomon (N, K) encoded messages with m-bit symbols, where N<

=2^m−

1 and 2t=N−

K, comprising;

a serial input for a message;

a parallel output;

a set of 2t syndrome calculation cells each coupled to said serial input and said parallel output, wherein the syndrome calculation cell_j includes;

a syndrome register having an output coupled to the parallel output;

a constant multiplier for a constant α

^j, with its input coupled to the syndrome register;

an adder with its inputs coupled to the serial input and the constant multiplier;

a mux with its inputs coupled to a constant 0 and the adder and its output coupled to the syndrome register.

2. The device of claim 1, wherein the mux is responsive to a syndrome calculate signal.

3. A device to divide polynomials over a Galois Field GF(2^m) to decode a Reed-Solomon (N, K) encoded message of m-bit symbols, where N<

=2^m−

1 and N−

K=2t, comprising;

a dividend polynomial array of first cells j=2t to 0, wherein first cell_j is coupled to first cell<sub>j−

1</sub> for j=2t to 1;

a divisor polynomial array of second cells j=2t to 1, wherein first cell_j for j=2t to 2 is coupled to second cell<sub>j−

1</sub>;

a shared divider with its inputs coupled to first cell_2t and second cell_2t and its output coupled to the first cells; and

logic to calculate a quotient of first cell_2t divided by second cell_2t and a remainder polynomial equal to the dividend polynomial minus (said quotient times the divisor polynomial).

4. The device of claim 3, wherein the logic to calculate produces the quotient and the remainder in a single clock cycle.

5. The device of claim 3, wherein the first cells include only one multiplier per first cell.

6. The device of claim 3 further including a quotient polynomial array of third cells j=t to 0, wherein third cell_j for j=t to 1 is coupled to third cell_j−

1 and third cell₀ is coupled to the shared divider.

7. The device of claim 6, wherein the second and third cells do not include any multipliers.

8. A device to apply Euclid'"'"'s algorithm to decode a Reed-Solomon (N, K) encoded message of m-bit symbols and corresponding syndromes, where N<

=2^m−

1 and N−

K=2t, comprising;

a dividend polynomial array of 2t+1 first cells, wherein first cell_j is coupled to first cell<sub>j−

1</sub>;

a divisor polynomial array of 2t+1 second cells, wherein second cell_j is coupled to first cell_j and first cell_j+1, and to second cell<sub>j−

1</sub>;

an array of t+1 third cells, wherein third cell_j is coupled to first cell_j, second cell_j and third cell<sub>j−

1</sub>;

a shared divider with its inputs coupled to first cell_2t and second cell_2t and its output coupled to the first cells;

logic to calculate a quotient of first cell_2t divided by second cell_2t and a remainder polynomial of the dividend polynomial minus (said quotient times the divisor polynomial).

9. A device to apply Euclid'"'"'s algorithm to decode a Reed-Solomon (N, K) encoded message of m-bit symbols and corresponding syndromes S(x), where N<

=2^m−

1 and N−

K=2t, comprising;

an array of 2t+1 first cells, 2t+1 second cells and t+1 third cells;

a shared divider coupled to the array, to divide first cell_2t and second cell_2t and output a quotient to the first cells;

logic to partition the first cells to represent polynomials Ω

<sup>(k−

2)</sup>(x) and Λ

<sup>(k−

2)</sup>(x) and to partition the second cells to represent polynomials Ω

<sup>(k−

1)</sup>(x) and Λ

<sup>(k−

1)</sup>(x), where k is an index of iteration; and

logic to calculate Λ

^(k)(x)=Λ

<sup>(k−

2)</sup>(x)−

[Q^(k)(x){circle around (×

)}Λ

<sup>(k−

1)</sup>(x)] and Ω

^(k)(x)=Ω

<sup>(k−

2)</sup>(x)−

[Q^(k)(x){circle around (×

)}Ω

<sup>(k−

1)</sup>(x)], where Q^(k)(x)=Ω

<sup>(k−

2)</sup>(x){circle around (×

)}Ω

<sup>(k−

1)</sup>(x).

10. The device of claim 9, wherein the initial values at k=1 are Λ

<sup>(−

1)</sup>(x)=0, Λ

⁽⁰⁾(x)=1, Ω

<sup>(−

1)</sup>(x)=x^2t, and Ω

⁽⁰⁾(x)=S(x).

11. The device of claim 9, further wherein the logic to calculate iterates until the degree of the of Ω

<sup>(k−

1)</sup>(x)<

t.

12. The device of claim 9, wherein the first cells include no more than one multiplier each.

13. The device of claim 12, where the first cells include logic which exercises the multiplier only once to calculate said difference.

14. A device for decoding Reed-Solomon (N, K) encoded messages with m-bit symbols, where N<

=2^m−

1 and 2t=N−

K, comprising;

an array of first cells, logically partitioned into Ω

<sup>(i−

2)</sup> and Λ

<sup>(i−

2)</sup> cells, said first cells coupled to adjacent first cells;

an array of second cells, logically partitioned into Ω

<sup>(i−

1)</sup> and Λ

<sup>(i−

1)</sup> cells, said second cells coupled to corresponding and next higher order first cells and to adjacent second cells;

an array of third cells, said third cells coupled to the corresponding first and second cells and to adjacent third cells;

a shared divider coupled to first cells;

logic associated with the first, second and third cells to calculate a quotient q=Ω

<sup>(i−

2)</sup>/Ω

<sup>(i−

1)</sup> and a remainder of the quotient;

logic associated with the first, second and third cells to calculate Ω

⁽ⁱ⁾=Ω

<sup>(i−

2)</sup>−

Q^(k)Ω

<sup>(i−

1)</sup>; and

logic associated with the first, second and third cells to calculate Λ

⁽ⁱ⁾=Λ

<sup>(i−

2)</sup>−

Q(k)Λ

<sup>(i−

1)</sup>.

15. A device for evaluating a t-term error location polynomial and a t-term error evaluator polynomial to decode Reed-Solomon (N, K) encoded messages with m-bit symbols, where N<

=2^m−

1 and 2t=N−

K, comprising;

an array of t Ω

cells initialized with an error location polynomial;

an array of t Λ

cells initialized with an error evaluator polynomial, said array of Λ

cells including Λ

even and Λ

odd sub arrays;

a first constant factor generator coupled to the highest order cell of the Ω

array;

a second constant factor generator coupled to the highest order cell of the Λ

even and Λ

odd sub arrays;

logic to pass first constant factors values serially through the Ω

array cells and to evaluate Ω

(x) at values of x^k generated by the first constant factor generator, where k is an index of iteration; and

logic to pass second constant factors serially through both the Λ

even array and the Λ

odd array and to evaluate Λ

even(x²) and Λ

odd(x²) at values of x^2k generated by the second constant factor generator.

16. The device of claim 15, further including logic evaluate Λ

(x)=Λ

even(x²)+x Λ

odd(x²) at x^2k and, when Λ

(x)=0 to evaluate E(x)=Ω

(x)/Λ

odd(x²).

17. A device for decoding Reed-Solomon (N, K) encoded messages with m-bit symbols, where N<

=2^m−

1 and 2t=N−

K, comprising;

syndrome calculation means for calculating a syndrome polynomial of a received Reed-Solomon (N, K) encoded message;

an array of 2t+1 first cells, logically partitioned into Ω

(i−

2) and Λ

(i−

2) cells, said first coupled to adjacent first cells;

an array of second cells, logically partitioned into Ω

(i−

1) and Λ

(i−

1) cells, said second cells receiving the syndrome polynomial from the syndrome calculation means and being coupled to the corresponding and next higher order first cells and to adjacent second cells;

an array of third cells, said third cells coupled to the first and second cells and to adjacent the third cells;

a shared divider coupled to the first and third cells;

logic associated with the first, second and third cells to apply Euclid'"'"'s algorithm and generate an error location and an error value polynomial;

Chien search means for identifying elements of GF(2{circumflex over ( )}m) which are roots of the error location polynomial, coupled to the logic to generate an error location polynomial; and

error evaluation means for evaluating the error value polynomial at roots of the error location polynomial, coupled to the logic to generate an error value polynomial and to the Chien search means.