Compact Galois field multiplier engine

• US 20040078409A1
• Filed: 03/24/2003
• Published: 04/22/2004
• Est. Priority Date: 10/09/2002
• Status: Active Grant

• Current Assignee: Analog Devices, Inc.
• Original Assignee: Analog Devices, Inc.
• Inventors: Kablotsky, Joshua A., Stein, Yosef
• Granted Patent: US 7,177,891 B2
• Time in Patent Office: Days
• 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 compact Galois field parallel multiplier engine includes a multiplier circuit for multiplying together two polynomials with coefficients over a Galois field to obtain their product; a Galois field linear transformer circuit has a multiply input from the multiplier circuit for predicting the modulo remainder of the polynomial product for an irreducible polynomial; first and second polynomial inputs; the Galois field linear transformer circuit may include a plurality of cells configured in a matrix section and a unity matrix section wherein the unity matrix section cells represent the prediction of the remainder when the output of the multiplier circuit is a polynomial with a power less than the power of the irreducible polynomial.

Claims

1. A compact Galois field multiplier engine comprising:

a multiplier circuit for multiplying together two polynomials with coefficients over a Galois field to obtain their product;

a Galois field linear transformer circuit having a multiply input from said multiplier circuit, an add input and an output for combining the add input with the predicted modulo remainder of the polynomial product for an irreducible polynomial;

a first polynomial input to said multiplier circuit;

a second polynomial input;

a multiplier input selection circuit for providing to said multiplier circuit in the multiply mode said second polynomial, in the multiply-add mode said output of said Galois field linear transformer circuit, and in the multiply-accumulate mode said second polynomial; and

an adder input selection circuit for providing to said add input of said Galois field linear transformer circuit in the multiply mode an additive identity, in the multiply-add mode said second polynomial input, and in said multiply-accumulate mode said output of said Galois field linear transformer circuit to obtain Galois field multiply, multiply-add, and multiply-accumulate functions of the input polynomials.

2. The compact Galois field multiplier engine of claim 1 in which said multiplier circuit includes and AND logic circuit for each term of said polynomial product to effect a Galois multiplier.

3. The compact Galois field multiplier engine of claim 1 in which said multiplier circuit includes an exclusive OR logic circuit for each pair of terms in said polynomial product to effect a Galois summation.

4. The compact Galois field multiplier engine of claim 1 in which said Galois field linear transformer circuit includes a matrix of cells each cell including an exclusive OR logic circuit, an AND logic circuit having an output connected to said exclusive OR logic circuit, and an input for receiving an input data bit.

5. The compact Galois field multiplier engine of claim 1 in which said output of said Galois field linear transformer circuit is fed back to said multiplier input selection circuit and said adder input selection circuit over a local bus in said engine.

6. The compact Galois field multiplier engine of claim 1 in which said multiplier input selection circuit includes an input from said output of said Galois field linear transformer circuit and an input from said second polynomial.

7. The compact Galois field multiplier engine of claim 1 in which said adder input selection circuit includes an input from said output of said Galois field linear transformer circuit, an input from said second polynomial, and an additive identity input.

8. The compact Galois field multiplier engine of claim 4 in which each said exclusive OR logic circuit has its output connected to the input of the next successive exclusive OR logic circuit except for the last exclusive OR logic circuit whose output is connected to the output of the matrix and the first exclusive OR logic circuit whose input is connected to a null level.

9. The compact Galois field multiplier engine of claim 1 further including a reconfigurable control circuit for supplying to said Galois field linear transformer circuit a set of coefficients for predicting the modulo remainder for a predetermined irreducible polynomial.

10. The compact Galois field multiplier engine of claim 9 in which said Galois field linear transformer circuit includes a plurality of Galois field transformer units and said reconfigurable control circuit supplies said coefficients in parallel to said Galois field transformer units.

11. The compact Galois field multiplier engine of claim 1 in which said Galois field linear transformer circuit includes a plurality of cells configured in a matrix section and a unity matrix section wherein the unity matrix section cells represent the prediction of the remainder when the output of the multiplier circuit is a polynomial with a power less than the power of the irreducible polynomial.

