Flexible galois field multiplier

• US 7,133,889 B2
• Filed: 10/22/2001
• Issued: 11/07/2006
• Est. Priority Date: 09/20/2001
• Status: Active Grant

• Current Assignee: STMicroelectronics Incorporated (STMicroelectronics NV)
• Original Assignee: STMicroelectronics Incorporated (STMicroelectronics NV)
• Inventors: Parthasarathy, Sivaghanam, Bartolommei, Cinzla A.
• Primary Examiner(s): MALZAHN, DAVID H
• Application Number:
  US10/032,742
• Publication Number:
  US 20030135530A1
• Time in Patent Office: 1,842 Days
• Field of Search: 708491-492
• US Class Current: 708/492
• CPC Class Codes: G06F 7/724 Finite field arithmetic for error detection or correction in general H03M13/00, in computers G06F11/10

Abstract

A flexible Galois Field multiplier is provided which implements multiplication of two elements within a finite field defined by a degree and generator polynomial. One preferred embodiment provides a method for multiplying two elements of a finite field. According to the method, two input operands are mapped into a composite finite field, an initial KOA processing is performed upon the two operands in order to prepare the two operands for a multiplication in the ground field, the multiplication in the ground field is performed through the use of a triangular basis multiplier, and final KOA3 processing and optional modulo reduction processing is performed to produce the result. This design allows rapid redefinition of the degree and generator polynomial used for the ground field and the extension field.

Claims

1. A hardware implemented Galois field multiplier comprising:

an input operand mapper for mapping two input operands into two mapped input operands in a composite finite field that is defined by a first irreducible polynomial of degree m*n, the first irreducible polynomial being defined by using a ground field that is defined by a second irreducible polynomial of degree n and by using an extension field that is defined by a third irreducible polynomial of degree m;

an initial KOA processor for performing an initial KOA processing upon the two mapped input operands to produce first result vectors;

a triangular basis ground field multiplier for performing multiplication in the ground field to produce a multiplier output; and

an output for providing the multiplier output.

2. The hardware implemented Galois field multiplier of claim 1,

wherein the initial KOA processor transforms each of the two mapped input operands that each include four sub-elements (a₀, a₁, a₂, a₃) into a respective result vector within the first result vectors that is defined by:

$\left(\begin{array}{c}{a}_0\\ a_0+a_1\\ a_1\\ a_0+a_2\\ ----\\ a_0+a_1+a_2+a_3\\ a_1+a_3\\ a_2\\ a_2+a_3\\ --------\\ a_3\\ x\\ x\\ x\end{array}\right)\hspace{1em}<br><br>$

wherein the “

+”

operator represents a bit-wise exclusive-OR operation and “

x”

indicates unused or undefined values.

3. The hardware implemented Galois field muhiplier of claim 1, further comprising a final KOA processor for performing a final KOA processing of the multiplier output, the final KOA processing being divided into a plurality of uniform subsets such that the uniform subsets are scalable for processing of different values of m used to define the extension field.

4. The hardware implemented Galois field multiplier of claim 1, wherein the first, second, and third irreducible polynomials are used-defined.

5. A hardware implemented finite field data multiplier for multiplying two elements of a finite field that correspond to two input operands, the multiplier comprising:

an input operand mapper for mapping two input operands into two mapped input operands in a composite finite field that is defined by a first irreducible polynomial of degree m*n, the first irreducible polynomial being defined by using a ground field that is defined by a second irreducible polynomial of degree n and by using an extension field that is defined by a third irreducible polynomial of degree m;

an initial KOA processor for performing an initial KOA processing upon each of the two mapped input operands to produce first result vectors, the initial KOA processor dividing the mapped input operands into a plurality of uniform subsets such that the uniform subsets are scalable for processing of different values of m used to define the extension field;

a multiplier means for performing a subsequent multiplication processing upon a result from the initial KOA processor to produce a multiplicative product over the composite finite field; and

a multiplier output for providing the multiplicative product.

6. The hardware implemented multiplier of claim 5, wherein the initial KOA processor produces a plurality of output operands that each are within the ground field.

7. The hardware implemented multiplier of claim 5, wherein the first, second, and third irreducible polynomials are used-defined.

8. A machine-readable medium encoded with a program for multiplying two elements of a finite field that correspond to two input operands, said program containing instructions for performing the steps of:

mapping two input operands into two mapped input operands in a composite finite field that is defined by a first irreducible polynomial of degree m*n, the first irreducible polynomial being defined by using a ground field that is defined by a second irreducible polynomial of degree n and by using an extension field that is defined by a third irreducible polynomial of degree m;

performing an initial KOA processing upon the two mapped input operands to produce first result vectors;

performing multiplication of the first result vectors in the ground field using a triangufar basis multiplier to produce a multiplier output; and

providing the multiplier output.

9. The machine-readable medium of claim 8, wherein the step of performing the initial KOA processing includes the sub-step of:

transforming each of the two mapped input operands that each include four sub-elements (a₀, a₁, a₂, a₃) into a respective result vector within the first result vectors that is defined by;

