Hardware implementation of a Galois field multiplier
An embodiment of the invention provides a method of operating a Galois field multiplier in a processor. An n bit multiplier and an n bit multiplicand are received during a first group of one or more clock cycles. An (2n−1) bit product is calculated based on the n bit multiplicand and the n bit multiplier. The (2n−1) bit product is stored in a first memory element during the first group of one or more clock cycles. An n bit polynomial value is received during a second group of one or more clock cycles. During the second group of one or more clock cycles, the (2n−1) bit product is divided by the n bit polynomial value producing an n bit result. The n bit result is stored in a second memory element during the second group of one or more clock cycles.
1. A method of operating a Galois field multiplier in a processor, the method comprising the steps of:
receiving a k bit multiplier operand and an n bit multiplicand operand, during a first group of one or more clock cycles wherein n is greater than k;
calculating a (n+k−1) bit product based on the k bit multiplier operand and the n bit multiplicand operand during the first group of one or more clock cycles;
storing the (n+k−1) bit product in a first memory element during the first group of one or more clock cycles;
receiving an n bit polynomial value during a second group of one or more clock cycles, the second group following in time after the first group;
dividing the (n+k−1) bit product by the n bit polynomial value during the second group of one or more clock cycles;
storing an n bit result of dividing the (n+k−1) product by the n bit polynomial value in a second memory element during the second group of one or more clock cycles.
2. The method of claim 1 wherein calculating the (n+k−1) bit product based on the k-bit multiplier operand and the n bit multiplicand operand during the first group of one or more clock cycles comprises:
producing n bit partial products; and
reducing the n bit partial products to the (n+k−1) bit product using a logarithmic XOR reduction.
3. The method of claim 2 wherein producing n bit partial products comprises:
ANDing the k-bit multiplier operand and the n bit multiplicand operand.
4. The method of claim 1 wherein dividing the (n+k−1) bit product by the n bit polynomial value comprises:
performing n−1 division steps, the first division step comprising:
ANDing the most significant bit (MSB) of the (n+k−1) product with the n bit polynomial value generating an n bit first intermediate output; and
XORing the n bit first intermediate output with the n bits of the product that immediately follow the MSB of the product generating an output;
wherein each of the n−1 division steps following the first division step comprise:
ANDing a most significant bit (MSB) of the output of the previous step with the n bit polynomial value generating an n bit second intermediate output;
XORing the n bit second intermediate output with the n−1 least significant (LSB) bits from the output of the previous step and a bit from the (n+k−1) product.
5. The method of claim 4 wherein each of the n−1 division steps may be performed in one or more clock cycles.
6. A Galois field multiplier comprising:
a first plurality of AND gates for generating partial products from a k bit multiplier and an n bit multiplicand during a first group of one or more clock cycles wherein n is greater than k;
a first plurality of XOR gates for logarithmically reducing the partial products to a (n+k−1) product during the first group of one or more clock cycles;
a first memory element for storing the (n+k−1) product during the first group of one or more clock cycles;
a second plurality of AND gates and a second plurality XOR gates for dividing the (n+k−1) product by an n bit polynomial value during a second group of one or more clock cycles, the second group following in time after the first group;
storing an n bit result of dividing the (n+k−1) product by the n bit polynomial value in a second memory element during the second group of one or more clock cycles.
7. The Galois field multiplier of claim 6 wherein the first plurality of AND gates are two-input AND gates, the first plurality of XOR gates are two-input XOR gates, the second plurality of AND gates are two-input AND gates, and the second plurality of two-input XOR gates.
8. The Galois field multiplier of claim 7 wherein a longest delay path through the first plurality of XOR gates is approximately equal to:
(log 2 n)*d 2XOR ;
wherein d 2XOR is approximately equal to the delay through a two-input XOR gate.
9. The Galois field multiplier of claim 7 wherein a longest delay path through the second plurality of XOR gates and the second plurality of AND gates is approximately equal to:
(n−1)*(d 2XOR +d 2AND );
wherein d 2XOR is approximately equal to a delay through a two-input XOR gate;
wherein d 2AND is approximately equal to a delay through a two-input AND gate.
10. The Galois field multiplier of claim 6 wherein the first plurality of AND gates are two-input AND gates, the first plurality of XOR gates are three-input XOR gates, the second plurality of AND gates are two-input AND gates, and the second plurality of two-input XOR gates.
11. The Galois field multiplier of claim 10 wherein a longest delay path through the first plurality of XOR gates is approximately equal to:
(log 3 n)*d 3XOR
wherein d 3XOR is approximately equal to the delay through a three-input XOR gate.
12. The Galois field multiplier of claim 6 wherein the generated partial products from the k bit multiplier and the n bit multiplicand are generated in a first clock cycle from the first group of one or more clock cycles;
wherein the generated partial products are logarithmically reduced to a (n+k−1) product in a second clock cycle from the first group of one or more clock cycles.