Reed-solomon coding device and method thereof

• US 6,378,104 B1
• Filed: 10/30/1997
• Issued: 04/23/2002
• Est. Priority Date: 10/30/1996
• Status: Expired due to Term

• Current Assignee: Texas Instruments, Inc.
• Original Assignee: Texas Instruments, Inc.
• Inventors: Okita, Shigeru
• Primary Examiner(s): Baker, Stephen M.
• Application Number:
  US08/960,812
• Time in Patent Office: 1,636 Days
• Field of Search: 714/784, 714/774
• US Class Current: 714/784
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/158 Finite field arithmetic processing

Abstract

To provide a type of Reed-Solomon coding device that allows a reduction of the size and price of the device. When the coding of the Galois field GF_b(2^m) is performed, in the input-side transformation circuit 116b, the Galois field of the input data is transformed from GF_b(2^m) into GF_a(2^m). In RS coding/decoding core unit 112, an operation is then performed on Galois field GF_a(2^m) to generate the coding data. In output-side transformation circuit 119b, the coding data are transformed from GF_a(2^m) into GF_b(²m). In RS coding/decoding core unit 112, a multiplier corresponding to Galois field GF_a(2^m) is set.

Claims

1. A type of Reed-Solomon coding device that can handle multiple RS (Reed-Solomon) codes using different field generation polynomials, comprising:

means for storing multiple multiplication coefficient sets corresponding to multiple code-forming polynomials;

switching means for selecting one of said coefficient sets;

a Galois field transformation means that transforms the input data to the data of a prescribed Galois field;

a coding means that performs coding processing using a selected multiplication coefficient set for the aforementioned transformed data by means of the aforementioned Galois field after transformation; and

a Galois field inverse transformation means that undertakes inverse transformation of the coded data of the aforementioned Galois field to a Galois field before transformation.

2. The Reed-Solomon coding device described in claim 1, wherein the aforementioned coding means has a multiplier corresponding to the aforementioned Galois field after transformation.

3. The Reed-Solomon coding device described in claim 1, wherein the aforementioned multiple RS codes are RS_a codes and RS_b codes using different field generation polynomials;

the coding symbols are Galois fields GF_a(2^m) and GF_b(2m) extended based on m-th order field generation polynomials GP_a(x) and GP_b(x) that are different from each other on Galois field GF(2), respectively;

for α

as the root of said Gp_a(x) and as the primitive element of said GF_a(2^m) and for β

as the root of said Gp_b(x) and as the primitive element of said GF_b(2^m), the following equation (1) is established;

said RS_b code has power of t-symbol error correction, and its code forming polynomial G_cb(x) is represented by the following equation (2);

when the aforementioned input data are coded by said RS_b code, said Galois field transformation means transforms the Galois field of the aforementioned input data from said Galois field GF_b(2^m) into said Galois field GF_a(2^m);

the aforementioned coding means performs coding corresponding to the following equation (3) as a polynomial, which transforms said code generation polynomial Gc_b(x) to said Galois field GF_a(2^m); and

the aforementioned Galois field inverse transformation means undertakes inverse transformation of the aforementioned Galois field of coded data from said Galois field GF_a(2m) into said Galois field GF_b(2^m);

4. The Reed-Solomon coding device described in claim 1, wherein

with the transposed matrix represented as ( . . . )^T, when m values among the 2m input/output relationships are as follows:

with respect to m-bit input (00 . . .

     0001)^T, m-bit output A₀=(00 . . . 00₁)^T is performed;

with respect to m-bit input (00 . . .

     0010)^T, m-bit output A₁=(A<sub>1,m−

1</sub>, A<sub>1,m−

2</sub>, . . . A_1,0)^T is performed;

with respect to m-bit input, (00 . . .

     0100)^T m-bit output A₂=(A<sub>2,m−

1</sub>, A<sub>2,m−

2</sub>, . . . A_2,0)^T is performed;

with respect to m-bit input (01 . . .

     0000)^T, m-bit output A<sub>m−

2</sub>=(A<sub>m−

2,m−

1</sub>, A<sub>m−

2,m−

2</sub>, . . . A<sub>m−

2,0</sub>)^T is performed;

