Electronic device comprising error correction coding device and electronic device comprising error correction decoding device

• US 8,677,213 B2
• Filed: 09/16/2011
• Issued: 03/18/2014
• Est. Priority Date: 09/16/2011
• Status: Expired due to Fees

• Current Assignee: Hitachi, Ltd.
• Original Assignee: Hitachi, Ltd.
• Inventors: Mizushima, Nagamasa
• Primary Examiner(s): Tabone, Jr., John J
• Application Number:
  US13/259,743
• Publication Number:
  US 20130073925A1
• Time in Patent Office: 914 Days
• Field of Search: 714/763, 714/781, 714/782, 714/785, 714/769, 714/773, 714/774, 714/800
• US Class Current: 714/763
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: H03M 13/152 Bose-Chaudhuri-Hocquenghem [BCH] codes
• CPC Class Codes: H03M 13/1595 Parallel or block-wise remainder calculation
• CPC Class Codes: H03M 13/617 Polynomial operations, e.g. operations related to generator polynomials or parity-check polynomials
• CPC Class Codes: H03M 13/6516 Support of multiple code parameters, e.g. generalized Reed-Solomon decoder for a variety of generator polynomials or Galois fields

Abstract

An electronic device comprises an error correction coding device. The error correction coding device comprises a parity code generator. This generator is a circuit for computing a remainder polynomial by dividing a user data polynomial by a generator polynomial and generating a parity code from this remainder polynomial. This generator computes the remainder polynomial by dividing and inputting either a bit string comprising coefficients of the generator polynomial, or a bit string comprising coefficients of the generator polynomial and a bit string comprising coefficients of the generator polynomial, and dividing a minimal unit multiple times based on either a division width of the user polynomial or a division width of the user polynomial and the generator polynomial, and outputs a bit string comprising the coefficient of this remainder polynomial.

Claims

1. An electronic device comprising an error correction coding device, which comprises a parity code generator for computing a remainder polynomial by dividing a user data polynomial by a generator polynomial and generating a parity code from the remainder polynomial,

wherein the parity code generator comprises:

an input part for dividing and inputting either a first bit string comprising coefficients of the generator polynomial or the first bit string and a second bit string comprising of the user data polynomial;

a first operation part for computing the remainder polynomial by splitting a division operation into multiple division operations based on either a division width of the user data polynomial or a division width of the user data polynomial and the generator polynomial; and

a first output part for outputting a third bit string comprising coefficients of the remainder polynomial, which is a result of the division by the first operation part.

2. The electronic device according to claim 1, wherein the error correction coding device is configured to, in a BCH code (Bose Chaudhuri Hocqueghem code), which is defined using a Galois field having an element of 2^m, where m is an integer of equal to or larger than 1, and corrects t errors, where t is an integer of equal to or larger than 1, the generator polynomial is a generator polynomial of degree mt, which is determined from the parameters m and t that are required in accordance with error characteristics of a recording medium, and the error correction coding device computes a remainder polynomial of degree (mt−

1) by dividing the user data polynomial of degree (k−

1), which is generated by this generator polynomial from user data of k bits, which satisfies a following expression;

k<

2^m−

m×

t, where k is an integer of equal to or larger than 1 and generates a parity code of mt bits from coefficients of the computed remainder polynomial,

wherein the input part includes a first input part for dividing a fourth bit string comprising coefficients of the user data polynomial by W bits and inputting the divided fourth bit string, and a second input part for inputting the first bit string, and the first operation part carries out following processing;

(A) computes a partial remainder polynomial, which is a portion of the remainder polynomial for computing a portion of the remainder polynomial by using the generator polynomial to divide the inputted W-bit user data, and in a case where the partial remainder polynomial has been computed, uses this computed partial remainder polynomial when dividing the subsequently inputted W-bit user data polynomial by the generator polynomial;

(B) repeatedly executes the (A) operation k/W times, and computes k/W partial remainder polynomials;

(C) computes the remainder polynomial from the k/W partial remainder polynomials computed in the (B); and

(D) computes the parity code from the remainder polynomial computed in the (C) operation.

3. The electronic device according to claim 2, wherein the first input part divides and inputs the generator polynomial in N portions, where N is an integer of equal to or larger than 2, and

the first operation part computes k/W partial remainder polynomials by computing the (B) operation N times as one set, and further repeating this operation k/NW sets.

4. The electronic device according to claim 3, wherein the second input part divides and inputs the generator polynomial to the first operation part D bits at a time, where D=mt/NW, and

the first operation part computes k/W partial remainder polynomials by computing the (B) operation N×

D times as one set, and further repeating this operation k/NW times.

5. The electronic device according to claim 2, wherein the first operation part substantially simultaneously carries out inputting of the partial remainder polynomials used for computing the remainder polynomial, and outputting the computed partial remainder polynomials.

6. The electronic device according to claim 2, wherein the first operation part substantially simultaneously carries out inputting of the partial remainder polynomials required in computation, and inputting of the partial remainder polynomials required in computation of another computing the remainder polynomial.

7. The electronic device according to claim 2, wherein the first operation part comprises a register for storing multiple quotients, which are the results of divisions by the generator polynomial, and

the first operation part uses one of the multiple quotients stored in the register to carry out the computation of the partial remainder polynomials.

8. The electronic device according to claim 2, comprising:

an error correction decoding device, which comprises a parity code checker for correcting an error in data comprising the user data and the parity code assigned to the user data,

wherein the parity code checker comprises;

a data input part for dividing and inputting a fifth bit string of the data from outside of the electronic device;

a second operation part, which computes an intermediate syndrome value for computing a syndrome from the divided and inputted the fifth bit string;

an intermediate value output part for outputting the intermediate syndrome value to the outside of the electronic device; and

an intermediate value input part for inputting the intermediate syndrome value from the outside,

the second operation part computes the syndrome by computing another intermediate syndrome value using the computed intermediate syndrome value.

9. The electronic device according to claim 1, wherein the parity code generator comprises a first memory for storing the generator polynomial, and a second memory for storing the remainder polynomial,

the error correction coding device comprises on an outside of the parity code generator a first external memory for storing the generator polynomial, and a second external memory for storing the remainder polynomial, and

the first and second external memories are coupled to the parity code generator.

10. The electronic device according to claim 9, comprising:

a first external memory bus, which is coupled to the first external memory;

and a first switching circuit for switching an input source of the generator polynomial to the first external memory via either the first memory or the first external memory bus.

11. The electronic device according to claim 9, comprising:

a second external memory bus, which is coupled to the second external memory; and

a second switching circuit for switching an input source of the remainder polynomial to the second external memory via either the second memory or the second external memory bus.

12. The electronic device according to claim 9, comprising:

an external memory bus for inputting the generator polynomial from the first external memory, outputting the remainder polynomial to the second external memory, and inputting the remainder polynomial from the second external memory; and

a switching circuit, which carries out at least one of controls from among (a) switching the input source of the generator polynomial to either the first memory or the external memory bus, (b) switching an output destination of the remainder polynomial to either the second memory or the external memory bus, and (c) switching the input source of the remainder polynomial to either the second memory or the external memory bus.

13. An error correction coding device, which comprises a parity code generator for computing a remainder polynomial by dividing a user data polynomial by a generator polynomial, and generating a parity code from the remainder polynomial,

wherein the parity code generator comprises:

an input part for dividing and inputting either a first bit string comprising coefficients of the generator polynomial or the first bit string and a second bit string comprising coefficients of the user data polynomial; and

an operation part for computing the remainder polynomial by splitting a division operation into multiple division operations based on either a division width of the user data polynomial or a division width of the user data polynomial and the generator polynomial.