Abstract:
A systolic product-sum calculator for computing A*B+C over multi-basis in Galois fields GF(2 m ) includes a systolic architecture comprises a plurality of basic cells arranged in m rows and m columns, at least one row of n multiplexers disposed between two pre-determined rows, n and n- 1,  and a column of stacked multiplexers. At least one selection line is used to control the multiplexers for selecting the outputs over multi-basis including at least GF(2 m ) or GF(2 n ).

Description:
FIELD OF THE INVENTION 
   This invention relates to a device for arithmetic computing over multi-basis in Galois fields GF(2 m ), and more specifically to a systolic architecture that allows the computation over multi-basis in Galois fields GF(2 m ) with a single product-sum calculator. 
   BACKGROUND OF THE INVENTION 
   Finite or Galois fields (GF) are widely used in many applications, including error-correcting codes, switching theory, and digital signal processing. For example, the Reed-Solomon (RS) error-correcting codes utilize the finite field GF(2 m ) of 2 m  elements, where m is a positive integer. These applications usually require to perform the arithmetic operations, which are different from the usual binary arithmetic operations, for the field GF(2 m ). 
   Because of their frequent computations, many hardware devices have been implemented to handle the arithmetic operations in hope to compute more efficiently. The systolic architecture, due to its simplicity and regularity, has been successfully used for such a VLSI implementation. The implementation allows simultaneous multiplication and addition operations without a look-up table for the elements of GF(2 m ). A look-up table is costly when m is large. However, the prior designs are unable to handle computations over dual-basis in Galois fields with a single calculator. An application that requires computing Galois fields over dual-basis needs two distinct product-sum calculators, and thus may double the gate count in the VLSI implementation. 
   A parallel-in, parallel-out systolic architecture for product-sum computation A*B+C in the Galois field GF(2 m ) was developed by C. -S. Yea et al. in an article titled “Systolic Multipliers for Finite Fields GF(2 m )”, pp. 357–360, VOL. C33, NO. 4, April 1984 of the IEEE Transactions on Computers. Although the proposed architecture was simple and regular enough for VLSI implementation, it can only compute over a singular basis. For applications that utilize dual-basis Galois fields, a VLSI design requires two product-sum calculators to accomplish the computation. This results in a higher gate count and a larger circuitry area, thus a higher manufacture cost. 
   SUMMARY OF THE INVENTION 
   The present invention has been made to overcome the above-mentioned drawback of the conventional systolic architecture for product-sum computation in Galois field GF(2 m ). Based on the conventional design, the present invention provides an improved systolic architecture so that applications utilizing multi-basis Galois fields can compute the arithmetic operations with a single product-sum calculator. 
   Accordingly, the systolic architecture of this invention comprises a plurality of basic cells arranged in m rows and m columns. A row of n multiplexers are disposed between two predetermined rows n and n- 1  to couple the basic cells between the two rows. A column of m multiplexers are used to select outputs for different basis of Galois fields and a selection line is used to control the multiplexers. The present invention can compute A*B+C over either GF(2 m ) or GF(2 n ), wherein 1&lt;n&lt;m. Therefore, with a single product-sum calculator, applications can perform arithmetic operations over dual-basis in Galois fields. 
   The invention can also compute A*B+C over multi-basis of Galois fields such as GF(2 m ), GF(2 n ) or GF(2 k ), where 1&lt;k&lt;n&lt;m, by disposing another row of k multiplexers between two predetermined rows k and k- 1  to couple the basic cells between the two rows. A column of m stacked multiplexers are used to select outputs for different basis of Galois fields and a plurality of selection lines are used to control the multiplexers. Consequently, with a single product-sum calculator, applications can perform arithmetic operations over multi-basis in Galois fields. 
   The present invention will become more obvious from the following description when taken in connection with the accompanying drawings which show, for purposes of illustration only, a preferred embodiment in accordance with the present invention. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
       FIG. 1  is a parallel-in, parallel-out systolic architecture for product-sum computation A*B+C in the Galois field GF(2 4 ), published by Yea, et al. 
       FIG. 2  is a diagram for a cell used in  FIG. 1 . 
       FIG. 3  is a diagram of an embodiment of the present invention for the systolic product-sum calculator over dual-basis between GF(2 4 ) and GF(2 3 ). 
       FIG. 4  is a diagram of an embodiment of the present invention for the systolic product-sum calculator over dual-basis between GF(2 m ) or GF(2 n ), where 1&lt;n&lt;m. 
       FIG. 5  is a diagram of an embodiment of the present invention for the systolic product-sum calculator over multi-basis between GF(2 m ), GF(2 n ) or GF(2 k ), where 1&lt;k&lt;n&lt;m. 
   

   DETAILED DESCRIPTION OF THE INVENTION 
   A Galois field is an algebraic field that has a finite number of elements. The number of the elements is always in the form of q m  elements, where q is a prime integer and m is a positive integer. Galois fields are widely used in error-correcting codes, switching theory, and digital signal processing. For example, the Reed-Solomon (RS) error-correcting codes utilize the Galois fields, and are used in diverse applications ranging from deep-space communication to digital audio disk systems. 
   The Galois field GF(2 m ) is an extended field of GF(2), where GF(2) is called a prime field of two elements, {0,1}. The Galois field GF(2 m ) contains 2 m  elements, {0, 1, . . . , 2 m −1}. All arithmetic operations in the prime field GF(2) is the same as arithmetic modulo 2, while arithmetic operations in the extended fields GF(2 m ) are more complicated. The nonzero elements of GF(2 m ) are generated by a primitive element α, where α is a root of a primitive irreducible polynomial f(x)=x m +f m-1 x m-1 + . . . +f 1 x+f 0  over GF(2 m ). For instance, f(x)=x 4 +x+1 and f(x)=x 3 +x+1 are primitive irreducible polynomials over GF(2 4 ) and GF(2 3 ), respectively. 
   The nonzero elements of GF(2 m ) can be represented in the power of α, i.e., GF(2 m )={0, α, α 2 , . . . , α 2     m     −2 , α 2     m     −1 } where α 2     m     −1 =1. Since α is a root of the primitive irreducible polynomial f, i.e., f(α)=0, thus α m =f m-1 α m-1 + . . . +f 1 α+f 0 , where f i ={0,1} for 0≦i≦m- 1 . Therefore, each element of GF(2 m ) can also be represented in a polynomial of α with a degree less than m, i.e., GF(2 m )={g m-1 α m-1 + . . . +g 1 α+g 0 } where g i ={0,1} for 0≦i≦m- 1 . The addition and the multiplication of any two elements of GF(2 m ) are performed as follows. 
   Assume A and B are two elements of GF(2 m ). Let A=a m-1 α m-1 + . . . +a 1 α+a 0  and B=b m-1 α m-1 + . . . +b 1 α+b 0 . Then the sum S=A+B=s m-1 α m-1 + . . . +s 1 α+s 0 , where s i =a i ⊕b i  for 0≦i≦m- 1  and ⊕ is exclusive-OR operator. Let Y=y m-1 α m-1 + . . . +y 1 α+y 0  be the product of A and B. Then: 
                   Y   =       A   ×   B     =       A   ⁢           ⁢     b   0       +       (     A   ⁢           ⁢   α     )     ⁢     b   1       +   …   +       (     A   ⁢           ⁢     α     m   -   1         )     ⁢     b     m   -   1                         =         ∑     i   =   0       m   -   1       ⁢           ⁢       (     A   ⁢           ⁢     α   i       )     ⁢     b   i         =       ∑     i   =   0       m   -   1       ⁢       (       ∑     j   =   0       m   -   1       ⁢       a   j     [   i   ]       ⁢     α   j         )     ⁢     b   i                       =       ∑     j   =   0       m   -   1       ⁢       (       ∑     i   =   0       m   -   1       ⁢       a   j     [   i   ]       ⁢     b   i         )     ⁢     α   j                       (   1   )             
 
