High-speed evaluation of polynomials

• US 6,026,420 A
• Filed: 01/20/1998
• Issued: 02/15/2000
• Est. Priority Date: 01/20/1998
• Status: Expired due to Term

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: 3Com Corporation (HP Inc.)
• Inventors: Mantri, Ravi G., DesJardins, Philip A.
• Primary Examiner(s): Mai, Tan V.
• Application Number:
  US09/009,393
• Time in Patent Office: 756 Days
• Field of Search: 708/492, 714/752, 714/781, 714/784, 714/785
• 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/157 Polynomial evaluation, i.e. determination of a polynomial sum at a given value

Abstract

A method and device for evaluating polynomial equations with a logic computer. To evaluate the polynomial equation more efficiently using a computer with latent memory accesses, the polynomial is split into a plurality of sub-polynomials. The sub-polynomials can be simultaneously evaluated using Horner'"'"'s rule. The results of the sub-polynomial evaluations are summed to obtain the evaluation of the polynomial equation. A device and method are described.

Claims

1. A device for evaluating a polynomial equation comprising:

a splitter for splitting the polynomial into a plurality of sub-polynomial equations;

a plurality of accumulators for evaluating the sub-polynomial equations of the polynomial equation;

a plurality of adders in communication with the corresponding plurality of accumulators, wherein the adders add to the sub-polynomial equations in the plurality of accumulators;

a plurality of multipliers in communication with the corresponding plurality of accumulators and the corresponding plurality of adders;

control logic to control the adders and multipliers to carry out Horner'"'"'s rule on the sub-polynomials;

a plurality of final multipliers in communication with the corresponding plurality of accumulators for multiplying accumulator values; and

a summer in communication with the plurality of final multipliers for summing final multiplier values to yield a result of the polynomial evaluation.

2. The device of claim 1 wherein the plurality of accumulators for evaluating the sub-polynomial equations simultaneously evaluate a plurality of sub-polynomial equations.

3. The device of claim 1 wherein the polynomial comprises a Galois field polynomial.

4. The device of claim 1 wherein the plurality of multipliers comprise a multiplication look-up table stored in memory.

5. The device of claim 1 wherein the plurality of multipliers comprise shift registers.

6. The device of claim 1 wherein the plurality of adders comprise Exclusive-OR logic.

7. The device of claim 1 wherein the control logic comprises programmed software.

8. The device of claim 1 wherein the control logic comprises digital logic hardware.

9. The device of claim 1 wherein the plurality of accumulators comprise locations in computer memory.

10. The device of claim 1 wherein the plurality of accumulators comprise computer processor registers.

11. The device of claim 1 wherein the sub-polynomial equations comprise a first sub-polynomial equation comprising the even-order terms and a second sub-polynomial equation comprising the odd-order terms.

12. The device of claim 4 wherein the sub-polynomial equations comprise a plurality of sub-polynomial equations appropriate for the number of the clock cycles required to access the multiplication table.

13. A computer readable medium having stored therein instructions for causing a processing unit to execute a method of evaluating a polynomial equation comprising the steps of:

splitting a polynomial equation into a plurality of sub-polynomial equations;

evaluating the sub-polynomial equations by accessing the multiplication table stored in memory, wherein a number of the plurality of sub-polynomial equations are evaluated simultaneously; and

summing the results of the step of evaluating sub-polynomials to obtain the evaluation of the polynomial.

14. The computer-readable medium of claim 13 wherein the polynomial is a Galois field polynomial.

15. The computer-readable medium of claim 13 wherein the step of evaluating the sub-polynomial uses Horner'"'"'s rule.

16. The computer-readable medium of claim 13 wherein the step of evaluating the sub-polynomial requires a latent memory access.

17. A computer-readable medium having stored therein instructions for causing a processing unit to execute a method of evaluating a polynomial equation comprising the steps of:

storing coefficients of the polynomial into memory locations;

separating the coefficients into a plurality of sub-polynomials;

evaluating the plurality of sub-polynomials using a multiplication lookup table stored in memory; and

summing the result of the sub-polynomials evaluation to obtain the result of the polynomial evaluation.

18. The computer-readable medium of claim 17 wherein the step of evaluating the plurality of sub-polynomials evaluates a number of sub-polynomials simultaneously.

19. A device for evaluating a polynomial equation comprising:

a splitter for splitting a polynomial equation into a plurality of sub-polynomial equations;

a multiplier for simultaneously evaluating the sub-polynomial equations; and

a summer for summing the evaluation results of the sub-polynomial equations to obtain the evaluation of the polynomial.

20. The device of claim 19 wherein the splitter and multiplier comprise electronic circuitry.

21. The device of claim 19 wherein the summer comprises combinational logic.

22. The device of claim 19 wherein the summer comprises a computer logic processor.