Multi-dimensional galois field multiplier

• US 6,760,742 B1
• Filed: 02/18/2000
• Issued: 07/06/2004
• Est. Priority Date: 02/18/2000
• Status: Expired due to Term

• Current Assignee: Texas Instruments, Inc.
• Original Assignee: Texas Instruments, Inc.
• Inventors: Hoyle, David
• Primary Examiner(s): Chaki, Kakali
• Assistant Examiner(s): DO, CHAT C
• Application Number:
  US09/507,187
• Time in Patent Office: 1,600 Days
• Field of Search: 708/492, 708/625, 708/653
• 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
• CPC Class Codes: H03M 13/158 Finite field arithmetic processing

Abstract

An implementation of a multi-dimensional Galois field multiplier and a method of Galois field multi-dimensional multiplication which are able to support many communication standards having various symbol sizes, different GFs, and different primitive polynomials, in a cost-efficient manner is disclosed. The key to allow a single implementation to perform for all different GF sizes is to align the input data such that the Galois field symbols of the operands are aligned to the left most significant bit (MSB) position of the input data field. Similarly, the primitive polynomial used to create a selected Galois field is aligned to the left MSB position. A polynomial multiply is performed. The product polynomial is then conditionally divided by the primitive polynomial starting with the most significant bit, the condition being if the left most bit of the product is a 1. In other words, if the product polynomial has an MSB of 1, then divide the product with the primitive polynomial. Perform this step until the MSB is 0. In addition, for fields smaller than a maximum size Galois field, the sequence of conditional divisions is further conditioned with a predetermined mask in dependence upon the size of the GF. The resultant product is aligned to the left MSB.

Claims

1. A digital system having a Galois field multiplier for multiplying using any size Galois field in the range GF(2¹) to GF(2ⁿ) and any corresponding primitive polynomial, the multiplier comprising:

an input to receive a field size indicator (m) of a selected Galois field, a multi-bit input to receive a selected primitive polynomial corresponding to the selected Galois field, and n-bit inputs to receive a first and second operand each comprising an m+1 bit Galois field symbol, wherein the Galois field symbols in the first and the second operands are aligned to the left most significant bit position (MSB) of the n-bit inputs;

n logic blocks coupled in series manner first to last, each logic block having a mask bit input, inputs to receive the primitive polynomial, inputs to receive the first operand, an input to receive a respective one bit of the second operand, intermediate inputs, and intermediate outputs for providing an intermediate result coupled to respective intermediate inputs of a next one of is the logic blocks, and an output for providing a partial product MSB;

mask circuitry connected to the field size indicator inputs and having a single different mask bit output connected to each of n logic blocks; and

a shift circuit connected to receive a last intermediate result from the last logic block, and connected to receive each partial product MSB output in rank order, with an n-bit product output for providing a Galois field product symbol right shifted in response to the field size indicator, wherein the Galois field product symbol is aligned to the left most significant bit position of the n-bit product output.

2. The multiplier of claim 1, wherein the shift circuit is operable to right shift the rank ordered partial product MSBs and the last intermediate result by an amount equal to n minus m and to zero fill least significant bits (LSB) of the n-bit product output for Galois fields smaller than GF(2ⁿ).

3. The multiplier of claim 1, wherein the each of the n logic blocks comprises:

a first logic block connected to receive the first n-bit operand and the respective one bit of the second operand and being operable to AND the one bit of the second operand with each bit of the first operand to form a partial product, wherein the MSB of the partial product is connected to the partial product MSB output;

a second logic block connected to receive the primitive polynomial and operable to AND each bit of the primitive polynomial with the mask bit and the partial product MSB to form an n-bit remainder; and

a third logic block connected to perform a bit-wise XOR on the n-bit remainder, an n-bit intermediate result from an immediately preceding logic block and n−

1 bits of the partial product to form the intermediate result.

4. The system of claim 3, further comprising a memory block coupled to the multiplier for providing the first and second n-bit operands, wherein the m-bit Galois field symbols in the first and the second operands are aligned to the left most significant bit position (MSB) of the n-bit operands.

5. The system of claim 3, wherein n=8, and wherein the memory block is a 32-bit memory block, and wherein four first operands are stored in a single 32-bit memory word, and wherein the system comprises four Galois field multipliers coupled to receive a respective one of the four first operands in a parallel manner.