where a j   [i]  is the coefficient of α j  in Aα i . From (1), one obtains:
 
 y   j   =a   j   [0]   b   0   +a   j   [1]   b   1   + . . . +a   j   [m-2]   b   m-2   +a   j   [m-1]   b   m-1 .
 
   Each a j[i]  for 0≦j≦m- 1  is recursively derived as follows:
 
Initially, for i=0, Aα 0 =A, i.e., a j   [0] =a j  for 0≦j≦m- 1 .   (2)
 
For 1≦i≦m- 1 , 
                     A   ⁢           ⁢     α   i       =       (     A   ⁢           ⁢     α     i   -   1         )     ⁢   α                 =         (       ∑     j   =   0       m   -   1       ⁢       a   j     [     i   -   1     ]       ⁢     α   j         )     ⁢   α     =       ∑     j   =   0       m   -   1       ⁢       a   j     [     i   -   1     ]       ⁢     α     j   +   1                         =         a     m   -   1       [     i   -   1     ]       ⁢     α   m       +       ∑     j   =   1       m   -   1       ⁢       a     j   -   1       [     i   -   1     ]       ⁢     α   j                         (   3   )             
 
Since α m =f m-1 α m-1 + . . . +f 1 α+f 0 , thus 
               A   ⁢           ⁢     α   i       =         a     m   -   1       [     i   -   1     ]       ⁢     f   0       +       ∑     j   =   1       m   -   1       ⁢       (         a     m   -   1       [     i   -   1     ]       ⁢     f   j       +     a     j   -   1       [     i   -   1     ]         )     ⁢     α   j                   (   4   )             
 
