Single-stack implementation of a Reed-Solomon encoder/decoder

A two stage general Galois field multiplier for multiplying a first Galois field polynomial number a(x) having a form

• a(x)=a.sub.m-1 x.sup.m-1 +a.sub.m-2 x.sup.m-2 + . . . +a.sub.i x.sup.i + . . . +a.sub.1 x+a.sub.0
• by a second Galois field polynomial number a(x) having a form
• b(x)=b.sub.m-1 x.sup.m-1 +b.sub.m-2 x.sup.m-2 + . . . +b.sub.j x.sup.j + . . . +b.sub.1 x+b.sub.0
• for forming a Galois field product in a Galois field having field elements 0, .alpha..sup.0, .alpha..sup.1 through .alpha..sup.2m-2, the multiplier comprising:
• a. a plurality of multiply cells, each cell having:
• (1) six inputs including input A, input B and input I as well as the complement of each of these inputs;
• (2) two outputs including output O and its complement;
• and
• (3) logic circuit means for combining the inputs so that O=I .sym.(A.multidot.B);
• b. a first logic stage having m rows, including row j:
• j=1, . . . , m, each row having m of said cells, including cell i:
• i=m-1, . . . , 0 such that:
• (1) each cell in the jth row has a B input of b.sub.j-1 ;
• (2) the ith cell in each row has an A input of a.sub.i ;
• (3) the rows are arranged such that the output O of each cell i in a row j is coupled to the I input of the cell i-1 in the row j+1;
• and
• c. a second logic stage having m-1 rows, including row j:
• j=m+1, . . . , 2m-1, each row having m of said cells, including cell i:
• i=m-1, . . . , 0, such that:
• (1) the output O of each cell i in each row j is coupled to an I input of cell i in row j+1;
• (2) the output O of each cell except cell 0 in the row m of the first multiply stage is coupled to all the B inputs of one row in the second multiply stage such that the output O of the cell i is coupled to all the B inputs of the row m+i;
• and
• (3) the A inputs to all the cells in row m+1 are the coefficient of the Galois field element .alpha..sup.m, the A inputs to all the cells in row m+2 are the coefficients of the Galois field element .alpha..sup.m+1 and so on;
• wherein the output of the circuit is equal to
• o(x)=(a(x)b(x)) modulo p(x).

An inverse circuit for a Reed-Solomon decoder for a Galois field GF(2.sup.m), the inverse circuit for forming an inverted byte corresponding to an input byte comprising:

• a. a plurality of multiplexors, each multiplexor having a first set of 2.sup.m/2 inputs, a second set of 2.sup.m/2 inputs and an output;
• b. a first multiplexor level having m multiplexor groups, each group containing 2.sup.m/2 of said plurality of multiplexors, wherein a predetermined signal is coupled to each of the first set of inputs according to known inverse values of the Galois field, and a first set of 2.sup.m/2 byte signals is coupled to each of the second set of inputs according to a logic state of a Galois field byte being inverted;
• and
• c. a second multiplexor level having m of said plurality of multiplexors, wherein each input of the first set of inputs is coupled to receive a corresponding output from a multiplexor in the first multiplexor level and a second set of 2.sup.m/2 byte signals is coupled to each of the second set of inputs according to the logic state of the Galois field byte being inverted.