6. The system of claim 3, comprising an n-bit memory region coupled to the multiplier via an n-bit data bus, wherein the primitive polynomial is stored in the memory region, wherein the primitive polynomial is aligned to the left most significant bit position of the n-bit memory region.

7. A method for performing Galois field multiplication using any size Galois field in the range GF(2¹) to GF(2_n) and any applicable primitive polynomial, comprising the steps of:

selecting a Galois field having a field size m from a range of 0 to n−

1, wherein Galois field symbols for the selected field have m+1 bits;

selecting a primitive polynomial that is valid for the selected Galois field size;

storing a first and second n-bit operand each containing a Galois field symbol in a memory region, wherein the Galois field symbols in the first and the second operands are aligned to the left most significant bit position (MSB) of the operands;

storing the primitive polynomial in a memory region such that the primitive polynomial is aligned to the left most significant bit position of the memory region;

combining the first and second operands to form n partial products, wherein each partial product has a most significant bit;

adding the n partial products together in an iterative manner to form n initial intermediate results;

selectively dividing each of the n initial intermediate results by the primitive polynomial in accordance with the field size and the most significant bit of the corresponding partial product to form a last intermediate result;

concatenating the most significant bit of each partial product in an ordered manner with the last intermediate result to form a raw product; and

right shifting the raw product by an amount determined by the field size to form a product result comprising a Galois field symbol within the selected Galois field wherein the Galois field symbol is aligned to the left most significant bit position of the product result.

8. The method of claim 7, wherein the step of combining the first and second operands comprises the steps of:

bit-wise ANDing each bit of the first operand with a most significant bit of the second operand to form a first partial product; and

repeating the step of bit-wise ANDing for each next less significant bit of the second operand to form the remaining n−

1 partial products.

9. The method of claim 8, wherein the steps of adding and dividing comprise repeating for n iteration counts the steps of:

XORing the n−

1 least significant bits of a current one of the n partial products with n−

1 most significant bits of a previous n-bit intermediate result to form an n-bit tentative intermediate, result;

XORing the tentative intermediate result with the primitive polynomial only if the MSB of the current partial product has a first value and a current iteration count is less than or equal to m to form an intermediate result;

wherein during the first iteration, the previous intermediate result is a null value; and

wherein the intermediate result of the last iteration is the last intermediate result.

10. The method of claim 7, further comprising the steps of:

receiving a continuous packed stream of Galois field symbols; and

unpacking the packed stream to form a plurality of n-bit operands by filling n−

(m+1) least significant bits of the operand with zeros.

11. A method for performing Galois field multiplication using any size Galois field in the range GF(2¹) to GF(2ⁿ) and any applicable primitive polynomial, comprising the steps of:

selecting a Galois field having a field size m from a range of 0 to n−

1, wherein Galois field symbols for the selected field have m+1 bits;

selecting a primitive polynomial that is valid for the selected Galois field size, wherein the primitive polynomial is aligned to the left most significant bit position;

combining a first and second n-bit operand each containing a Galois field symbol to form n partial products, wherein the Galois field symbols in the first and the second operands are aligned to the left most significant bit position (MSB) of the operands, and wherein each partial product has a most significant bit;

selectively dividing each of the n partial products by the primitive polynomial in accordance with the field size and the most significant bit of the corresponding partial product to form a last intermediate result;

concatenating the most significant bit of each partial product in an ordered manner with the last intermediate result to form a raw product; and

right shifting the raw product by an amount determined by the field size to form a product result comprising a Galois field symbol from the selected Galois field wherein the Galois field symbol is aligned to the left most significant bit position of the product result.

12. The method of claim 11, wherein the step of combining the first and second operands comprises the steps of:

bit-wise ANDing each bit of the first operand with a most significant bit of the second operand to form a first partial product; and

repeating the step of bit-wise ANDing for each next less significant bit of the second operand to form the remaining n−

1 partial products.

13. The method of claim 11, wherein the step of dividing comprises repeating for n iteration counts the steps of:

XORing the n−

1 least significant bits of a current one of the n partial products with n−

1 most significant bits of a previous n-bit intermediate result to form an n-bit tentative intermediate result;

XORing the tentative intermediate result with the primitive polynomial only if the MSB of the current partial product has a first value and a current iteration count is less than or equal to m to form an intermediate result;

wherein during the first iteration, the previous intermediate result is a null value; and

wherein the intermediate result of the last iteration is the last intermediate result.