with respect to m-bit input (10 . . .

     0000)^T, m-bit output A<sub>m−

1</sub>=(A<sub>m−

1,m−

1</sub>, A<sub>m−

1,m−

2</sub>, . . . A<sub>m−

1,0</sub>)^T is performed;

with m by m matrix [H_ba] being defined by the following equation (4); and

the aforementioned Galois field transformation means performs operation processing corresponding to the following equation (5) with respect to said m-bit input data D_b-in to generate m-bit output data D_a-out;

5. The Reed-Solomon coding device described in claim 4, wherein the aforementioned Galois field inverse transformation means performs operation processing corresponding to the following equation (6) to generate m-bit output data D_b-out when the inverse matrix of said matrix [H_ba] is [H_ab];

6. A type of Reed-Solomon decoding device, that can handle multiple RS codes using different field generation polynomials, comprising:

means for storing multiple multiplication coefficient sets corresponding to multiple code-forming polynomials;

switching means for selecting one of said coefficient sets;

a Galois field transformation means that transforms the input coded data into the coded dat of the prescribed Galois field;

a decoding means that performs decoding processing using a selected multiplication coefficient set of the aforementioned transformed coded data by means of the aforementioned Galois field after transformation;

and a Galois field inverse transformation means that undertakes inverse transformation of the decoded data of the aforementioned Galois field to a Galois field before transformation.

7. The Reed-Solomon decoding device described in claim 6, wherein the aforementioned Galois field transformation means has a multiplier corresponding to the aforementioned Galois field after transformation.

8. The Reed-Solomon decoding device described in claim 6, wherein the aforementioned multiple RS codes are RS_a codes and RS_b codes using different field generation polynomials;

the coding symbols are Galois fields GF_a(2^m) and GF_b(2^m) extended based on m-th order field generation polynomials Gp_a(x) and Gp_b(x), which are different from each other, on Galois field GF(2), respectively;

for α

as the root of said GP_a(x) and as the primitive element of said GF_a(2^m) and for β

as the root of said Gp_b(x) and as the primitive element of said GF_b(2^m), the following equation (7) is established;

said RS_b code has power of t-symbol error correction, and its code generation polynomial G_cb(x) is represented by the following equation (8);

when the aforementioned input coded data are decoded;

said Galois field transformation means transforms the Galois field of the aforementioned coded data from said Galois field GF_b(2^m) into said Galois field GF_a(2^m);

the aforementioned decoding means performs decoding corresponding to the following equation (9) as a polynomial that transforms said code generation polynomial G_cb(x) into said Galois field GF_a(2^m);

and the aforementioned Galois field inverse transformation means undertakes transformation of the aforementioned Galois field of decoded data from said Galois field GF_a(2^m) into said Galois field GF_b(2^m);

9. The Reed-Solomon decoding device described in claim 6 wherein with the transposed matrix represented as ( . . . )^T, when m values among the 2^m input/output relationships are as follows:

with respect to m-bit input (00 . . .

     0001)^T, m-bit output A₀=(00 . . . 00₁)^T is performed;

with respect to m-bit input (00 . . .

     0001)^T, m-bit output A₁=(A<sub>1,m−

1</sub>, A<sub>1,m−

2</sub>, . . . A_1,0)^T is performed;

with respect to m-bit input (00 . . .

     0100)^T, m-bit output A₂=(A<sub>2,m−

1</sub>, A<sub>2,m−

2</sub>, . . . A_2,0)^T is performed;

with respect to m-bit input (01 . . .

     0000)^T, m-bit output A<sub>m−

2</sub>=(A<sub>m−

2,m−

1</sub>, A<sub>m−

2, m−

2</sub>, . . . A<sub>m−

2,0</sub>)^T is performed;

with respect to m-bit input (10 . . .

     0000)^T, m-bit output A<sub>m−

1</sub>=(A<sub>m−

1,m−

1</sub>, A<sub>m−

1,m−

2</sub>, . . . A<sub>m−

1,0</sub>)^T is performed;

with m by m matrix [H_ba] being defined by following equation (10);