12. The compact Galois field multiplier engine of claim 9 in which said Galois field linear transformer circuit includes a plurality of Galois field transformer units and said reconfigurable control circuit includes a plurality of reconfigurable control units one associated with each of said Galois field linear transformer units.

13. The compact Galois field multiplier engine of claim 1 in which said functions of the input polynomials are generated in one cycle.

14. The compact Galois field multiplier engine of claim 9 in which said an additive identity is a null level.

57. The compact Galois field multiply-accumulate engine of claim 5 in which each said exclusive OR logic circuit has its output connected to the input of the next successive exclusive OR logic circuit except for the last exclusive OR logic circuit whose output is connected to the output of the matrix and the first exclusive OR logic circuit whose input is connected to said output of said Galois field linear transformer circuit to obtain Galois field multiply-accumulate functions of the input polynomials.

15. A compact Galois field multiplier engine comprising:

a multiplier circuit for multiplying together two polynomials with coefficients over a Galois field to obtain their product;

a Galois field linear transformer circuit having a multiply input from said multiplier circuit for predicting the modulo remainder of the polynomial product for an irreducible polynomial;

a first polynomial input to said multiplier circuit;

a second polynomial input; and

an adder input selection circuit for providing to said add input of said Galois field linear transformer circuit in the multiply mode an additive identity level to obtain Galois field multiply functions of the input polynomials.

16. The compact Galois field multiplier engine of claim 15 in which said multiplier circuit includes and AND logic circuit for each term of said polynomial product to effect a Galois multiplier.

17. The compact Galois field multiplier engine of claim 15 in which said multiplier circuit includes an exclusive OR logic circuit for each pair of terms in said polynomial product to effect a Galois summation.

18. The compact Galois field multiplier engine of claim 15 in which said Galois field linear transformer circuit includes a matrix of cells each cell including an exclusive OR logic circuit, an AND logic circuit having an output connected to said exclusive OR logic circuit, and an input for receiving an input data bit.

19. The compact Galois field multiplier engine of claim 15 in which said adder input selection circuit includes an input from said output of said Galois field linear transformer circuit, an input from said second polynomial, and an additive identity input.

20. The compact Galois field multiplier engine of claim 18 in which each said exclusive OR logic circuit has its output connected to the input of the next successive exclusive OR logic circuit except for the last exclusive OR logic circuit whose output is connected to the output of the matrix and the first exclusive OR logic circuit whose input is connected to said adder input selection circuit.

21. The compact Galois field multiplier engine of claim 15 further including a reconfigurable control circuit for supplying to said Galois field linear transformer circuit a set of coefficients for predicting the modulo remainder for a predetermined irreducible polynomial.

22. The compact Galois field multiplier engine of claim 21 in which said Galois field linear transformer circuit includes a plurality of Galois field transformer units and said reconfigurable control circuit supplies said coefficients in parallel to said Galois field transformer units.

23. The compact Galois field multiplier engine of claim 15 in which said Galois field linear transformer circuit includes a plurality of cells configured in a matrix section and a unity matrix section wherein the unity matrix section cells represent the prediction of the remainder when the output of the multiplier circuit is a polynomial with a power less than the power of the irreducible polynomial.

24. The compact Galois field multiplier engine of claim 21 in which said Galois field linear transformer circuit includes a plurality of Galois field transformer units and said reconfigurable control circuit includes a plurality of reconfigurable control units one associated with each of said Galois field linear transformer units.

25. The compact Galois field multiplier engine of claim 15 in which said functions of the input polynomials are generated in one cycle.

26. The compact Galois field multiplier engine of claim 15 in which said an additive identity level is a null level.

27. A compact Galois field multiplier engine comprising:

a multiplier circuit for multiplying together two polynomials with coefficients over a Galois field to obtain their product;

a Galois field linear transformer circuit having a multiply input from said multiplier circuit, an add input and an output for combining the add input with the predicted modulo remainder of the polynomial product for an irreducible polynomial;

a first polynomial input to said multiplier circuit;

a second polynomial input said output of Galois field linear transformer circuit;

an adder input selection circuit for providing to said add input of said Galois field linear transformer circuit in the multiply-add mode said second polynomial input to obtain Galois field multiply-add functions of the input polynomials.

28. The compact Galois field multiplier engine of claim 27 in which said functions of the input polynomials are generated in one cycle.

