POLYNOMIAL SYNTHESIS

• US 20110010141A1
• Filed: 11/05/2007
• Published: 01/13/2011
• Est. Priority Date: 11/03/2006
• Status: Active Grant

• Current Assignee: Oxford Brookes University
• Original Assignee: Oxford Brookes University
• Inventors: Jabir, Abusaleh M.
• Granted Patent: US 9,223,917 B2
• Time in Patent Office: Days
• US Class Current: 703/2
• CPC Class Codes: G06F 30/30 Circuit design

Abstract

Galois Field circuit production apparatus for fabricating a polynomial over GF(2^m) in a circuit, comprising, an input device for allowing a specification relating to a desired polynomial over GF(2^m) to be entered, a processor and memory for producing an improved, and preferably optimized, netlist, and means for fabricating a circuit from an improved netlist, wherein the processor and memory are configured to factorize a netlist corresponding to an input specification, determining common factors by passing through chains of multipliers following chains of adders, and to use an optimization algorithm on the factorized net list to generate an improved net list, and wherein the means for fabricating operably fabricates a circuit based on the improved netlist produced by the processor.

Claims

1. A Galois Field circuit production apparatus for fabricating a polynomial over GF(2^m) in a circuit, comprising:

an input device for allowing a specification relating to a desired polynomial over GF(2^m) to be entered;

a processor and memory for producing an improved netlist defined over GF; and

a Galois Field circuit fabricator for fabricating a circuit from an improved netlist;

wherein the processor and memory are configured to factorize a netlist defined over GF and corresponding to an input specification, determining common factors by passing through chains of multipliers following chains of adders; and

wherein the circuit fabricator operably fabricates a circuit based on the improved netlist produced by the processor.

2. A Galois Field circuit production apparatus for fabricating a polynomial over GF(2^m) in a circuit, comprising;

an input device for allowing a specification relating to a desired polynomial over GF(2^m) to be entered;

a processor and memory for producing a netlist; and

a Galois Field circuit fabricator for fabricating a circuit from a netlist;

wherein the processor and memory are configured to decompose a Galois Polynomial Decision Diagram (GPDD) based on the initial specification by cutting nodes of the GPDD into sets, to reduce one or more of the area, power consumption, or delay of a circuit, and generate a first netlist; and

wherein the circuit fabricator operably fabricates a circuit from a netlist based on the first netlist produced by the processor.

3. An apparatus according to claim 2, wherein the netlist based on the first netlist is the first netlist.

4. An apparatus according to claim 2, wherein a processor and memory are configured to factorize the first netlist, determining common factors by passing through chains of multipliers following chains of adders.

5. An apparatus according to claim 2, wherein there is an optimization algorithm stored in the memory and the processor is configured to run the optimization algorithm on the first or the factorized net list to generate an improved, preferably optimized, net list and wherein the means for fabricating operably fabricates a circuit based on the improved netlist produced by the processor.

6. An apparatus according to claim 5, wherein the optimization algorithm processes recursively from the variable or constant nodes towards the root node, and/or for each GF(2^m) multiplier/adder node, one or more of and preferably all of the following are carried out:

if its two children are constants then, the GF(2^m) multiplier/adder node value is replaced with the addition or multiplication over GF(2^m) of its two children, if the GF(2^m) multiplier/adder node is equal to the GF(2^m) multiplication of a child with 1 or the GF(2^m) addition of a child with 0 then it is replaced with the value of that child (constant propagation), if the GF(2^m) multiplier/adder node value is equal to the value of the child GF(2^m) multiplied with 0 is added to itself the node value is replaced with 0.

7. An apparatus according to claim 5, comprising means to construct a first netlist, the means to construct is configured to decompose a diagram based on the initial specification and generate a first net list, the processor and memory configured to use the first net list as the basis for factorization and improvement using the optimization algorithm.

9. An apparatus according to claim 2, wherein the one or more cuts are made directly above the node with the minimum number of corresponding parents and/or the two sets comprise a first set including the nodes from the top of the initial GPDD down to, but not including the node with the minimum number of parent nodes, and a second set including the node with the minimum number of parent nodes.

11. An apparatus according to claim 2, wherein the one or more cuts are made directly above the node with the maximum number of corresponding parents and/or the two sets comprise a first set including the nodes from the top of the initial GPDD down to, but not including the node with the maximum number of parent nodes, and a second set including the node with the maximum number of parent nodes.

12. An apparatus according to claim 2, wherein the decomposing is multiplicative and/or additive.