Therefore, from (4) 
               a   j     [   i   ]       =     {               a     m   -   1       [     i   -   1     ]       ⁢     f   0       ,         for         j   =   0                     a     m   -   1       [     i   -   1     ]       ⁢     f   j       +     a     j   -   1       [     i   -   1     ]         ,         for         1   ≤   j   ≤     m   -   1                       (   5   )             
 
Combining the product and sum operation described above together, one can derive P=A*B+C, where A, B, or C is an element of GF(2 m ). Therefore, the coefficient of α j  in P has the form of 
         p   j     =       (       ∑     i   =   0       m   -   1       ⁢       a   j     [   i   ]       ⁢     b   i         )     +       c   j     .           
 
     FIG. 1  shows a diagram of a prior art published by C. -S. Yea et al. It is a parallel-in, parallel-out systolic architecture for product-sum computation A*B+C in the Galois field GF(2 m ), where m=4. Elements A, B, and C are the inputs, and are of the form of {a 0 , a 1 , a 2 , a 3 }, {b 0 , b 1 , b 2 , b 3 }, and {c 0 , c 1 , c 2 , c 3 }, respectively. P is the product-sum, defined as P=A*B+C. M(u, v)  11  represents the basic cell for the arithmetic computation, and D  12  represents the delay device for the synchronization purpose. 
     FIG. 2  shows the gate-level structure diagram of the basic cell M(u, v)  11  in  FIG. 1 . Each cell computes temporary value of the product-sum function as follows:
 h — out=h — in; d — out=d — in; v — out=g — in; u — out=u — in;   e   — out=( g   — in* d   — in)⊕ e   — in; (AND gate  21 , XOR gate  22 )   g   — out=( h   — in* u   — in)⊕ v   — in. (AND gate  23 , XOR gale  24 ) 
For simplicity, the delays are neglected in present discussion. Thus the initial inputs to the cells located on the first column and the first row in the systolic architecture are:
 h — in=f j ; g — in=a j ; e — in=c j ; d — in=b i ; u — in=v — out. 
Finally, the product-sum P=A*B+C has the form {p 0 , p 1 , p 2 , p 3 }, where each p j =e — out is the output of the cell located on the rightmost column.
 
     FIG. 3  shows the embodiment of the present invention for the systolic product-sum calculator over dual-basis between GF(2 4 ) and GF(2 3 ) . For the simplicity of discussion, the delay devices  12  as shown in  FIG. 1  are temporary neglected. In the present invention, an additional row of multiplexers(MUXs)  31  are built between the first and the second rows (subscript m- 1 , and m- 2 , respectively) to control the product-sum calculator for computing A*B+C in either GF(2 3 ) or GF(2 4 ), and another column of MUXs  32  are used for selecting the output (subscript m- 1 , and m- 2 ). A “sel” line  33  is used to control these MUXs  31 ,  32 . As there are only two possibilities, i.e., m and n, a single bit is sufficient for the “sel” line  33  to determine whether the computation is in GF(2 4 ), where the behavior resembles the architecture in  FIG. 1 ; or the MUX chooses another input, thus resembling the behavior as in GF(2 3 ). 
     FIG. 4  shows an embodiment of the present invention for systolic product-sum calculator over dual-basis between GF(2 m ) or GF(2 n ), where 1&lt;n&lt;m. By placing the MUXs  41  between the rows with subscripts n and n- 1 , the present invention can choose to compute the product-sum in either GF(2 m ) or GF(2 n ), where 1&lt;n&lt;m and n is determined by the requirement of systems. Similarly, the column of the MUXs  42  are used to choose the outputs between the column with subscripts of m- 1  and n- 1 . For instance, when the “sel” line  43  is enabled, the MUXs  41  would allow the output of the row n to propagate to row n- 1 , and the MUXs  42  select the column m- 1  as the output. Therefore, the product-sum calculator behaves like computing over basis m. When the “sel” line  43  is disabled, the MUXs  41  would stop the propagation of row n to row n- 1 , and the MUXs  42  select the column n- 1  as the output, thus computing over basis n. The values assigned to the “sel” would still work vice versa. 
   The present invention could further be enhanced to allow over multi-basis arithmetic computation in GF(2 m ). By placing the MUXs between any two selected rows, and use stacked MUXs, and multiple “sel” lines, the enhanced version of the present invention can compute the designated arithmetic operations over multi-basis.  FIG. 5  illustrates a systolic architecture that can compute A*B+C over multi-basis of Galois fields such as GF(2 m ), GF(2 n ) or GF(2 k ), where 1&lt;k&lt;n&lt;m, according to the present invention. As can be seen, a row of k multiplexers are placed between two rows k and k- 1  in addition to the n multiplexers between rows n and n- 1 , and a column of stacked multiplexers are used to select outputs over multi-basis. 
   While only the preferred embodiments in accordance with the present invention are shown above, it should be clear to those skilled in the art that further embodiments may be made without departing from the scope of the present invention.