29. The compact Galois field multiplier engine of claim 27 in which said an additive identity level is a null level.

30. A compact Galois field multiplier engine comprising:

a multiplier circuit for multiplying together two polynomials with coefficients over a Galois field to obtain their product;

a Galois field linear transformer circuit having a multiply input from said multiplier circuit, an add input and an output for combining the add input with the predicted modulo remainder of the polynomial product for an irreducible polynomial;

a first polynomial input to said multiplier circuit;

a second polynomial input;

an adder input selection circuit for providing to said add input of said Galois field linear transformer circuit in said multiply-accumulate mode said output of said Galois field linear transformer circuit to obtain Galois field multiply-accumulate functions of the input polynomials.

31. The compact Galois field multiplier engine of claim 30 in which said functions of the input polynomials are generated in one cycle.

32. The compact Galois field multiplier engine of claim 30 in which said an additive identity level is a null level.

33. A compact Galois field multiplier engine comprising:

a multiplier circuit for multiplying together two polynomials with coefficients over a Galois field to obtain their product;

a Galois field linear transformer circuit having a multiply input from said multiplier circuit, an add input and an output for combining the add input with the predicted modulo remainder of the polynomial product for an irreducible polynomial;

a first polynomial input to said multiplier circuit;

a second polynomial input;

a multiplier input selection circuit for providing to said multiplier circuit in the multiply mode said second polynomial and in the multiply-add mode said output of said Galois field linear transformer circuit; and

an adder input selection circuit for providing to said add input of said Galois field linear transformer circuit in the multiply mode an additive identity level and in the multiply-add mode said second polynomial input, to obtain Galois field multiply and multiply-add functions of the input polynomials.

34. The compact Galois field multiplier engine of claim 33 in which said functions of the input polynomials are generated in one cycle.

35. The compact Galois field multiplier engine of claim 33 in which said an additive identity level is a null level.

36. A compact Galois field multiplier engine comprising:

a multiplier circuit for multiplying together two polynomials with coefficients over a Galois field to obtain their product;

a Galois field linear transformer circuit having a multiply input from said multiplier circuit, an add input and an output for combining the add input with the predicted modulo remainder of the polynomial product for an irreducible polynomial;

a first polynomial input to said multiplier circuit;

a second polynomial input;

a multiplier input selection circuit for providing to said multiplier circuit in the multiply mode said second polynomial and in the multiply-accumulate mode said second polynomial; and

an adder input selection circuit for providing to said add input of said Galois field linear transformer circuit in the multiply mode an additive identity level and in said multiply-accumulate mode said output of said Galois field linear transformer circuit to obtain Galois field multiply and multiply-accumulate functions of the input polynomials.

37. The compact Galois field multiplier engine of claim 36 in which said functions of the input polynomials are generated in one cycle.

38. The compact Galois field multiplier engine of claim 36 in which said an additive identity level is a null level.

39. A compact Galois field multiplier engine comprising:

a multiplier circuit for multiplying together two polynomials with coefficients over a Galois field to obtain their product;

a Galois field linear transformer circuit having a multiply input from said multiplier circuit, an add input and an output for combining the add input with the predicted modulo remainder of the polynomial product for an irreducible polynomial;

a first polynomial input to said multiplier circuit;

a second polynomial input;

a multiplier input selection circuit for providing to said multiplier circuit in the multiply-add mode said output of said Galois field linear transformer circuit, and in the multiply-accumulate mode said second polynomial; and

an adder input selection circuit for providing to said add input of said Galois field linear transformer circuit in the multiply-add mode said second polynomial input, and in said multiply-accumulate mode said output of said Galois field linear transformer circuit to obtain Galois field multiply-add and multiply-accumulate functions of the input polynomials.

40. The compact Galois field multiplier engine of claim 39 in which said functions of the input polynomials are generated in one cycle.

41. The compact Galois field multiplier engine of claim 39 in which said an additive identity level is a null level.

42. A compact Galois field parallel multiplier circuit comprising:

a multiplier circuit for multiplying together two polynomials with coefficients over a Galois field to obtain their product; and