with the aforementioned Galois field transformation means performing operation processing corresponding to the following equation (11) with respect to said m-bit input data D_b-in to generate m-bit output data D_a-out;

10. The Reed-Solomon coding device described in claim 9, wherein the aforementioned Galois field inverse transformation means

performs operation processing corresponding to the following equation (12) to generate m-bit output data D_b-out when the inverse matrix of said matrix [H_ba] is [H_ab];

11. A Reed-Solomon coding method, comprising in a Reed-Solomon decoding method that can handle multiple RS codes using different field generation polynomials, the steps of:

input data is transformed into data of a prescribed Galois field;

for the aforementioned transformed data, coding processing is carried out by means of the aforementioned Galois field after transformation;

coded data of the aforementioned Galois field is inverse transformed into data of a Galois field before the aforementioned transformation; and

wherein the aforementioned multiple RS codes are RS_a codes and RS_b codes using different field generation polynomials;

the coding symbols are Galois fields GF_a(2^m) and GF_b(2^m) extended based on m-th order field generation polynomials Gp_a(x) and Gp_b(x) which are different from each other, on Galois field GF(2), respectively;

for α

as the root of said Gpa(x) and as the primitive element of said GF_a(2^m) and for β

as the root of said Gp_b(x) and as the primitive element of said GF_b(2^m), the following equation (13) is established;

said RS_b code has power of t-symbol error correction, and its code generation polynomial Gc_b(x) is represented by the following equation (14);

when the aforementioned input data are coded by said RS_b code,

the Galois field of the aforementioned input data is transformed from said Galois field GF_b(2^m) into said Galois field GF_a(2m);

the aforementioned coding is performed corresponding to the following equation (15) as a polynomial that transforms said code generation polynomial G_cb(x) into said Galois field GF_a(2^m); and

the aforementioned Galois field of the coded data is inverse transformed from said Galois field GF_a(2^m) into said Galois field GF_b(2^m),

12. A Reed-Solomon coding method, comprising in the Reed-Solomon decoding method that can handle multiple RS codes using different field generation polynomials, the steps of:

the input data are transformed into the data of a prescribed Galois field,

for the aforementioned transformed data, coding processing is carried out by means of the aforementioned Galois field after transformation;

the Galois field of the aforementioned coded data is inverse transformed into the Galois field before the aforementioned transformation; and

wherein with the transposed matrix represented as ( . . . )^T, when m values among the 2^m transformation relationships are as follows;

with respect to m-bit input (00 . . .

     0001)^T, m-bit output A₀=(00 . . . 00₁)^T is performed;

with respect to m-bit input (00 . . .

     0010)^T, m-bit output A₁=(A<sub>1,m−

1</sub>, A<sub>1,m−

2</sub>, . . . A_1,0^T is performed;

with respect 59 m-bit input (00 . . .

     0100)^T, m-bit output A₂(A<sub>2,m−

1</sub>, A<sub>2,m−

2</sub>, . . . A_2,0)^T is performed;

with respect to m-bit input (00 . . .

     0100)^T, m-bit output A<sub>m−

2</sub>=(A<sub>m−

2,m−

1</sub>, A<sub>m−

2,m−

2</sub>, . . . A<sub>m−

2,0</sub>)^T is performed;

with respect to m-bit input (10 . . .

     0000)^T, m-bit output A<sub>m−

1</sub>=(A<sub>m−

1,m−

1</sub>, A<sub>m−

1,m−

2</sub>, . . . A<sub>m−

1,0</sub>)^T is performed;

and m by m matrix [H_ba] is defined by the following equation (16), the aforementioned Galois field transformation of the input data is performed by carrying out operation processing corresponding to the following equation (17) with respect to said m-bit input data D_b-in to generate m-bit output data D_a-out;

 

[H_ba]=(A<sub>m−

1</sub>A<sub>m−

2</sub> . . . A₂A₁A₀) 

 

Equation 16

13. The Reed-Solomon coding method described in claim 12, wherein the aforementioned Galois field inverse transformation is performed by:

carrying out operation processing corresponding to the following equation (18) to generate m-bit output data D_b-out when the inverse matrix of said matrix [H_ba] is [H_ab];