Granted Patent B2

US 8,312,072 · App. 12/211,268 · Granted Nov 13, 2012

Assignee: LSI Corporation

Abstract

Claims (87)

1. An apparatus comprising:

a multiplier circuit configured to multiply a first multiplicand and a second multiplicand based on a programmable base value and generate a plurality of intermediate values, each intermediate value representing a result of the multiplication reduced by a respective irreducible polynomial; and

a multiplexing circuit configured to generate an output in response to the plurality of intermediate values from the multiplier circuit and said programmable base value.

2. The apparatus according to claim 1 , wherein said multiplier circuit comprises:

a binary-unary encoder circuit configured to generate a code value in response to said programmable base value;

a plurality of double conjunction modules configured to modify a first portion of said first multiplicand and a first portion of said second multiplicand in response to said code value;

a polynomial multiplier circuit configured to generate a product value by multiplying said first multiplicand as modified by said plurality of double conjunction modules with said second multiplicand as modified by said plurality of double conjunction modules; and

a linear transform circuit configured to generate each of said plurality of intermediate values by reducing said product value by the respective irreducible polynomial.

3. The apparatus according to claim 2 , wherein said binary-unary encoder comprises:

a first circuit configured to bitwise AND a first input and a second input;

a second circuit configured to bitwise AND said first input and a third input;

a third circuit configured to bitwise AND said second input and said third input;

a fourth circuit configured to bitwise AND an output of said second circuit and said second input;

a fifth circuit configured to bitwise OR said third input and a fourth input;

a sixth circuit configured to bitwise OR an output of said first circuit and an output of said fifth circuit;

a seventh circuit configured to bitwise OR an output of said third circuit and said fourth input;

an eighth circuit configured to bitwise OR an output of said fifth circuit and said second input;

a ninth circuit configured to bitwise OR said fourth input and an output of said fourth circuit;

a tenth circuit configured to bitwise OR said output of said second circuit and an output of said seventh circuit; and

an eleventh circuit configured to bitwise OR said first input and an output of said eighth circuit.

4. The apparatus according to claim 2 , wherein said multiplier circuit further comprises:

a normal base to standard base transform circuit; and

a standard base to normal base transform circuit.

5. The apparatus according to claim 4 , wherein said normal base to standard base transform circuit further comprises:

a first linear transform circuit configured to transform said first multiplicand from normal to standard bases;

a first multiplexing circuit configured to multiplex outputs of said first linear transform circuit in response to a control input;

a second linear transform circuit configured to transform said second multiplicand from normal to standard bases; and

a second multiplexing circuit configured to multiplex outputs of said second linear transform circuit in response to said control input.

6. The apparatus according to claim 2 , wherein said linear transform circuit comprises a plurality of submodules, each configured to reduce an output of said polynomial multiplier by a respective modulus.

7. The apparatus according to claim 2 , wherein said linear transform circuit comprises a plurality of submodules, each configured to reduce an output of said polynomial multiplier by a respective irreducible polynomial over a field GF(2).

8. The apparatus according to claim 7 , wherein said respective irreducible polynomial comprise a polynomial selected from the group consisting of:

P 0 =x 8 +x 4 +x 3 +x+ 1,

P 1 =x 9 +x+ 1,

P 2 =x 10 +x 3 +1,

P 3 =x 11 +x 2 +1,

P 4 =x 12 +x 3 +1,

P 5 =x 13 +x 4 +x 3 +x+ 1,

P 6 =x 14 +x 5 +1,

P 7 =x 15 +x+ 1, and

P 8 =x 16 +x 5 +x 3 +x+ 1.

9. The apparatus according to claim 1 , wherein the multiplier circuit is optimized using a cover of units-submatrices.

10. An apparatus comprising:

means for multiplying a first multiplicand and a second multiplicand based on a programmable base value and generating a plurality of intermediate values, each intermediate value representing a result of the multiplication reduced by a respective irreducible polynomial; and

means for generating an output in response to the plurality of outputs of the multiplying means and said programmable base value.

11. A method of universal Galois field multiplication comprising the steps of:

using a circuit to multiply a first multiplicand and a second multiplicand based on a programmable base value and generate a plurality of intermediate values, each intermediate value representing a result of the multiplication reduced by a respective irreducible polynomial; and

generating an output in response to the plurality of intermediate values and said programmable base value.

12. The method according to claim 11 , wherein multiplying said first multiplicand and said second multiplicand based on said programmable base value comprises:

generating a code value in response to said programmable base value;

modifying a first portion of said first multiplicand and a first portion of said second multiplicand in response to said code value;

generating a product value by multiplying said first multiplicand as modified with said second multiplicand as modified; and

generating each of said plurality of intermediate values by reducing said product value by the respective irreducible polynomial.

13. The method according to claim 12 , wherein generating said code value in response to said programmable base value comprises the steps of:

(A) receiving said programmable base value as a first input, a second input, a third input and a fourth input;

(B) bitwise ANDing said first input and said second input;

(C) bitwise ANDing said first input and said third input;

(D) bitwise ANDing said second input and said third input;

(E) bitwise ANDing a result of step (C) and said second input;

(F) bitwise ORing said third input and said fourth input;

(G) bitwise ORing a result of step (B) and a result of step (F);

(H) bitwise ORing a result of step (D) and said fourth input;

(I) bitwise ORing a result of step (F) and said second input;

(J) bitwise ORing said fourth input and a result of step (E);

(K) bitwise ORing the result of step (C) and a result of step (H); and

(L) bitwise ORing said first input and a result of step (I).

14. The method according to claim 12 , wherein multiplying said first multiplicand and said second multiplicand comprises:

performing a normal base to standard base transformation; and

performing a standard base to normal base transformation.

15. The method according to claim 14 , wherein said normal base to standard base transformation comprises:

a first linear transformation configured to transform said first multiplicand from normal to standard bases;

multiplexing a result of said first linear transformation in response to a control input;

a second linear transformation configured to transform said second multiplicand from normal to standard bases; and

multiplexing a result of said second linear transformation in response to said control input.

16. The method according to claim 12 , wherein reducing said product value by the respective irreducible polynomial is performed over a field GF(2).

17. The method according to claim 16 , wherein said respective irreducible polynomial comprise a polynomial selected from the group consisting of:

P 0 =x 8 +x 4 +x 3 +x+ 1,

P 1 =x 9 +x+ 1,

P 2 =x 10 +x 3 +1,

P 3 =x 11 +x 2 +1,

P 4 =x 12 +x 3 +1,

P 5 =x 13 +x 4 +x 3 +x+ 1,

P 6 =x 14 +x 5 +1,

P 7 =x 15 + 1, and

P 8 =x 16 +x 5 +x 3 +x+ 1.

18. The method according to claim 11 , wherein said circuit comprises a multiplier circuit.

19. The method according to claim 11 , wherein said output is generated using a second circuit.

20. The method according to claim 19 , wherein said second circuit comprises a multiplexing circuit.

Assignments (8)

Continuity (1)