a Galois field linear transformer circuit for predicting the modulo remainder of its polynomial product for an irreducible polynomial including a plurality of cells configured in a matrix section and a unity matrix section wherein the unity matrix section cells represent the prediction of the remainder when the output of the multiplier circuit is a polynomial with a power less than the power of the irreducible polynomial.

43. The compact Galois field parallel multiplier-circuit of claim 42 in which each said cell includes a programmable exclusive OR cell.

44. The compact Galois field parallel multiplier circuit of claim 43 in which said programmable exclusive OR cell includes an exclusive OR circuit and an AND circuit.

45. The compact Galois field parallel multiplier circuit of claim 42 further including a reconfigurable control circuit for supplying to said Galois field linear transformer circuit a set of coefficients for predicting the modulo remainder for a predetermined irreducible polynomial.

46. The compact Galois field parallel multiplier circuit of claim 45 in which said Galois field linear transformer circuit includes a plurality of Galois field linear transformer units.

47. The compact Galois field parallel multiplier circuit of claim 45 in which said reconfigurable control circuit supplies said coefficients in parallel to said Galois field linear transformer units.

48. The compact Galois field parallel multiplier circuit of claim 45 in which said reconfigurable control circuit includes a plurality of reconfigurable control units one associated with each of said Galois field linear transformer units.

49. A compact Galois field multiplier engine comprising:

a multiplier circuit for multiplying together two polynomials with coefficients over a Galois field to obtain their product;

a first polynomial input to said multiplier circuit;

a second polynomial input to said multiplier circuit;

a Galois field linear transformer circuit having a multiply input from said multiplier circuit for predicting the modulo remainder of the polynomial product for an irreducible polynomial to obtain Galois field multiply functions of the input polynomials.

50. The compact Galois field multiplier engine of claim 49 in which said Galois field linear transformer circuit includes a matrix of cells each cell including an exclusive OR logic circuit, an AND logic circuit having an output connected to said exclusive OR logic circuit, and an input for receiving an input data bit.

51. The compact Galois field multiplier engine of claim 50 in which each said exclusive OR logic circuit has its output connected to the input of the next successive exclusive OR logic circuit except for the last exclusive OR logic circuit whose output is connected to the output of the matrix and the first exclusive OR logic circuit whose input is connected to an additive identity level to obtain Galois field multiply functions of the input polynomials.

52. A compact Galois field multiply-add engine comprising:

a multiplier circuit for multiplying together two polynomials with coefficients over a Galois field to obtain their polynomial product; and

a Galois field linear transformer circuit responsive to said polynomial product from said multiplier circuit and a polynomial input at its add input for providing one of the polynomial inputs to said multiplier by combining the add input with the predicted modulo remainder of the polynomial product for an irreducible polynomial to obtain Galois field multiply-add functions of the input polynomials.

53. The compact Galois field multiply-add engine of claim 52 in which said Galois field linear transformer circuit includes a matrix of cells each cell including an exclusive OR logic circuit, an AND logic circuit having an output connected to said exclusive OR logic circuit, and an input for receiving an input data bit.

54. The compact Galois field multiplier-add engine of claim 53 in which each said exclusive OR logic circuit has its output connected to the input of the next successive exclusive OR logic circuit except for the last exclusive OR logic circuit whose output is connected to the output of the matrix and the first exclusive OR logic circuit whose input is connected to a second polynomial input to obtain Galois field multiply-add functions of the input polynomials.

55. A compact Galois field multiply-accumulate engine comprising:

a multiplier circuit for multiplying together two polynomials with coefficients over a Galois field to obtain their polynomial product;

a first polynomial input to said multiplier circuit;

a second polynomial input to said multiplier circuit;

a Galois field linear transformer circuit responsive to said polynomial product from said multiplier circuit, and a polynomial add input for combining the add input with the predicted modulo remainder of the polynomial product for an irreducible polynomial to obtain Galois field multiply-accumulate functions of the input polynomials; and

said output providing said polynomial to said add input of said Galois field linear transform circuit.

56. The compact Galois field multiply-accumulate engine of claim 55 in which said Galois field linear transformer circuit includes a matrix of cells each cell including an exclusive OR logic circuit, an AND logic circuit having an output connected to said exclusive OR logic circuit, and an input for receiving an input data bit.