Encoding/decoding device using a reed-solomon encoder/decoder

• US 7,404,134 B2
• Filed: 09/29/2004
• Issued: 07/22/2008
• Est. Priority Date: 09/29/2003
• Status: Expired due to Fees

• Current Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Original Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Inventors: Lehobey, Frédéric, Le Bars, Philippe, Piret, Philippe
• Primary Examiner(s): Baker; Stephen M.
• Application Number:
  US10/952,597
• Publication Number:
  US 20050138533A1
• Time in Patent Office: 1,392 Days
• Field of Search: 714/752, 714/784
• US Class Current: 714/752
• CPC Class Codes: G11B 20/18 Error detection or correction; Testing , e.g. of drop-outs
• CPC Class Codes: H03M 13/132 Algebraic geometric codes, e.g. Goppa codes
• 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/154 Error and erasure correction, e.g. by using the error and erasure locator or Forney polynomial
• CPC Class Codes: H03M 13/155 Shortening or extension of codes

Abstract

The present invention concerns a device (10) for the encoding of information symbols to transmit or to record, and for the correction of errors among the symbols received or read, according to codes defined over a Galois field F_q, where q is an integer greater than 2 and equal to a power of a prime number, and in which a set of elements of F_q are considered which are denoted y_l(j), where j=1, . . . , R with 1≦R≦q−1 and l=0, . . . , p−1 with p>1. Said device (10) comprises a Reed-Solomon encoder (210), a Reed-Solomon decoder (220) and a unit (500) serving to calculate the inverse of a Vandermonde matrix as well as:

• • registers “A” (420, 430, 440, 450) in which are stored, for the encoding, said information symbols, and, for the error correction, the symbols received or read after they have been corrected,
  • registers “S” (280, 285, 290, 295) in which are stored, for the encoding, the symbols output from said Reed-Solomon encoder (210), and, for the error correction, the symbols entering said Reed-Solomon decoder (220), and
  • registers “Y” (410, 411, 412, 413) in which said quantities y_l(j) are stored.

Claims

1. A device for the encoding of information symbols to transmit or to record, and the correcting errors among the symbols received or read, according to codes defined over a Galois field Fq, where q is an integer greater than 2 and equal to a power of a prime number, and in which a set of elements of Fq are considered which are denoted y_l(j), where j=1, . . . , R with 1≦

R≦

q−

1 and l=0, . . . , p−

1 with p>

1, said device comprising;

a Reed-Solomon encoder;

a Reed-Solomon decoder;

a unit serving to calculate the inverse of a Vandermonde matrix;

registers A in which there are stored

for the encoding, said information symbols, and

for the error correction, the symbols received or read after they have been corrected;

registers S in which there are stored

for the encoding, the symbols output from said Reed-Solomon encoder, and

for the correction of errors, the symbols input to said Reed-Solomon decoder; and

registers Y in which said quantities y_l(j) are stored.

2. A The device according to claim 1, in which said Reed-Solomon decoder is of length (q−

1), and further comprising a conversion-X table placing the indices of any register of length R opposite the respective elements of the Galois field Fq.

3. The device according to claim 1 or claim 2, in which in said registers Y the powers y_l(j)^s of the symbols y_l(j), where s=2, . . . , p−

1, are also stored.

4. The device according to claim 1 or claim 2, further comprising multiplier circuits calculating the powers y_l(j)^s of the symbols y_l(j), where s=2, . . . , p−

1, after the values of those symbols have been read in the registers Y during the post-processing steps.

5. A The device according to claim 1 or claim 2, further comprising a state machine, adapted to organize activation and deactivation of all the signals driving the encoding and error correcting operations.

6. The device according to claim 1 or claim 2, further comprising a control unit in the form of an Application Specific Integrated Circuit (ASIC) or Field Programmable Gate Array (FPGA).

7. The device according to claim 1 or claim 2, further comprising a control unit in the form of a data processing device capable of being controlled by a computer program.

8. A computer program stored in a computer-readable medium, containing instructions adapted to operate said control unit of said device according to claim 7.

9. An apparatus for sending and receiving encoded digital signals, comprising means for modulating the encoded digital signals, a modulated data transmitter, a modulated data receiver, means for demodulating the encoded digital signals, means for calculating estimated information symbols from corrected received words, and a device according to claim 1 or claim 2.

