Methods and apparatus for single stage Galois field operations
Techniques for single function stage Galois field (GF) computations are described. The new single function stage GF multiplication requires only m-bits per internal logic stage, a savings of m−1 bits per logic stage that do not have to be accounted for as compared with a previous two function stage approach. Also, a common design GF multiplication cell is described that may be suitably used to construct an m-by-m GF multiplication array for the calculation of GF[2 m ]/g[x]. In addition, these techniques are further described in the context of packed data form computation, very long instruction word (VLIW) processing, and processing on multiple processing elements in parallel.
1. A method for Galois field (GF(2 m )) multiplication by a logic circuit, where m is a positive integer, and the GF(2 m ) multiplication operation calculates the multiplication of two polynomials producing a product which is divided by a generator polynomial, and wherein the multiplication of the two polynomials is combined with the division operation whereby the GF(2 m ) multiplication is computed as a single function GF(2 m ) multiplication operation, the method comprising:
generating x m−i polynomial coefficient terms from multiplication and division mathematical operations, where i is a variable;
combining x m−i polynomial coefficient terms having the same exponents from the multiplication and division mathematical operations to generate a recurrence relation that represents the combination of the multiplication and division operations;
computing the recurrence relation using the combined x m−i polynomial coefficient terms in the single function GF(2 m ) multiplication operation to produce a GF(2 m ) result; and
storing the GF(2 m ) result in memory in a computer readable form.
2. The method of claim 1 wherein the recurrence relation for the single GF(2 m ) multiplication function is Y(i)=Y(i−1)+(q m−i *p+Y(i−1) 2m−i *g)*x m−i , i=1, 2, . . . , m and where Y( 0 )=0, Y(i=m) is the GF(2 m ) result, p and q are coefficients of input polynomials p[x] and q[x], respectively, and g is the coefficients of a generator polynomial g[x].
3. The method of claim 1 further comprising:
computing the recurrence relation for a single GF(2 m ) multiplication function as Y(i) Y(i−1)+(q m−i *p+Y(i−1) 2m−1 *g Y(i−1) m−1 *g)*x m−i , i=1, 2, . . . , m and where Y( 0 )=0, Y(i=m) is the GF(2 m ) result, p and q are coefficients of input polynomials p[x] and q[x], respectively, and g is the coefficients of a generator polynomial g[x] in an m by m single function computation array utilizing m bits per internal calculation stage.
4. A method for Galois field (GF(2 m )) multiplication by a logic circuit, where m is a positive integer, and the GF(2 m ) multiplication operation calculates the multiplication of two polynomials producing a product which is divided by a generator polynomial, and wherein the multiplication of the two polynomials is combined with the division operation whereby the GF(2 m ) multiplication is computed as a single function GF(2 m ) multiplication operation, the method comprising:
generating x m−i polynomial coefficient terms from multiplication and division mathematical operations, where i is a variable;
combining x m−i polynomial coefficient terms having the same exponents from the multiplication and division mathematical operations to generate a recurrence relation that represents the combination of the multiplication and division operations;
computing the recurrence relation using the combined x m−i polynomial coefficient terms in the single function GF(2 m ) multiplication operation thereby calculating m by m bits for the GF(2 m ) multiplication function to produce an m bit GF(2 m ) result; and
storing the m bit GF(2 m ) result in memory in a computer readable form.
5. The method claim 4 wherein the recurrence relation for the single GF(2 m ) multiplication function is Y(i)=Y(i−1)+(q m−i *p+Y(i−1) m−1 *g)*x m−1 , i=1, 2, . . . , m and where Y( 0 )=0, Y(i=m) is the m bit GF(2 m ) result, p and q are coefficients of input polynomials p[x] and q[x], respectively, and g is the coefficients of a generator polynomial g[x].
6. The method of claim 4 wherein the step of computing the recurrence relation is accomplished in an m by m single function computation logic array utilizing m bits per internal logic stage.
7. A GF multiplication circuit cell producing result Y(i) j for iε{1, 2, . . . , m}, jε{0, 1, . . . , m−1}, where m is a positive integer, and a selected i and j value comprising:
a bit q m−i selected from the set {q m−1 , q m−2 , . . . , q m−i , . . . q 0 } of first product inputs based on the selected i value;
a bit p j selected from the set {p m−1 , p m−2 , . . . , p j , . . . , p 0 }of second product inputs based on the selected j value;
a bit g j selected from the set {g m−1 , g m−2 , . . . , g j , . . . , g 0 } of generator polynomial coefficients based on the selected j value;
a most significant bit Y(i−1) m−1 of a previous stage of GF multiplication circuit cells results;
a value of the rightmost neighbor bit Y(i−1) j−1 of a previous stage of GF multiplication circuit cell results, wherein the rightmost neighbor bit Y(i−1) j−1 is in relation to the present GF multiplication circuit cell producing result Y(i) j for the selected i and j values;
a logic device producing q m−i AND p j as output A;
a logic device producing Y(i−1) m−1 AND g j as output B; and
a logic device producing A XOR B XOR Y(i−1) j−1 as result Y(i) j to be utilized in one or more GF multiplication circuit cells or stored in a processor accessible storage unit.
8. The GF multiplication circuit cell of claim 7 disposed within an m-by-m array of interconnected GF multiplication circuit cells for producing a Galois Field (2 m ) multiplication result Y, where m is a positive integer, further comprising:
input operand q=(q m−1 q m−2 . . . q 0 );
input operand p=(p m−1 p m−2 . . . p 0 );
input operand g=(g m−1 g m−2 . . . g 0 );
the Y(i−1) m−1 and the Y(i−1) j−1 array border GF multiplication circuit cell input values set to 0; and
output Y result which is stored in a computer readable form.
9. The CF multiplication circuit cell of claim 8 wherein the m-by-m array of interconnected GF multiplication circuit cells further comprises:
the interconnections of the GF multiplication circuit cells governed by the equation
Y ( i )= Y ( i− 1)+( q m−i *p+Y ( i− 1) m−1 *g )* x m−i , i=1, 2, . . . , m and where Y (0)=0.
10. The GF multiplication circuit cell of claim 8 wherein the m-by-m array of GF multiplication circuit cells is further disposed within a grouping of multiple m-by-m arrays in a processor execution unit and further comprises:
a GF (2 m ) multiplication instruction with a data type field specifying at least one GF (2 m ) multiplication operation; and
means for connecting the multiple m-by-m arrays inputs and outputs for performing at least one GF (2 m ) multiplication in the execution of the GF (2 m ) multiplication instruction.
11. The GF multiplication circuit cell of claim 8 wherein the input operands q=(q m−1 q m−2 . . . q 0 ), p=(p m−1 p m−2 . . . p 0 ), and g=(g m−1 g m−2 . . . g 0 ) are connected to read outputs of at least one storage unit in a processor system.
12. The GF multiplication circuit cell of claim 8 wherein the output Y results are connected to at least one storage unit write inputs in a processor system.
13. The GF multiplication circuit cell of claim 11 wherein the at least one storage unit is a processor accessible register file.
14. The GF multiplication circuit cell of claim 13 wherein the at least one storage unit is a processor accessible register file.