$\left(\begin{array}{c}{a}_0\\ a_0+a_1\\ a_1\\ a_0+a_2\\ ----\\ a_0+a_1+a_2+a_3\\ a_1+a_3\\ a_2\\ a_2+a_3\\ --------\\ a_3\\ x\\ x\\ x\end{array}\right)\hspace{1em}<br><br>$

wherein the “

+”

operator represents a bit-wise exclusive-OR operation and “

x”

indicates unused or undefined values.

10. The machine-readable medium of claim 8, wherein said program further contains instructions for performing the step of performing a final KOA processing of the multiplier output, the final KOA processing being divided into a plurality of uniform subsets such that the uniform subsets are scalable for processing of different values of m used to define the extension field.

11. A machine-readable medium encoded with a program for multiplying two elements of a finite field that correspond to two input operands, said program containing instructions for performing the steps of:

mapping two input operands into two mapped input operands in a composite finite field that is defined by a first irreducible polynomial of degree m*n, the first irreducible polynomial being defined by using a ground field that is defined by a second irreducible polynomial of degree n and by using an extension field that is defined by a third irreducible polynomial of degree m;

performing an initial KOA processing upon each of the two mapped input operands to produce first result vectors, the initial KOA processing being divided into a plurality of uniform subsets such that the uniform subsets are scalable for processing of different values of m used to define the extension field;

performing a subsequent multiplication processing upon a result of the initial KOA processing to produce a multiplicative product over the composite finite field; and

providing the multiplicative product as an output.

12. The machine-readable medium of claim 11, wherein the step of performing the initial KOA processing includes the sub-step of producing a plurality of output operands that each are within the ground field.

13. A machine-readable medium encoded with a program for performing a machine implemented meThod for multiplying two elements corresponding to a first multiplicand and a second multiplicand of a finite field, with an initial basis, that is redefinable, the method comprising the steps of:

switching data bit ordering of a plurality of data bits representing a first multiplicand to produce a first bit switched multiplicand, such that a most significant bit of the first multiplicand is placed into a least significant bit position regardless of the number of bits in the plurality of data bits representing the first multiplicand, successively less significant bits are placed into successively more significant bit positions relative to the least significant bit position, and unused bits are set to zero;

converting the first bit switched multiplicand from the initial basis into a triangular basis;

switching data bit ordering of a plurality of coefficient bits representing each of a plurality of coefficients in a Galois Field generator polynomial that defines a Galois Field over which multiplication is to be performed, such that a most significant bit of each of the coefficients is placed into a least significant bit position regardless of the number of bits in the plurality of coefficient bits, successively less significant bits are placed into successively more significant bit positions relative to the least significant bit position, and unused bits are set to zero;

performing multiplication based upon at least the first bit switched multiplicand in the triangular basis and a second multiplicand that is converted from the initial basis to the triangular basis to produce a multiplication result;

converting the multiplication result from the triangular basis to the initial basis to produce a multiplier output; and

providing the multiplier output.

14. The machine-readable medium of claim 13, wherein the step of performing multiplication includes the sub-steps of:

generating a Hankel Matrix based upon the first multiplicand and the plurality of coefficients; and

multiplying the Hankel matrix with a second multiplicand to produce the multiplication result.

15. The machine-readable medium of claim 13, wherein the step of switching data bit ordering of a plurality of data bits includes the step of selecting a plurality of outputs from a plurality of data multiplexers, the plurality of data multiplexers including one data multiplexer for each data bit in the plurality of data bits.

16. A hardware implemented flexible Galois field multiplier for multiplying two elements corresponding to a first multiplicand and a second multiplicand of a finite field, with an initial basis, that is redefinable, the multiplier comprising:

a first switching circuit for switching data bit ordering of a plurality of data bits representing a first multiplicand to produce a first bit switched multiplicand, the first switching circuit placing a most significant bit of the first multiplicand into a least significant bit position regardless of the number of bits in the plurality of data bits representing the first multiplicand, placing successively less significant bits into successively more significant bit positions relative to the least significant bit position, and setting unused bits to zero;

a first basis converter for converting the first bit switched multiplicand from an initial basis into a triangular basis;

a second switching circuit for switching data bit ordering of a plurality of coefficient bits representing each of a plurality of coefficients in a Galois Field generator polynomial that defines a Galois Field over which multiplication is to be performed, the second switching circuit placing a most significant bit of each of the coefficients into a least significant bit position regardless of the number of bits in the plurality of coefficient bits, placing successively less significant bits into successively more significant bit positions relative to the least significant bit position, and setting unused bits to zero;

a multiplier for performing multiplication based upon at least the first bit switched multiplicand in the triangular basis and a second multiplicand that is converted from the initial basis to the triangular basis to produce a multiplication result;

a second basis converter for converting the multiplication result from the triangular basis to the initial basis; and

an output for providing the multiplication result in the initial basis.

17. The hardware implemented multiplier of claim 16, wherein the multiplier generates a Hankel Matrix based upon the first multiplicand and the plurality of coefficients, and multiplies the Hankel matrix with a second multiplicand to produce the multiplication result.

18. The hardware implemented multiplier of claim 16, wherein the first switching circuit includes a plurality of data multiplexers, the plurality of data multiplexers including one data multiplexer for each data bit in the plurality of data bits.