High-speed real-time Reed-Solomon decoder

A digital logic Galois Field polynomial solver which performs an operation during a clock pulse for correcting a received polynomial field element R(x), in a Galois Field in an (n, k) error correction code, wherein n is a number representing the number of unique elements in a code and k is number representing a number of elements of information in the code, comprising;

• a. first means for evaluating .OMEGA.(x), wherein .OMEGA.(x) is a polynomial
• whereby ##EQU15## represents a magnitude of an error said first means coupled within the poIynomial solver;
• b. second means for evaluating .LAMBDA.(x) where .LAMBDA.(x) is a polynomial representing a location of an error said second means coupled within the polynomial solver;
• c. third means for evaluating .LAMBDA.'(x), where .LAMBDA.'(x) is a polynomial representing a first derivative of .LAMBDA.(x);
• said third means coupled within the polynomial solver and
• d. fourth means for evaluating said polynomials for an arbitrary n in n clock pulses said fourth means coupled within the polynomial solver.

A Galois Field Euclid Algorithm apparatus for operating on an arbitrary received polynomial R(x), for calculating a magnitude polynomial, .OMEGA..sub.i (x) having a first plurality of coefficients and a location polynomial, .LAMBDA..sub.i (x), having a second plurality of coefficients, said magnitude polynomial representing a magnitude of an error in said received polynomial and said location polynomial representing a location of said error in said received polynomial for use with a code having t correctable errors, said apparatus comprising:

• a. a Euclid Algorithm divide module coupled to receive said received polynomial for implementing a first equation set forth below:
• .OMEGA..sub.i (x)=.OMEGA..sub.i-2 (x) mod .OMEGA..sub.i-1 (x);
• and
• b. a Euclid Algorithm multiply module coupled to receive said received polynomial for implementing a second equation set forth below:
• .LAMBDA..sub.i (x)=-q.sub.i (x).LAMBDA..sub.i-1 (x)+.LAMBDA..sub.i-2 (x).

A Galois Field error correction decoder comprising:

• a. means for receiving a received polynomial;
• b. means for generating a plurality of syndrome polynomials, for said received polynomial;
• c. means for calculating a magnitude polynomial and a location polynomial having a first derivative from said syndrome polynomials utilizing Euclid's Algorithm, said means for calculating including a general Galois Field multiplier comprised of combinational logic circuits;
• d. means for dividing said magnitude polynomial by said first derivative of said location polynomial comprised of means for calculating an inverse of said first derivative and multiplying said inverse by said magnitude polynomial for forming a correction polynomial;
• and
• a. means for correcting an error in said received polynomial by combining the received polynomial with the correction polynomial.

A commutative general purpose multiplier in a GF(2.sup.n) Galois Field having a plurality of sets of elements, each element having a plurality of binary bits, with each set corresponding to a polynomial p(x) having one or more terms in said Galois Field, said multiplier for multiplying a first element by a second element comprising:

• a. an n.times.n array of multiplier cells arranged in n columns of multiplier cells, each column having n multiplier cells 0 through n-1, by n rows of multiplier cells, each row having n multiplier cells 0 through n-1, the column cells 0 through n-1 corresponding to the bits of a first element and the row cells 0 through n-1 corresponding to the bits of a second element such that each ith multiplier cell in each jth column is coupled to each (i+1)th multiplier cell in the jth column and to the (i+1)th multiplier cell in the (j+1)th column;
• b. a plurality of input means, one of said input means coupled to each said multiplier cell;
• and
• c. a plurality of feedback means, one or more in each row corresponding to said terms of said polynomial p(x) coupled between each said ith cell in the jth column and the (i+1)th cell in the (j+1)th column where appropriate according to p(x), and means for receiving an input from one of said columns of said array and for providing a feedback signal to one or more multiplier cells,
• whereby a product of said multiplier is one element of said set of elements.