Patent Publication Number: US-6701336-B1

Title: Shared galois field multiplier

Description:
BACKGROUND OF THE INVENTION 
     The invention relates generally to error correcting systems and, more particularly, to error correcting systems which perform Galois field multiplication during encoding and decoding processes. 
     As storage systems migrate to longer sector sizes, error correcting codes (ECC) with longer block lengths are needed. One way to achieve format efficiency is to use different field element (e.g., symbol) sizes—smaller symbols for shorter sectors and larger symbols for longer sectors. Symbols of different sizes can share some frequently used field operations. For example, addition may be performed for differently sized symbols using exclusive-OR adders. Galois field multiplication, which multiplies two elements in a Galois field, is frequently used in error correction encoding and decoding hardware, such as Reed-Solomon encoders or decoders, but requires dedicated multiplier hardware for each different symbol size. Consequently, error correction systems having one type of Galois field multiplier to accommodate a symbol/sector size are incompatible with alternative symbol/sector sizes. Some well-known field multipliers are described in Berlekamp, Algebraic Coding Theory, Academic Press, 1968, at pps. 47-48, as well as Peterson and Weldon, Error Correction Codes, 2d Edition, MIT Press, 1972, at pps. 170-182. 
     SUMMARY OF THE INVENTION 
     This invention features a Galois field multiplier that can operate on field elements of more than one size. 
     Generally, in one aspect of the invention, a Galois field multiplier includes computation circuitry for receiving an input, the computation circuitry being responsive to a control signal to perform computations based on the input having a first size to produce an output of the first size, or to perform computations based on the input having a second, different size to produce an output of the second size. 
     Embodiments of the invention may include one or more of the following features. 
     The computation circuitry can include select circuitry, responsive to the control signal, for configuring the computation circuitry. 
     In one embodiment, the input can be an element of a Galois field GF(2 m ) of a cyclic type (“cyclic Galois field”), that is, having a generator polynomial of the form x m +x m−1 +x m−2 + . . . +x+1, and the computation circuitry can further include shifting circuitry, coupled to and responsive to the select circuitry, for performing a cyclic shifting of bits of the input. 
     The first size can be 10 bits and the associated input an element of the cyclic Galois field GF(2 10 ). The second size can be 12 bits and the associated input an element of the cyclic Galois field GF(2 12 ). The shifting circuitry can further include a plurality of shifting units connected in parallel, a first one of the shifting units for receiving input values for the input and cyclically shifting the input values, each next consecutive one of the other shifting units receiving a cyclically shifted output from a previous one of the shifting units and cyclically shifting the cyclically shifted output. 
     The input can be a first input and the computation circuitry can receive a second input of the same size as the first input. The field multiplier can further include: a plurality of AND gates, each of the AND gates coupled to a value of the second input, a least significant one of the AND gates coupled to the received input values of the first input, a next most significant one of the AND gates coupled to cyclically shifted output of the first one of the shifting units, and each next most significant one of the AND gates coupled to and receiving a cyclically shifted output from the next consecutive one of the other shifting units to form product values; and a plurality of Galois field adders, one adder for each input value, each adder for receiving one of the product values for a corresponding one of the input values from each of the AND gates, for producing a set of multiplier output values of the output. 
     In another embodiment, the input can be a first input and the computation circuitry can receive a second input having the same size as the first input. The first and second inputs of the Galois field multiplier can each be elements of an extended Galois field GF((2 m ) k ) over a field GF(2 m ). In this alternative embodiment, the computation circuitry can be implemented to compute the product of the first and second inputs using the Karatsuba-Ofman algorithm and can further include a plurality of base multipliers coupled to the control line, each of the base multipliers for taking the multiplications over the field GF(2 m ). Each of the plurality of base multipliers can include base multiplier computation circuitry for receiving base multiplier inputs to produce base multiplier outputs, the base multiplier computation circuitry being adapted to respond to the control signal. 
     The shared-field multiplier of the invention offers several advantages. First, it performs the job of at least two dedicated multiplier circuits with reduced hardware complexity by exploiting common attributes of multiplication operations in different fields. Second, the shared-field multiplier allows ECC systems to satisfy different sector length requirements with flexibility and efficiency. ECC systems designed for a first symbol size may be compatible with and can therefore be upgraded to a second symbol size as sector and ECC block formats change. 
     Other features and advantages of the invention will be apparent from the following description taken together with the claims. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a schematic diagram of a single field multiplier having shifting units for cyclically shifting inputs. 
     FIG. 2 is a detailed diagram of the shifting units of FIG.  1 . 
     FIG. 3 is table depicting logic complexity and delay associated with the single field multiplier shown in FIG.  1 . 
     FIG. 4 is a shared field multiplier having shared shifting units for cyclically shifting as inputs either 10-bit or 12-bit symbols. 
     FIG. 5 is a detailed diagram of the shared shifting units of FIG.  1 . 
     FIG. 6 is table depicting logic complexity and delay associated with the shared-field multiplier shown in FIG.  4 . 
     FIG. 7 is a schematic diagram of a composite shared field multiplier. 
     FIG. 8 is a depiction of the multiplication of two GF(2 5 ) field elements. 
     FIG. 9 is a depiction of the multiplication of two GF(2 6 ) field elements. 
     FIG. 10 is a block diagram of the base multiplier shown in FIG.  7 . 
     FIGS. 11-18 illustrate in detail the various logic circuits of the base multiplier shown in FIG.  7 . 
     FIG. 19 is a schematic diagram of the constant multiplier of the shared-field multiplier shown in FIG.  7 . 
     FIGS. 20-21 are tables depicting the gate count and delay associated with the 10-bit and the 12-bit composite field multipliers, respectively. 
     FIG. 22 is a block diagram of an exemplary encoder which includes a plurality of field multipliers that may be implemented as the shared field multiplier of either FIG. 3 or FIG.  7 . 
     FIG. 23 is a block diagram of an exemplary decoder having functional units which may perform Galois field multiplication using the shared field multiplier of either FIG. 4 or FIG.  7 . 
    
    
     DETAILED DESCRIPTION 
     Referring to FIG. 1, a single field multiplier  10  designed for the Galois field GF(2 m ) is used to perform multiplication operations on field elements, such as error correction code symbols. The single field multiplier  10  receives first input values (or multiplicand) a 0  through a m    12 , at a first one of a plurality of parallel-connected consecutive shifting units (“SU”) SU 1 , SU 2 , SU 3 , . . . , (or more generally, “shifting circuitry”  14 ). The first SU, SU 1 , shifts the received input values by one place. Each subsequent, consecutive one of the shifting units  14  then shifts previously shifted input values received from a previous shifting unit by one place. A set of AND logic circuits  16  for ANDing the first input values with a second input or second input values (multiplier) b 0  through b m  are also provided. Each of the AND gates  16  is coupled to and therefore corresponds to a different value of the second input, from least significant to most significant. A first one of the AND gates  16  corresponding to the least significant second input value (b 0 ) is coupled to each of the received first input values. A next most significant one of the AND gates  16  having b 1  as input is coupled to shifted first input values as provided at the output of the first SU, SU 1 , and each next most significant one of the AND gates  16  is similarly coupled to the output of a corresponding next consecutive one of the shifting units in the shifting circuitry  14 . The results of each AND circuit  16  for each of the input values are exclusive-ORed with the results of every other AND circuit  16  for corresponding ones of the input values by XOR circuits  20  to produce output values c 0  through c m    18 . Although the multiplier is an m-bit field multiplier, for reasons which will be made apparent in the discussion to follow, it requires m+1 input/output lines (as shown). 
     The single field multipler  10  has a cyclic property, that is, it operates on a GF(2 m ) field generated by an irreducible polynomial of the form x m +x m−1 +x m−2 + . . . +x 2 +x+1. These cyclic-type fields will be referred to herein as “cyclic Galois fields”. This type of “cyclic” single field multiplier is described in a co-pending U.S. application Ser. No. 08/786,894, entitled “Modified Reed-Solomon Error Correction System Using (W+I+1)-Bit Representations of Symbols of GF(2 W+I ),” in the name of Weng et al., incorporated herein by reference. For further discussion of fields of the cyclic type, reference may be had to a paper by Jack Keil Wolf entitled, “Efficient Circuits for Multiplying in GF(2 m ) for Certain Values of m,” Discrete Mathematics 106/107, Elsevier Science Publishers B.V. 1992, at pps. 497-502. For a discussion of cyclic codes and their properties, see pages 206-268 of the above-referenced book by Peterson and Weldon. 
     Two fields which belong to the cyclic class of field multipliers are GF(2 10 ) and GF(2 12 ). The 10-bit field GF(2 10 ) can be generated by the irreducible polynomial 
     
       
           r   10 ( x )=1 +x+x   2   +x   3   +x   4   +x   5   +x   6   +x   7   +x   8   +x   9   +x   10   (1) 
       
     
     and the 12-bit field GF(2 12 ) can be generated by the irreducible polynomial 
       r   12 ( x )=1 +x+x   2   +x   3   +x   4   +x   5   +x   6   +x   7   +x   8   +x   9   +x   10   +x   11   +x   12 .  (12) 
     Every element in the field GF(2 m ) (where m=10, 12) can be represented by two m+1-bit symbols, for example, A 1 =(a 1,0 , a 1,1 ,  . . .  a m,m−1 , 0) and A 2 =(a 2,0 , a 2,1 , . . . , a 2,m−1 , 1), such that the compliment of A 1  is equal to A 2 , and vice versa. If two such elements in the field GF(2 m ) are represented as A(x)=sum(i=0, . . . , l)a i x i  and B(x)=sum(i=0, . . . , m) b i x i , then the multiplication of the elements A(x) and B(x) may be expressed as 
     
       
           A ( x ) B ( x )mod( x   m+1 +1).  (3) 
       
     
     Thus, for i=0, Eq. (3) is reduced to x 0 [a 0 +a 1 x+a 2 x 2 + . . . , +a 9 x 9 +a 10 x 10 ]*b o . For i=1, Eq. (3) becomes x[a 0 +a 1 x+a 2 x 2 + . . . +a 9 x 9 +a 10 x 10 ]*b 1  mod(x m+1 +1), which can be represented as [a 0 x+a 1 x 2 +a 2 x 3 + . . . +a 9 x 10 +a 10 x 11 ]*b 1  mod(x m+1 +1) and is equal to [a 10 +a 0 x+a 1 x 2 +a 2 x 3 + . . . +a 9 x 10 ]*b 1 . Therefore, one cyclic shift of A(x) is xA(x), or (a 10 , a 0 , a 1 , . . . , a 9 ), two cyclic shifts is x 2 A(x), or (a 9 , a 10 , a o , a 1 , . . . a 8 ), and so forth. 
     Another way of representing the product A(x)*B(x), then, is as b o A(x)+b 1 xA(x)+b 2 x 2 A(x)+ . . . +b 10 x 10 A(x). Still referring to FIG. 1, the first product term “b o A(x)” has no shifts; the second product term “b 1 xA(x)” corresponds to one shift of A(x) as performed by SU 1 ; the third product term “b 2 x 2 A(x)” corresponds to two shifts of A(x) as performed by SU 2 ; and each next term corresponds to a next higher shift number, with the final product term “b 10 x 10 A(x)” corresponding to ten shifts of A(x), as performed by SU 10 . 
     Referring to FIG. 2, the shifting circuitry  14  corresponding to each of the identical shifting units SU 1 , SU 2 , . . . , SU m−1 , SU m , is shown. The shifting circuitry  14  has shifting unit input values  22  and shifting output values  24  interconnected by cross-connect lines  26 . As can be seen from the figure, each of the inputs values a o  through a m  (where a o , a 2 , a 3 , . . . , a m  may be bits of a field element, e.g., code word symbol or polynomial coefficient) “shifts” one place to a next higher position (i.e., next MSB position), until the mth input value, which cyclically shifts to the lowest (or LSB) position. For example, the shifting unit input value a 0  is connected to the shifting unit output value a 1  (an output of the shifting unit, but an input to the subsequent shifting unit), and the shifting input value a 1  is similarly shifted to the shifting unit output value a 2 . The last shifting unit input value a m  is cyclically shifted to the shifting unit output value a o . Consequently, if the shifting unit  14  in FIG. 2 is the first unit, SU 1 , then the once shifted A(x) provided by SU 1  to SU 2  is again shifted by the second unit SU 2 . That is, the a o  and a m  values that were shifted to a 1  and a 0 , respectively, by SU 1 , are now shifted to a 2  and a 1 , respectively, by SU 2 . 
     The logic gate (XOR, AND) count and associated gate delay for both a 10-bit (m=10) and a 12-bit (m=12) implementation of the single field multiplier  10  (FIG. 1) are illustrated in FIG.  3 . For a 10-bit implementation, the total number of gates (XOR and AND gates) is 231. The associated delay is  5 . For the 12-bit implementation, the total number of gates is 325 and the associated delay is  5 . 
     Referring to FIG. 4, a shared field multiplier  30  shared by 10-bit and 12-bit fields is shown. As the shared field multiplier  30  includes many of the same components included in the single field multiplier  10  of FIG. 1, like reference numerals are used to indicate like elements. In contrast to the single field multiplier  10 , which can only be used for one particular field, the shared-field multiplier  30  is adapted for control by a control line  32 , which directs the multiplier  30  to operate on a first symbol size, e.g., 10-bits, or a second symbol size, e.g., 12-bits. The control line  32  is user-set (via, e.g., external control software, not-shown) to a predetermined position corresponding to the desired symbol size. In the present embodiment, one predetermined position selects a 10-bit symbol size and an alternate position selects a 12-bit symbol size. For each position or setting, the control line  32  controls the selection of circuitry within shared shifting units SU 1 , SU 2 , SU 3 , . . . , SU 12    34 , referred to collectively as “shared shifting circuitry”. 
     With reference to FIG. 5, each shared shifting unit  34  includes a first logic device  40  shown as a multiplexer (MUX) and a second logic device  42  shown as an AND gate. Collectively, these logic devices are referred to as select circuitry  44 . The select circuitry  44  is coupled to ones of the shared shifting unit&#39;s internal cross-connect (shifting) lines to direct the selection of shifting operations for each symbol size. Essentially, the select circuitry  44  configures the SU to either a 10-bit SU or as 12-bit SU in accordance with the control signal  32 . 
     The MUX  40  receives as inputs a 10  and a 12 , and the control line  32  as a select line. The output of the MUX  40  is connected to a o . The input a 10  is also an input to the AND gate  42 , which has as a second input the control line  32 . When the control line  32  is in a first state (position “1”, corresponding to a logic “0”, for 10-bit), a 11 -a 12  are not used and a 10 , is connected to a 0 . When the control line  32  is in a second state (position “2”, corresponding to a logic “1”, for 12-bit), the a 12  input is connected to the a o  output. The a 10  input is shifted to the a 11  output via AND gate  42 . The a 11  input is connected to the a 12  value at the output of the shared shifting unit  14 . 
     Thus, by replacing the shifting units  14  in FIG. 1 with the shared shifting units  34  controlled by the control line  32  of FIG. 4, a shared field multiplier for both fields GF(2 10 ) and GF(2 12 ) is obtained. The total gate count and delay needed for the shared-field multiplier  30  of FIG. 4 is depicted in FIG.  6 . In comparing the shared field multiplier  30  to the single 12-bit field multiplier  10 , it can be appreciated that the gate count increases by only an additional twelve AND gates and twelve multiplexers (MUX), that is, one extra AND gate and MUX for each of the SUs, and the total delay is increased by one extra MUX delay. Therefore, the total increase in gate count for the share field multiplier is no more than 9%. However, the total delay time for the shared multiplier is 20% greater than that of the single field multiplier. 
     The cyclic shared field multiplier  30  described above must be operated with 13 bits. Therefore, the entire ECC system within which such a shared-field multiplier operates has to be carried out with 13-bit symbols, increasing the overall gate count of the ECC system as a result. 
     Other embodiments are contemplated. For example, the shared multiplier may be implemented using a composite (or “extended”) field structure. Because the composite field requires 12 bits only, overall gate count is reduced from that of the cyclic implementation. However, the latency associated with the composite field implementation may be more than that of the cyclic shared-field multiplier of FIG.  4 . 
     Extended Galois fields are known and well-defined. The earlier-mentioned Peterson and Weldon book, at p. 155, defines an extension field in the following manner: “A field formed by taking polynomials over a field F modulo an irreducible polynomial p(X) of degree k is called an extension field of degree k over F.” Thus, the GF(2 5 ) field may be extended to the GF((2 5 ) 2 ) field, that is, the GF(2 10 ) field, using a polynomial p(x) of degree 2, such as x 2 +a 1 x+a 0 , which is irreducible over GF(2 5 ), such that a 1 , a 0  are elements of GF(2 5 ). Likewise, taking a primitive element α 6 =(3) 8 , the GF(2 6 ) field may be extended to GF(2 12 ) using the polynomial p(x)=x 2 +x+α 6   42 , which is irreducible over GF(2 6 ). 
     Consider A(x) and B(x) as elements of the field GF(2 10 ), where A(x)=A 1 x+A 0  and B(x)=B 1 x+B 0 , and A 1 , A 0  and B 1 , B 0  are elements of the GF(2 5 ) field. Multiplication of elements A=(A 1 , A 0 ) and B=(B 1 , B 0 ) in GF(2 10 ) can be calculated by the Karatsuba-Ofman algorithm 
     
       
           A {circle around (X)} B =( D +( A   0   *B   0 ), ( A   0   *B   0 )+( A   1   *B   1 ))  (4) 
       
     
     where A i , B i εGF(2 5 ) and D=(A 0 +A 1 )*(B 0 +B 1 ). 
     Similarly, the multiplication of two field elements A=(A 1 , A 0 ) and B=(B 1 , B 0 ) in GF(2 12 ) can be calculated by 
     
       
           A {circle around (X)} B =( D +( A   0   *B   0 ), ( A   0   *B   0 )+( A   1 *(B 1 *α 6   42 )  (5) 
       
     
     where A i , B i εGF(2 6 ) and D=(A 0 +A 1 )*(B 0 +B 1 ). Since α 6   42 =(10) 8 , then 
     
       
           B   1 *α 6   42 =( b   1,0   , . . . b   1,5 )*α 6   42 =( b   1,3   , b   1,4   , b   1,5   , b   1,3   +b   1,0   , b   1,4   +b   1,1   , b   1,5   +b   1,2 ).  (6) 
       
     
     Eq. (6) can be obtained for GF(2 6 ) using the multiplication illustrated in FIG. 9, as described below. 
     The operation of Eqs. (4) and (5) is simplified by reducing the product A(x)*B(x) modulus p(x), where p(x) is an irreducible polynomial of GF(2 m ) of degree k, and therefore may be derived in the following manner: 
     
       
           A ( x )* B ( x )= A ( x ) B ( x )mod  p ( x )=( A   1   x+A   0 )( B   1   x+B   0 )mod  p ( x )= A   1   B   1   x   2 +( s+A   1   B   1   +A   0   B   0 ) x+A   0   B   0  mod  p ( x ) 
       
     
     
       
         where  s =( A   1   +A   0 )( B   1   +B   0 )= A   1   B   1   +A   1   B   0   +A   0   B   1   +A   0   B   0   
       
     
     Letting A 0 B 0 =D 0 , A 1 B 1 =D 1 , s=D 2 , s 2 =D 1 , s 1 =D 2 +D 1 +D 0 , and s 0 =D 0 , and using p(x)=x 2 +p 1 x+p o  (where x 2  mod x 2 +p 1 x+p 0 =p 1 x+p 0 ) for GF(2 10 ) and GF(2 12 ), then 
     
       
           A ( x )* B ( x )= s   2   x   2   +s   1   x+s   0  mod  p ( x ) 
       
     
      where  p ( x )= x   2   +p   1   x+p   
     
       
           0 =( s   2   x   2   +s   1   x+s   0 )mod  x   2   +p   1   x+p   
       
     
     
       
         o =s   2   p   1   x+s   2   p   0   +s   1   x+s   
       
     
     
       
           0 =( s   2   p   1   +s   1 ) x +( s   2   p   o   +s   
       
     
     
       
           0 )=( s   2   +s   1 ) x +( s   2   +s   0 ) if GF(2 10 ) 
       
     
     
       
         where ( s   2   +s   1 )= D   1   +D   2   +D   1   +D   0   =D   2   +D   0   =C   1   
       
     
     
       
         where ( s   2   +s   0 )= D   1   +D   0   =C   
       
     
     
       
           0 =( s   2   +s   1 ) x +( s   2 α 42   +s   0 ) if GF(2 12 ) 
       
     
     
       
         where ( s   2   +s   1 )= C   1   
       
     
     
       
         where ( s   2 α 42   +s   0 )=C 0   
       
     
     
       
         where α 42  is a constant multiplier 
       
     
     Based on the composite structure property discussed above, along with the equations (4) and (5), a shared field multiplier  70  for GF(2 10 ) and GF(2 12 ) is implemented as shown in FIG.  7 . Referring to FIG. 7, the shared field multiplier  70  includes inputs (multiplicand) A 0 and A 1    72 , (multiplier) B 0  and B 1    73 , and output values (product) C 0  and C 1    74 . Further included are base multipliers  76   a ,  76   b ,  76   c  (more generally,  76 ), output adders  78   a  and  78   b , a constant multiplier  80 , a constant multiplier select  82 , input adders  83   a ,  83   b  and a control line  84 . The control line  84  is connected to each of the base multipliers  76  and the constant multiplier select  82 . The base multiplier  76   a  receives as inputs A 0 and B 0 . The base multiplier  76   b  receives as inputs A 0 +A 1  (as summed by input adder  83   a ) and B 0 +B 1  (as summed by the input adder  83   b ). The base multiplier  76   c  receives as inputs A 1  and the output of the constant multiplier select  82 , which, under the control of the control line  84 , selects the input B 1  in 10-bit mode and the output of the constant multiplier (i.e., B 1 α 42    80  in 12-bit mode). The products generated by the base multipliers  76   a  and  76   c  are exclusive-ORed by the output adder  78   b  to produce output value C 0 . The products of the base multipliers  76   a  and  76   b  are exclusive-ORed by the output adder  78   a  to produce output value C 1 . 
     The base multipliers  76  of the shared-field multiplier  70  are implemented as shared field multipliers for GF(2 5 ) and GF(2 6 ). With a 5-bit field GF(2 5 ) generated by the primitive polynomial x 5 +x 2 +1, multiplication of two field elements a=(a 0 , . . . , a 4 ) and b=(b 0 , . . . , b 4 ) can be calculated using a multiplication algorithm known as the Mastrovito algorithm, illustrated in FIG.  8 . With reference to FIG. 8, d 1   (5) =a 1 +a 4 , d 2   (5) =a 0 +a 3  and d 3 =a 2 +a 4 . For a detailed description of the Mastrovito multiplier algorithm, reference may be had to a paper by E. D. Mastrovito, entitled “VLSI Design for Multiplication Over Finite Field GF(2 m ),” Lecture Notes in Computer Science 357, pp. 297-309, Springer-Verlag, Berlin, March 1989. 
     Similarly, for the field GF(2 6 ), which can be generated with an irreducible polynomial x 6 +x 3 +1, multiplication of two field elements a=(a o , . . . , a 5 ) and b=(b 0 , . . . , b 5 ) of GF(2 6 ) can be calculated by the multiplication operation (again, using the Mastrovito multiplier algorithm) shown in FIG. 9, where d 1   (6) =a 1 +a 4 , d 2   (6) =a 0 +a 3  and d 4 =a 2 +a 5 . 
     It is apparent from the calculations illustrated in FIGS. 8 and 9 that the field multipliers for GF(2 5 ) and GF(2 6 ) share the same d 1  and d 2  terms. Therefore, d 1  can be defined by d 1 = a   1 +a 4  and d 2  defined by d 2 =a 0 +a 3  for both of the multipliers. 
     Referring to FIG. 10, the base multiplier  76 —a shared field multiplier for GF(2 5 ) and GF(2 6 )—is based on the similarity of the two multiplications presented in FIGS. 8 and 9. Each base multiplier  76  includes the set of “a” inputs  72 , the second set of “b” inputs  73 , and a set of “c” outputs  82 . Further included is a first compute circuit or “d compute logic”  86 , a second compute circuit or “e compute logic”  88  and a third compute circuitry or “c i -compute logic” (where I=0 to 5)  90 . Note that the control line  84  (from FIG. 7) is coupled to the c o  compute logic  90   a , the c 2  compute logic  90   c , the c 3  compute logic  90   d , the c 5  compute logic  90   f  and the e compute logic  88 . 
     Referring to FIG. 11, the d compute logic  86  includes adders (i.e., exclusive ORs)  100   a  through  100   d . The adder  100   a  XORs a 2  and a 5  to produce d 3   (6) . The adder  100   b  XORs a 2  and a 4  to produce d 3   (5) . The adder  100   c  XORs a 0  and a 3  to produce d 2 . The adder  100   d  XORs a 1  and a 4  to produce d 1 . 
     Referring to FIG. 12, the e compute logic  88  includes selectors  102   a ,  102   b ,  102   c  and  102   d , all coupled to the control line  84 . When the control line  84  defines the 10-bit mode, the selector  102   a  operates to select input a 2  as output e 1 , the selector  102   b  selects a 3  as e 2 , the selector  102   c  selects a 4  as e 3  and the selector  102   d  selects a 2  as e 4 . When the control line  84  selects the 12-bit mode, the selector  102   a  selects a 3  as e 3 , the selector  102   b  selects a 4  as e 2 , the selector  102   c  selects a 5  as e 3 , and the selector  102   d  selects d 3   (6)  as e 4 . 
     Referring to FIG. 13, the c o  compute logic  90   a  includes six AND gates  104   a ,  104   b ,  104   c ,  104   d ,  104   e ,  104   f , and a MUX  106 . Also included are five XOR gates  108   a ,  108   b ,  108   c ,  108   d , and  108   e . The AND gate  104   a  receives as inputs b o  and a o . The output of the AND gate  104   a  is connected to the adder  108   a , which XORs that output to the output of AND gate  104   b . The AND gate  104   b  logically ANDs inputs b 3  and e 1 . The adder  108   b  XORs the outputs of AND gates  104   c , which ANDs b 2  and e 2 , and  104   d , which ANDs b 1  and e 3 . The XOR  108   d  receives the output of the AND  104   e , which is coupled to b 5  and d 1 , as well as the output of AND gate  104   f , which receives as inputs b 4  and the output of the mux  106 . The mux  106  receives as inputs d 1  and d 3   (6) . The MUX  106  receives as a select the control line  84 . When control line  84  has the 10-bit mode selected, the mux  106  selects d 1 . In the 12-bit mode, mux  106  selects d 3   (6) . The XOR gate  108   c  XORs the outputs of the XOR gates  108   a  and  108   b . The XOR gate  108   d  XORs the outputs of AND gates  104   e  and  104   f . The XOR gate  108   e  XORs the outputs of the XOR gates  108   c  and  108   d  to produce output value c o . 
     Referring to FIG. 14, the c 1  compute logic  90   b  includes six AND gates  120   a ,  120   b ,  120   c ,  120   d ,  120   e  and  120   f . Also included are five XOR gates  122   a ,  122   b ,  122   c ,  122   d , and  122   e . The XOR gate  122   e  XORs the outputs of XORs  122   d  and  122   e  to produce c 1 . The XOR gate  122   d  XORs the outputs of the XOR gates  122   a  and  122   b . The XOR gate  122   a  XORs the outputs of AND gates  120   a  and  120   b . The AND  120   a  gate receives as inputs b 1  and a 0 . The AND gate  120   b  receives as inputs b o  and a 1 . The XOR gate  122   b  XORs the outputs of AND gates  120   c  and  120   d . The AND gate  120   c  receives as inputs b 4  and e 1 . The AND gate  120   d  receives as inputs b 3  and e 2 . The XOR gate  122   c  XORs the AND gates  120   e  and  120   f . The AND gate  120   e  is coupled to inputs b 2  and e 3 . The AND gate  120   f  is coupled to inputs b 5  and d 3   (6) . 
     Referring to FIG. 15, the c 2  compute logic  90   c  includes four MUXes  130   a ,  130   b ,  130   c  and  130   d , all coupled the control line  84 , six AND gates  132   a ,  132   b ,  132   c ,  132   d ,  132   e ,  132   f , and six XOR gates  134   a ,  134   b ,  134   c ,  134   d ,  134   e , and  134   f . The XOR gate  134   f  XORs the outputs of XOR gates  134   d  and  134   e  to produce c 2 . The XOR gate  134   e  XORs the outputs of XOR gates  134   b  and  134   c . The XOR gate  134   b  XORs the outputs of the AND gates  132   a  and  132   b . The AND gate  132  a receives as inputs b 2  and the output of the mux  130   a , controlled to generate as an output a 0  for 12-bit mode and d 2  for 10-bit mode. The AND gate  132   b  receives as inputs b 1  and the output of the mux  130   b , which is controlled to select as its output the input a 1  for 12-bit mode and the input d 1  for 10-bit mode. The AND gate  132   c  receives inputs b o  and a 2 . The AND gate  132   d  receives as inputs b 5  and a 3 . The AND gate  132   e  receives as inputs b 4  and the output of the mux  130   c , which is controlled to select input a 4  in 12-bit mode and the XOR sum produced by the XOR gate  134   b  of inputs a 3  and d 1  in 10-bit mode. The AND gate  132   f  receives as inputs b 3  and the output of the mux  130   d , which is controlled to select a 5  in 12-bit mode and d 3   (5)  in 10-bit mode. 
     Referring to FIG. 16, the c 3  compute logic  90   d  includes a mux  140 , which is coupled to and controlled by control line  84 , six AND gates  142   a ,  142   b ,  142   c ,  142   d ,  142   e ,  142   f , and five XOR gates  144   a ,  144   b ,  144   c ,  144   d  and  144   e . The XOR gate  144   e  XORs the outputs of XOR gates  144   c  and  144   d . The XOR gate  144   c  XORs the outputs of XOR gates  144   a  and  144   b . The XOR gate  144   a  XORs the outputs of the AND gates  142   a , which produces b 5 *a 1  and  142   b , which generates a product from inputs b 4  and the selected output of the mux  140 —a 2  in 10-bit mode and d 3   (5)  in 12-bit mode. The AND gate  142   c  generates the product b 0 *a 3  and the AND gate  142   d  generates the product b 1 *e 4 . The AND gate  142   e  generates the product b 3 *d 2  and the AND gate  142   f  produces the product b 2 *d 1 . 
     Referring to FIG. 17, the c 4  compute logic  90   e  includes six AND gates  150   a ,  150   b ,  150   c ,  150   d ,  150   e ,  150   e ,  150   f , and five XOR gates  152   a ,  152   b ,  152   c ,  152   d , and  152   e . The XOR gate exclusive-ORs the outputs of XOR gates  152   d  and  152   c . The XOR gate  152   d  XORs the outputs of XOR gates  152   a  and  152   b . The XOR gate  152   a  XORs the outputs of the AND gates  150   a , which has as its inputs b 5  and a 2 , and  150   b , which has for inputs b 1  and a 3 . The XOR gate  152   b , in conjunction with AND gates  150   c  and  150   d , computes b 0 *a 4 +b 2 *e 4 . The XOR gate  152   c  adds product b 4 *d 2  (from the AND gate  150   e ) and product b 3 *d 1  (from the AND gate  150   f ). 
     Referring to FIG. 18, the c 5  compute logic  90   f  includes four muxes  160   a ,  160   b ,  160   c ,  160   d , all coupled to the control line  84 , six AND gates  162   a - 162   f , as well as four XOR gates  164   a - 164   d . The XOR gate  164   e  XORs the outputs of the XOR gates  164   d  and  164   c . The XOR gate  164   d  XORs the outputs of XOR gates  164   a  and  164   b . The XOR gate  164   c  XORs the outputs of AND gates  162   e  and  162   f . The AND gate  162   e  receives as inputs b 4  and d 2 . The AND gate  162   f  ANDs inputs b 4  and the output of the mux  160   d , which selects as that output input a 5  if control line  84  selects 12-bit and input d 1  if control line  84  selects 10-bit. The XOR gate  164   a  XORs the outputs of AND gates  162   a  and  162   b , and the XOR gate  164   b  XORs the AND gates  162   c  and  162   d . The AND gate  162   a  receives as inputs b 2  and the output of the mux  160   a , which is a 5  for 10-bit symbol inputs and a 3  for 12-bit symbol inputs (as determined by control line  84 ). The AND gate  162   b  receives as inputs b 1  and the output of the mux  160   b . The  160   b  mux output is determined by control line  84  to be a 4  for 12-bit mode and a 5  for 10-bit mode. The AND gate  162   c  receives as inputs b 0  and a 5 . The AND gate  162   d  receives as inputs b 3  and the output of the mux  160   c . As with the other muxes, the output of mux  160   c  is selected by the control line  84 . In 12-bit mode, the output of mux  160   c  is d 3   (6) . In 10-bit mode, the output of mux  160   c  is a 5 . 
     The constant field multiplier  80  (from FIG. 7) is shown in detail in FIG.  19 . Referring to FIG. 19 along with Eq. (6), the constant field multiplier  80  forms the product B 1 *α 6   42  by receiving constant multiplier inputs b 1,0 , . . . b 1,5    170  and produces as outputs g o , g 1 , . . . , g 5    172 , which correspond to b 1,3 , b 1,4 , b 1,5 , b 1,3 +b 1,0 , b 1,4 +b 1,1 , b 1,5 +b 1,2 , respectively As shown, b 1,3  is XORed with b 1,0  by a first XOR  174   a , b 1,4  is XORed with b 1,1  by a second XOR  174   b , and b 1,5  is XORed with b 1,2  by a third XOR  174   c.    
     The gate count and delay for the base multiplier  76  is shown in the table of FIG.  20 . The total number of gates is 85 and the total delay is  6 . 
     The total gate count and delay for the shared field multiplier  30  (of FIG. 7) is provided in the table of FIG.  21 . The total gate count is 288 and the associated delay is  8 . In a two single field multiplier design, the gate count of the single field 10-bit multiplier is  75  AND and  95  XOR, and the gate count of the single-field 12-bit multiplier is  108  AND and  132  XOR. For a single chip design, the gate count increase for the shared-field multiplier will be 71% in comparison to a single-field 12-bit multiplier. In contrast, using the shared field multiplier shown in FIG. 7, the gate count increase is 30%, with an increase in latency of 15%. 
     The shared field multipliers  30 ,  70  of FIGS. 4 and 7, respectively, can be employed as either general or constant multipliers by conventional encoders and decoders. For example, and referring to FIG. 22, a simple, conventional encoder  200  includes constant Galois field multipliers  202  which multiply each of the coefficients of a generator polynomial G(x) by a polynomial coefficient corresponding to each code word symbol of a code word input  204 . Collectively, the multipliers  202 , along with shift register stages  206  and adders  208 , operate to produce an encoded code word output  210  from the code word input  204 . A detailed description of this type of encoder, along with alternative encoder implementations, all of which utilize field multipliers for fixed polynomial multiplication and/or division, can be found in the Peterson and Weldon book, as well as other texts. 
     In another example, and referring to FIG. 23, a conventional decoder shown as a Reed-Solomon decoder  220 , may use a combination of general and constant field multipliers, both of which may be implemented as the shared field multipliers for handling either 10-bit or 12-bit field multiplication. The conventional decoder  220  for receiving an erroneous code word and producing a corrected code word includes a syndrome computation unit  222 , an error locator polynomial generator  224 , an error location computation (or root finding) circuit  226 , and error value computation unit  228 , and an error corrector  230 . Control of each of the units is effected by a decoder control unit  232 . 
     The decoder  220  typically uses general multipliers in performing algorithms of the error locator polynomial generator  224 , or constant (fixed polynomial) field multipliers in the syndrome computation circuit  222  and error location computation circuit  226 . Examples of such decoding circuits that employ constant field multipliers are described in a U.S. application Ser. No. 09/327,285, entitled “Determining Error Locations Using Error Correction Codes”, in the name of Lih-Jyh Weng, incorporated herein by reference. Additional details of these circuits, along with general (polynomial) multiplications of the type used to generate error locator polynomials, for example, the well-known Euclidean and Berlekamp-Massey algorithms, can be found in the aforementioned book by Peterson and Weldon, as well as U.S. Pat. No. 5,107,503, issued to Riggle et al., also incorporated herein by reference, as well as many other sources. 
     Although the cyclic and composite shared field multipliers have been described with respect to a 10-bit/12-bit implementation, they may be suitably modified for use with field elements of other sizes. A cyclic shared field multiplier of the type described above could be designed for elements of other cyclic fields, e.g., 12-bit/18-bit or 18-bit/28-bit. Other values of m for cyclic Galois fields GF(2 m ) are discussed in the above-referenced Wolf paper. The composite shared field multiplier concept could be extended to other field element sizes as well, e.g., 12-bit/14-bit or 14-bit/16-bit, to name but a few combinations. Also, the shared field multiplier could conceivably be shared by more than two different field element sizes, e.g., a composite field multiplier could be designed to support three different field element sizes (such as 10-bit/12-bit/14-bit).