Decoder for decoding ECC using Euclid's algorithm

• US 5,517,509 A
• Filed: 03/31/1994
• Issued: 05/14/1996
• Est. Priority Date: 03/31/1993
• Status: Expired due to Term

• Current Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Original Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Inventors: Yoneda, Minoru
• Primary Examiner(s): Gordon, Paul P.
• Application Number:
  US08/220,616
• Time in Patent Office: 775 Days
• Field of Search: 371/37.1, 371/37.5, 371/43, 341/94
• US Class Current: 714/785
• CPC Class Codes: H03M 13/132 Algebraic geometric codes, e.g. Goppa codes
• CPC Class Codes: H03M 13/1535 using the Euclid algorithm

Abstract

A decoder in the form of a Euclid'"'"'s algorithm operation circuit in which division polyonomials are repeatedly divided by residues resulting from the division process of dividend polynomials and division polynomials until the degree of residues of the division process satisfies a prescribed condition. The Euclid'"'"'s algorithm operation circuit comprises register groups for storing dividend polynomials and division polynomials, respectively, a feedback loop for storing residues resulting from the division process of the dividend polynomials by the division polynomials, a shifter for shifting contents of registers, and an exchanger for exchanging coefficients of the dividend polynomials with coefficients of the division polynomials. The decoder comprises a syndrome operator for calculating syndromes from received code-words, an erasure locator generator for generating erasure locator data from erasure locator flags synchronous with received code-words, a modified syndrome generator for generating modified syndromes, an erasure locator polynomial generator for generating erasure locator polynomials from the erasure locator data, a Euclid'"'"'s algorithm operation circuit for obtaining error locator polynomials and error value polynomials, a Chien searcher for obtaining error locations and error values and a correction processor for correcting errors of the received code-word. The modified syndrome generator and the erasure locator polynomial generator are used jointly with the Euclid'"'"'s algorithm operation circuit.

Claims

1. A Euclid'"'"'s algorithm operation circuit for repeatedly dividing dividend polynomials by residues from the division of dividend polynomials and division polynomials until degrees of the residues satisfy prescribed conditions, the Euclid'"'"'s algorithm operation circuit comprising:

a first register group and a second register group each having a plurality of registers for storing the dividend polynomials and the division polynomials;

a feedback loop for storing residues resulting from the division of the dividend polynomials by the division polynomials in registers of the first register group using the first and the second register groups;

a shifter for shifting the contents of the registers of the first register group to registers in the next stage whenever one time of division is completed until the maximum degree coefficient of the division polynomials become non-zero; and

an exchanger for exchanging the coefficients of the dividend polynomials with the coefficients of the division polynomials.

2. A decoder comprising:

a syndrome operator for calculating syndromes from received code-words;

an erasure locator generator for generating erasure locator data from erasure locator flags synchronous with received code words;

a modified syndrome generator for generating modified syndromes excepting erasure locator information from the syndromes;

an erasure locator polynomial generator for generating erasure locator polynomials from the erasure locator data;

a Euclid'"'"'s algorithm operation circuit for obtaining error locator polynomials and error value polynomials from the modified syndromes and the erasure locator polynomials;

A Chien searcher for obtaining error locations and error values from the error locator polynomials and the error value polynomials obtained by the Euclid'"'"'s algorithm operation circuit; and

a correction processor for correcting errors of the received code-word based on error locations and error values obtained by the Chien searcher;

the modified syndrome generator and the erasure locator polynomial generator being used jointly with the Euclid'"'"'s algorithm operation circuit.

3. A decoder as claimed in claim 2, wherein:

the Euclid'"'"'s algorithm operation circuit includes a divider and a product sum operating circuit for Euclid'"'"'s algorithm; and

the modified syndrome generator is used jointly with the divider of the Euclid'"'"'s algorithm operation circuit and the erasure locator polynomial generator is used jointly with the product sum operating circuit for Euclid'"'"'s algorithm.

4. A decoder as claimed in claim 2, wherein:

the Euclid'"'"'s algorithm operation circuit includes a divider and a plurality of registers; and

the divider of the Euclid'"'"'s algorithm operation circuit obtains error locator polynomials by performing a division process generating coefficients of dividend polynomials until maximum degree coefficients of the dividend polynomials become non-zero while exchanging data of the registers in which the coefficients of dividend polynomials are stored for every division process and generating modified syndromes using the registers holding the coefficients of dividend polynomials.

5. A decoder as claimed in claim 2, wherein:

a product sum operating circuit for Euclid'"'"'s algorithm generates the erasure locator polynomials using resisters for multiplication.

6. A decoder comprising:

a syndrome operator for calculating syndromes from received code-words;

an erasure locator generator for generating erasure locator data from erasure locator flags synchronizing with received code-words;

a first cell group comprising a plurality of first cells connected, each of which has a first and a second registers;

a first adder and a first multiplier;

a modified syndrome generator for generating modified syndromes excepting erasure locator information from the syndromes using the first register, the first adder and the first multiplier by providing the syndromes and the erasure locator data to the first cell group and for storing them in the first register;

a Euclid'"'"'s algorithm divider for obtaining error value polynomials from the modified syndromes and the erasure locator polynomials stored in the first register using the first and the second registers, the first adder and the first multiplier;

a second cell group comprising a plurality of second cells connected, each of which has a third, a fourth and a fifth registers, a second adder and a second multiplier an erasure locator polynomial generator for providing the erasure locator data to the second cell group and generating erasure locator polynomials using the third register, the second adder and the second multiplier, and storing them in the third register;

a Euclid'"'"'s algorithm operation circuit that is provided with a quotient from the Euclid'"'"'s divider and obtains an error locator polynomial using the third, the fourth and the fifth registers, the second adder and the second multiplier from the erasure locator polynomials stored in the third register and the quotient;

a Chien searcher for obtaining error locations and error values from error value polinomials and error locator polynomials obtained by the divider and product sum operation circuit for Euclid'"'"'s algorithm, respectively; and

a correction processor for correcting the errors of received code-words based on the error locations and error values obtained by the Chien searcher.