10. An apparatus for recording and reading encoded digital signals, comprising means for modulating the encoded digital signals, a modulated data recorder, a modulated data reader, means for demodulating the encoded digital signals, means for calculating estimated information symbols from corrected read words, and a device according to claim 1 or claim 2.

11. A device for encoding information symbols into a linear code, and for detecting error locations and magnitudes of encoded information symbols of the linear code, comprising:

a Reed-Solomon encoder, adapted to encode information symbols into a Reed-Solomon codes;

address conversion means for matching locations of the linear code to locations of the Reed-Solomon code; and

post-processing means for processing symbols output from said Reed-Solomon encoder,

wherein said post-processing means comprise a unit for calculating an inverse of a Vandermonde matrix.

12. The device according to claim 11, further comprising:

a Reed-Solomon decoder, adapted to decode the Reed-Solomon code;

pre-processing means for processing information symbols to be input to said Reed-Solomon encoder and encoded information symbols to be input to said Reed-Solomon decoder; and

a command unit adapted to organize activation and deactivation of signals driving the encoding, the decoding, the pre-processing and the post-processing operations.

13. The device according to claim 12, further comprising:

a first register, adapted to store the information symbols or encoded information symbols;

a second register, adapted to store the symbols output from said Reed-Solomon encoder or the symbols input to said Reed-Solomon decoder; and

a third register, adapted to store predetermined values of the first linear code.

14. The device according to any one of claims 11 to 13, wherein the linear code is an algebraic geometric code.

15. A device for encoding information symbols into a linear code, comprising:

pre-processing means for performing first operations on information symbols to be encoded and predetermined values of the linear code;

a Reed-Solomon encoder adapted to encode the pre-processed information symbols into a Reed-Solomon code and outputting encoded information symbols; and

post-processing means for performing second operations on the information symbols to be encoded, the symbols encoded by said Reed-Solomon encoder and the predetermined values of the linear code;

wherein said post-processing means comprise means for calculating an inverse of a Vandermonde matrix.

16. The device according to claim 15, further comprising:

a plurality of first registers each for storing the information symbols to be encoded;

a plurality of second registers each for storing information symbols encoded by said Reed-Solomon encoder; and

a plurality of third registers each for storing the predetermined values of the linear code.

17. The device according to claim 16, wherein said post-processing means is adapted to calculate an inverse of a Vandermonde matrix from values stored in the plurality of third registers.

18. The device according to claim 15, wherein the linear code is an algebraic geometric code.

19. A device for decoding encoded information symbols of a linear code, comprising:

pre-processing means for performing first operations on encoded information symbols to be decoded and predetermined values of the linear code;

a Reed-Solomon decoder, adapted to decode the pre-processed information symbols; and

post-processing means for performing second operations on the encoded information symbols to be decoded, the symbols decoded by said Reed-Solomon decoder, and the predetermined values of the linear code;

wherein said post-processing means comprise means for calculating an inverse of a Vandermonde matrix.

20. The device according to claim 19, wherein the linear code is an algebraic geometric code.

21. The device according to claim 19, further comprising:

a plurality of first registers each for storing encoded information symbols to be decoded;

a plurality of second registers each for storing decoded information symbols; and

a plurality of third registers each for storing predetermined values of the linear code.

22. The device according to claim 21, wherein said post-processing means is adapted to calculate an inverse of a Vandermonde matrix from values stored in sad the plurality of third registers.

23. A method for encoding information symbols into a linear code, comprising the steps of:

pre-processing the information symbols by performing first operations on the information symbols to be encoded and predetermined values of the linear code;

encoding the pre-processed information symbols into a Reed-Solomon code; and

post-processing the encoded information symbols by performing second operations on the information symbols to be encoded, the encoded information symbols, and the predetermined values of the linear code,

wherein said step of post-processing includes calculating an inverse of a Vandermonde matrix.

24. A method for decoding encoded information symbols of a linear code, comprising the steps of:

pre-processing the encoded information symbols by performing first operations on the encoded information symbols to be decoded and predetermined values of the linear code;

decoding the pre-processed symbols as a Reed-Solomon code; and

post-processing the decoded information symbols by performing second operations on the information symbols to be decoded, the decoded information symbols, and the predetermined values of the linear code,

wherein said step of post-processing includes calculating an inverse, of a Vandermonde matrix.