GMD decoding apparatus and a method therefor

• US 5,742,620 A
• Filed: 07/19/1996
• Issued: 04/21/1998
• Est. Priority Date: 07/21/1995
• Status: Expired due to Term

• Current Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Original Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Inventors: Iwamura, Keiichi
• Primary Examiner(s): Baker, Stephen M.
• Application Number:
  US08/684,080
• Time in Patent Office: 641 Days
• Field of Search: 371/37.06, 371/37.11
• US Class Current: 714/784
• CPC Class Codes: H03M 13/151 using error location or error correction polynomials

Abstract

A decoding apparatus generates code words by means of syndrome polynomial, erasure location polynomial, and polynomials indicating error location and size thereof in order to materialize a high speed decoding with a smaller size of memory and a smaller amount of calculations. This decoding apparatus comprises an error location polynomial P_k (x) using the product of the syndrome polynomial and the erasure location polynomial as an initial value; a memory unit to store the polynomial Q_k (x) to obtain an error number and auxiliary polynomials U_k (x) and W_k (x); a calculation unit to execute a given plurality of calculations with a plurality of polynomials stored in the memory unit as input in order to output a plurality of polynomials, and a control unit to update the polynomials stored in the memory unit by the output of the calculating unit, and to decide on the input and output relations of the calculation unit in accordance with the d-2th coefficients d_k and b_k of the polynomials Q_k (x) and W_k (x).

Claims

1. A decoding apparatus comprising:

means for generating a syndrome polynomial to generate syndrome polynomials from a reception system;

means for generating an erasure location polynomial to generate erasure location polynomials in accordance with reliability of each of the symbols of said reception system;

polynomial multiplication means for multiplying the syndrome polynomial generated by said means for generating a syndrome polynomial and the erasure location polynomial generated by said means for generating an erasure location polynomial;

memory means for storing a plurality of polynomials including said polynomial having the result of multiplication of said polynomial multiplication means as the initial value;

calculating means for executing a given number of plural calculations with one or a plurality of polynomials stored in said memory means as input, and outputting a plurality of polynomials as the result of calculations;

updating means for updating the polynomials stored in said memory means by use of the output of said calculating means;

control means for deciding on the input and output relations of said calculating means in accordance with a coefficient of a given degree of a specific polynomial among the polynomials stored in said memory means;

means for generating code words to generate code words one after another by use of said reception system, said polynomials being output one after another by said calculating means, and the erasure location polynomials generated by said means for generating an erasure location polynomial; and

determination means for determining whether or not code words generated by said generating means and said reception system satisfy a given condition, and outputting the word found as satisfying said condition as the result of decoding.

2. A decoding apparatus according to claim 1, wherein said apparatus further comprises a plurality of calculation means for executing a given plurality of calculations, and each of said calculating means calculates the coefficient of each of polynomials to be output in order of degrees thereof, and said control means controls to begin the calculation of the next polynomial to be calculated in order by another calculation means when said coefficient of a given degree of said specific polynomial is calculated by one calculation means.

3. A decoding apparatus according to claim 1, wherein said control means is provided with means for storing variables to store variables, and means for updating variables to update the variables stored in said means for storing variables, and decides on the input and output relations of said calculation means in accordance with the values of said variables in addition to said coefficient of given degree.

4. A decoding apparatus according to claim 1, wherein said updating means updates a part of said variables in accordance with said coefficient of given degree.

5. A decoding method comprising the following steps of:

generating a syndrome polynomial to generate syndrome polynomials from a reception system;

generating an erasure location polynomial to generate erasure location polynomials in accordance with reliability of each of the symbols of said reception system;

multiplying the syndrome polynomial generated in said step of generating a syndrome polynomial and the erasure location polynomial generated in said step of generating an erasure location polynomial;

storing in a memory means a plurality of polynomials including the polynomial having the result of multiplication obtained in said step of polynomial multiplication as the initial value thereof;

making a given number of plural calculations with one or a plurality of polynomials stored in said memory means as input and outputting a plurality of polynomials as the result of calculations;

updating the polynomials stored in said memory means by use of the output of said calculating step;

controlling the decision on the input and output relations of said calculating step in accordance with a coefficient of a given degree of a specific polynomial among the polynomials stored in said memory means;

generating code words one after another by use of said reception system, the polynomials being output one after another in said calculating step, and the erasure location polynomial generated in said step of generating an erasure location polynomial; and

determining whether or not code words generated in said generating step and said reception system satisfy a given condition, and outputting the word found as satisfying said condition as the result of decoding.

6. A decoding method according to claim 5, wherein said method further comprises steps of using a plurality of calculation units for executing a given plurality of calculations, and of calculating the coefficient of each of polynomials to be output in order of degrees thereof in each of said calculation units, and of controlling to begin the calculation of the next polynomial to be calculated in order by another calculation unit when said coefficient of a given degree of said specific polynomial is calculated by one calculation unit.

7. A decoding method according to claim 5, wherein said method is further provided with steps of storing variables in a memory for storing variables, and of updating variables to update the variables stored in said memory for storing variables, and in said controlling step, the input and output relations of said calculation step is decided in accordance with the values of said variables in addition to said coefficient of given degree.

8. A decoding method according to claim 5, wherein a part of said variables is updated in said updating step in accordance with said coefficient of given degree.