Arithmetic circuit having a simple structure for producing an error numeric value polynomial and an error locator polynomial

An arithmetic circuit for producing error locator coefficients of an error locator polynomial in accordance with Euclid's algorithm, said arithmetic circuit comprising:

• first through M-th primary register circuits for latching first through M-th primary coefficients of a first polynomial, respectively, where M represents a positive integer greater than one, said first primary coefficient being a highest coefficient of said first polynomial and said M-th primary coefficient being a lowest coefficient of said first polynomial;
• a generating circuit for generating first through M-th subsidiary coefficients of a second polynomial, said first subsidiary coefficient being a highest coefficient of said second polynomial and said M-th subsidiary coefficient being a lowest coefficient of said second polynomial, said generating circuit further generating first through N-th additional coefficients of a third polynomial, where N represents a positive integer greater than one, said first additional coefficient being a highest coefficient of said third polynomial and said N-th additional coefficient being a lowest coefficient of said third polynomial, said generating circuit still further generating first through N-th local coefficients of a fourth polynomial, said first local coefficient being a highest coefficient of said fourth polynomial and said N-th local coefficient being a lowest coefficient of said fourth polynomial;
• a divider circuit for dividing said first primary coefficient by said first subsidiary coefficient to produce an output coefficient;
• first through (M-1)-th primary multiplier circuits for multiplying said output coefficient and said second through said M-th subsidiary coefficients to produce first through (M-1)-th multiplied coefficients, respectively;
• first through (M-1)-th primary exclusive OR circuits for carrying out an exclusive OR of said second through said M-th primary coefficients and said first through (M-1)-th multiplied coefficients, respectively, to produce first through (M-1)-th exclusive ORed coefficients and to thereby set said first through said (M-1)-th exclusive ORed coefficients as said (M-1)-th through said first primary coefficients in said first through said (M-1)-th primary register circuits, respectively;
• first through N-th additional multiplier circuits for multiplying said output coefficient and said first through said N-th additional coefficients to produce first through N-th additional multiplied coefficients, respectively;
• first through N-th additional register circuits for latching said first through N-th additional multiplied coefficients, respectively;
• first through (N-1)-th additional exclusive OR circuits for carrying out an exclusive OR of said second through said N-th additional multiplied coefficients and said first through (N-1)-th additional multiplied coefficients, respectively, to produce first through (N-1)-th additional exclusive ORed coefficients and to thereby set said first through said (N-1)-th additional exclusive ORed coefficients as said first through said (N-1)-th additional multiplied coefficients in said first through said (N-1)-th additional register circuits, respectively;
• a subsidiary register circuit for latching said first additional multiplied coefficient as a subsidiary coefficient;
• first through (N-1)-th local exclusive OR circuits for carrying out an exclusive OR of said second through said N-th additional multiplied coefficients and said second through said N-th local coefficients, respectively, to produce first through (N-1)-th local exclusive ORed coefficients;
• and
• an output register circuit connected to said first through said (N-1)-th local exclusive OR circuits, said first additional register circuit, and said subsidiary register circuit for latching said first through said (N-1)-th local exclusive ORed coefficients, said first additional multiplied coefficient, and said subsidiary coefficient to produce said first through said (N-1)-th local exclusive ORed coefficients, said first additional multiplied coefficient, and said subsidiary coefficient as said error locator coefficients of said error locator polynomial.