Nova Patents
EP0806839A1

Device and method for error correcting coding, and device and method for error correcting decoding

Abstract

Disclosed are device and method for error correcting coding for encoding an error correcting code for input data of natural number N bits per symbol, by using a Reed-Solomon code having elements on a Galois field GF(2N) having a number of elements of 2N. The ROM (14) is provided as product data storage means, after previously computes a plurality of product data on the Galois field between each of the input data and each of coefficients of a generator polynomial of the Reed-Solomon code, and the ROM (14) previously stores the plurality of product data with handling a plurality of b product data as one set for each address. The read control means (12, 13, 24 - 26, 28), in response to the input data, read out the plurality of product data stored in the ROM (14) in parallel with the plurality of b product data taken as one set, and thereafter write them selectively and sequentially into the natural number m storage units (20 - 22) via the exclusive OR computing units (15 - 18) and the bus selector (19). Input data is inputted to the ROM (14) sequentially, and then parity data are generated by the m storage units and outputted therefrom.

EP0806839A1, drawing sheet 1
Sheet 1 of 73

Term

Term ended

Projected expiry passed 2 October 2016, 10 years ago.

  1. Priority
  2. Filed
  3. Published
  4. Projected expiry
  5. Today

5 claims: 2 independent, 3 dependent

  1. 1
    A device for error correcting coding for encoding an error correcting code for input data of natural number N bits per symbol, by using a Reed-Solomon code having elements on a Galois field GF(2 N ) having a number of elements of 2 N , said device comprising:product data storage means for previously storing a plurality of product data on the Galois field between each of the input data and each of coefficients of a generator polynomial of the Reed-Solomon code, with handling a plurality of b product data as one set for each address, after previously computing the plurality of product data;first storage means comprising a natural number of m storage units each having a storage capacity of N × b bits;read control means for controlling said product data storage means to read out the plurality of product data stored in said product data storage means in parallel by handling a plurality of b product data as one set, in response to the input data;exclusive OR operation means having first and second input terminals each of N × b bits, the plurality of b product data read out in parallel from said product data storage means by said read control means being inputted to the first input terminal, said exclusive OR operation means computing exclusive OR data between data inputted to the first input terminal and data inputted to the second input terminal, and outputting resulting computation data;first selecting means for controlling said first storage means to selectively and sequentially read out and output data stored in said m storage units every one storage unit thereof, to output data of more significant N × (b-1) bits out of the selectively read out and outputted data of N × b bits, to less significant N × (b-1) bits of the second input terminal of said exclusive OR operation means, and to write the resulting computation data outputted from said exclusive OR operation means into one of said m storage units by selectively and sequentially switching said m storage units;and second storage means having a storage capacity of N bits, for temporarily storing data of the less significant N bits out of the N × b bit data selectively outputted from one of said m storage units by said first selecting means, and for outputting temporarily stored data to the more significant N bits of the second input terminal of said exclusive OR operation means,    wherein when sequentially inputting the input data into said product data storage means, said m storage unit of said first storage means generates parity data,    wherein said device further comprises: second selecting means for sequentially outputting the respective parity data generated by said m storage units by selectively and sequentially switching the m storage units every one storage unit in succession to the input data.
  2. 2
    The device for error correcting coding as claimed in Claim 1,    wherein said read control means, said first selecting means and said second selecting means are implemented by a central processing unit for executing a predetermined program stored in a further storage unit.
  3. 3
    A device for error correcting decoding for decoding an error correcting code for input data of natural number N bits per symbol, by using a Reed-Solomon code having elements on a Galois field GF(2 N ) having a number of elements of 2 N , said device comprising:received word storage means for storing an input received word comprised of a plurality of received symbols including input data and parity data associated with the input data, in a unit of the received symbols;remainder computing means comprising said device for error correcting coding as claimed in Claim 1, said remainder computing means computing and outputting a remainder for the input received word by using a generator polynomial of the Reed Solomon code;error numerical value and error position computing means for computing and outputting a set of an error position in the received word and an error numerical value corresponding to the error position, based on the remainder outputted from said remainder computing means;control means for reading out from said received word storage means and outputting a received symbol in the error position stored in said received word storage means based on the error position in the received word outputted from said error numerical value and error position computing means;exclusive OR operation means for computing exclusive OR data between the received symbol in the error position outputted from said read control means and the error numerical value corresponding to the error position outputted from said error numerical value and error position computing means, and outputting resulting computation data;and write control means for writing the resulting computation data outputted from said exclusive OR operation means into the error position in said received word storage means, and for correcting the received symbol in the error position.
  4. 4
    A method for error correcting coding for encoding an error correcting code for input data of natural number N bits per symbol, by using a Reed-Solomon code having elements on a Galois field GF(2 N ) having a number of elements of 2 N , said method including the following steps of:previously storing in product data storage means a plurality of product data on the Galois field between each of the input data and each of coefficients of a generator polynomial of the Reed-Solomon code, with handling a plurality of b product data as one set for each address, after previously computing the plurality of product data;controlling said product data storage means to read out the plurality of product data stored in said product data storage means in parallel by handling a plurality of b product data as one set, in response to the input data;by using exclusive OR operation means having first and second input terminals each of N × b bits, the plurality of b product data read out in parallel from said product data storage means by said read control means being inputted to the first input terminal, computing exclusive OR data between data inputted to the first input terminal and data inputted to the second input terminal, and outputting resulting computation data;controlling said first storage means comprising m storage unit each having a storage capacity of N x b bits, to selectively and sequentially read out and output data stored in said m storage units every one storage unit thereof, to output data of more significant N × (b-1) bits out of the selectively read out and outputted data of N × b bits, to less significant N × (b-1) bits of the second input terminal of said exclusive OR operation means, and to write the resulting computation data outputted from said exclusive OR operation means into one of said m storage units by selectively and sequentially switching said m storage units;by using second storage means having a storage capacity of N bits, temporarily storing data of the less significant N bits out of the N × b bit data selectively outputted from one of said m storage units, and outputting temporarily stored data to the more significant N bits of the second input terminal of said exclusive OR operation means;when sequentially inputting the input data into said product data storage means, generating parity data in said m storage unit of said first storage means;and sequentially outputting the respective parity data generated by said m storage units by selectively and sequentially switching the m storage units every one storage unit in succession to the input data.
  5. 5
    A method for error correcting decoding for decoding an error correcting code for input data of natural number N bits per symbol, by using a Reed-Solomon code having elements on a Galois field GF(2 N ) having a number of elements of 2 N , said method including the following steps of:storing in received word storage means an input received word comprised of a plurality of received symbols including input data and parity data associated with the input data, in a unit of the received symbols;by said method for error correcting coding as claimed in Claim 4, computing and outputting a remainder for the input received word by using a generator polynomial of the Reed Solomon code;computing and outputting a set of an error position in the received word and an error numerical value corresponding to the error position, based on the outputted remainder;reading out from said received word storage means and outputting a received symbol in the error position stored in said received word storage means based on the error position in the outputted received word;computing exclusive OR data between the received symbol in the outputted error position and the error numerical value corresponding to the outputted error position, and outputting resulting computation data;and writing the outputted resulting computation data into the error position in said received word storage means, and correcting the received symbol in the error position.
Independent claims5