13. An apparatus according to claim 2, comprising means for calculating polynomial coefficients wherein the means for calculating processor is configured to calculate the coefficients for the polynomial corresponding to a specification received by the input and to be fabricated into a circuit.

14. An apparatus according to claim 13, a wherein the means for calculating/processor is configured to store the coefficient for a first exponentiation term and calculate the coefficient for a lower exponentiation term by using the stored coefficient for the first term and using an incremental method preferably comprising multiplication and/or addition.

15. An apparatus according to claim 13, wherein the calculated coefficients arc stored in the memory, for use in producing the (first) net list, in the form of a directed acyclic graph such as a GPDD.

16. An apparatus according to claim 2, wherein the processor is configured to realize an exponentiation in the polynomial into a netlist by repeated multiplication.

17. An apparatus according to claim 2, wherein the first exponentiation of a first variable to be generated is stored in the memory and second exponentiation of the first variable is expressed in terms of a third exponentiation of the variable multiplied by the first exponentiation and then realized by generating the third exponentiation and multiplying it with the stored result of the first exponentiation.

18. An apparatus according to claim 5, where m is greater than 1 wherein the factorization and optimization results in a first optimized netlist containing word level blocks, which apparatus comprises synthesizing means configured to synthesize the word level blocks at the bit level, and wherein the processor and memory are configured so that the bit level output is further factorized, determining common factors by passing through chains of multiplier following chains of adders, and

to use the optimization algorithm on the factorized bit level net list to generate an optimized bit level net list and

wherein the circuit fabricator operably fabricates a circuit based on the optimized bit level netlist produced by the processor.

19. An apparatus according to claim 5, where m is greater than 1 wherein the factorization and optimization results in a first optimized netlist containing word level blocks and/or wherein the first netlist contains word level blocks

which apparatus comprises synthesizing means configured to synthesize the word level blocks at the bit level, and conversion means for converting the bit level output to a GPDD, and the processor and memory and/or means to construct are configured to decompose a GPDD, produced by the means for converting, to generate a bit level net list, the apparatus preferably configured to factorize and/or optimize the bit level net list as an optimized bit level netlist and

wherein the means for fabricating operably fabricates a circuit based on the (optimized) bit level netlist.

8. (canceled)

10. (canceled)

20. (canceled)

21. A Galois Field circuit apparatus for producing netlists for the fabrication of a polynomial over GF(2^m) in a circuit, comprising:

an input device for allowing a specification relating to a desired polynomial over GF(2^m) to be entered;

a processor and memory for producing an optimized netlist;

wherein the processor and memory are configured to factorize a netlist corresponding to an input specification, determining common factors by passing though chains of multiplier following chains of adders; and

preferably to use an optimization algorithm on the factorized net list to generate an optimized net list for use in fabricating a circuit.

22. A method of producing a netlist for fabricating a polynomial over GF(2^m) in a circuit, comprising the steps of:

taking a specification relating to a desired polynomial over GF(2^m);

using a processor to factorize a netlist corresponding to the specification;

determining common factors by passing though chains of multiplier following chains of adders; and

using an optimization algorithm on the factorized net list to generate an improved, and preferably optimized, net list for use in fabricating a circuit.

23. A method of producing a netlist for a polynomial over GF(2^m) in a circuit, comprising the steps of:

taking a specification relating to a desired polynomial over GF(2^m);

using a processor to decompose a GPDD based on the initial specification by cutting nodes of the GPDD into sets, the cuts being selected to reduce one or more of the area, power consumption, or delay of a circuit; and

generate a first net list for use in

fabricating a circuit.

24. A method of claim 23, further comprising the step of fabricating a circuit from a netlist based on the first netlist.

25. A method of verifying whether a plurality of optimized netlists produced by the method of claim 23 are functionally equivalent by comparing their structure to see if they are substantially the same.

26. A method of verifying whether a plurality of polynomials over GF(2^m) or initial specification corresponding to them are equal by comparing the node structure of the optimized netlists, corresponding to the polynomials or specifications, produced by the method of claim 23.

27. (canceled)

28. (canceled)

29. (canceled)

30. (canceled)

31. (canceled)

32. A Galois Field circuit apparatus for producing netlists for the fabrication of a polynomial over GF(2^m) in a circuit, comprising:

an input device for allowing a specification relating to a desired polynomial over GF(2^m) to be entered;

a processor and memory for producing a netlist; and

wherein the processor and memory are configured to decompose a Galois Polynomial Decision Diagram (GPDD) based on the initial specification by cutting nodes of the GPDD into sets the cuts being selected to reduce one or more of the area, power consumption or delay of a circuit, and generate a first netlist for use in fabricating a circuit.