Polynomial calculations optimized for programmable integrated circuit device structures

• US 9,207,909 B1
• Filed: 03/08/2013
• Issued: 12/08/2015
• Est. Priority Date: 11/26/2012
• Status: Active Grant

• Current Assignee: Altera Corporation (Intel Corporation)
• Original Assignee: Altera Corporation (Intel Corporation)
• Inventors: Langhammer, Martin
• Primary Examiner(s): Ngo, Chuong D
• Assistant Examiner(s): Brien, Calvin M
• Application Number:
  US13/790,106
• Time in Patent Office: 1,005 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 7/5443 Sum of products for applications thereof, see the relevant places, e.g. G06F17/10, H03H17/00
• CPC Class Codes: G06F 7/724 Finite field arithmetic for error detection or correction in general H03M13/00, in computers G06F11/10

Abstract

Polynomial circuitry includes a respective partial product generator for each bit position of each term of a plurality of terms of a polynomial to be evaluated. A respective plurality of adders for each bit position adds partial products of a respective bit position across all of the plurality of terms to provide a respective bit-slice sum. Resulting bit-slice sums are offset from one another according to their respective bit positions. A final adder adds together the respective offset bit-slice sums to provide a result.

Claims

1. Polynomial circuitry for evaluating a polynomial having a plurality of terms, each term having a number of bit positions, said polynomial circuitry comprising:

a plurality of groups of partial product generators, each of said groups of partial product generators corresponding to a single term in said plurality of terms and, in each one of said groups of partial product generators, each respective partial product generator in said one of said groups of partial product generators providing an output value for a respective single input bit position of said single term to which said one of said groups of partial product generators corresponds;

adder circuitry for providing respective bit-slice sums, said adder circuitry comprising a plurality of respective groups of adders, each respective group of adders in said plurality of respective groups of adders including a number of adders equal in number to said plurality of terms and corresponding to one respective bit position in all of said plurality of terms, and summing output values of multiple ones of said partial product generators for said one respective bit position to provide said respective bit-slice sum having a respective bit-width, wherein resulting bit-slice sums are offset from one another, by less than their respective bit-widths, according to their respective bit positions, said plurality of groups of adders being equal in number to said number of bit positions; and

a final adder that adds together said respective offset bit-slice sums to provide a final result.

2. The polynomial circuitry of claim 1 wherein:

said terms have m bit positions; and

each respective partial product generator provides a partial result that is m bits wide.

3. The polynomial circuitry of claim 2 further comprising reduction circuitry that reduces width of said final result to m bits.

4. The polynomial circuitry of claim 1 further comprising reduction circuitry that reduces bit width of said final result.

5. The polynomial circuitry of claim 1 wherein each adder of said plurality of respective groups of adders is configured using at least one look-up table of a programmable integrated circuit device.

6. The polynomial circuitry of claim 5 wherein said programmable integrated circuit device comprises a field-programmable gate array.

7. A method of configuring a programmable device as circuitry for evaluating a polynomial having a plurality of terms, each term having a number of bit positions, said method comprising:

configuring, on said programmable device, a plurality of groups of partial product generators, each of said groups of partial product generators corresponding to a single term in said plurality of terms and, in each one of said groups of partial product generators, each respective partial product generator in said one of said groups of partial product generators providing an output value for a respective single input bit position of said single term to which said one of said groups of partial product generators corresponds;

configuring, on said programmable device, adder circuitry for providing respective bit-slice sums, said adder circuitry comprising a plurality of respective groups of adders, each respective group of adders in said plurality of respective groups of adders including a number of adders equal in number to said plurality of terms and corresponding to one respective bit position in all of said plurality of terms, and summing output values of multiple ones of said partial product generators for said one respective bit position to provide said respective bit-slice sum having a respective bit-width, wherein resulting bit-slice sums are offset from one another, by less than their respective bit-widths, according to their respective bit positions, said plurality of groups of adders being equal in number to said number of bit positions; and

configuring, on said programmable device, a final adder that adds together said respective offset bit-slice sums to provide a final result.

8. The method of claim 7 wherein:

said terms have m bit positions; and

said configuring a plurality of partial product generators comprises configuring each partial product generator to provide a partial result that is m bits wide.

9. The method of claim 8 further comprising configuring, on said programmable device, reduction circuitry that reduces width of said final result to m bits.

10. The method of claim 7 further comprising configuring, on said programmable device, reduction circuitry that reduces bit width of said final result.

11. The method of claim 7 wherein configuring adder circuitry comprises configuring each adder of said respective groups of adders using at least one look-up table of a programmable integrated circuit device.

12. The method of claim 11 wherein configuring adder circuitry comprises configuring each adder of said respective groups of adders using at least one look-up table of a field-programmable gate array.

13. A non-transitory machine-readable data storage medium encoded with non-transitory machine-executable instructions for configuring a programmable device as circuitry for evaluating a polynomial having a plurality of terms, each term having a number of bit positions, said instructions comprising:

instructions to configure, on said programmable device, a plurality of groups of partial product generators, each of said groups of partial product generators corresponding to a single term in said plurality of terms and, in each one of said groups of partial product generators, each respective partial product generator in said one of said groups of partial product generators providing an output value for a respective single input bit position of said single term to which said one of said groups of partial product generators corresponds;

instructions to configure, on said programmable device, adder circuitry for providing respective bit-slice sums, said adder circuitry comprising a plurality of respective groups of adders, each respective group of adders in said plurality of respective groups of adders including a number of adders equal in number to said plurality of terms and corresponding to one respective bit position in all of said plurality of terms, and summing output values of multiple ones of said partial product generators for said one respective bit position to provide said respective bit-slice sum having a respective bit-width, wherein resulting bit-slice sums are offset from one another, by less than their respective bit-widths, according to their respective bit positions, said plurality of groups of adders being equal in number to said number of bit positions; and

instructions to configure, on said programmable device, a final adder that adds together said respective offset bit-slice sums to provide a final result.

14. The non-transitory machine-readable data storage medium of claim 13 wherein:

said terms have m bit positions; and

said instructions to configure a plurality of partial product generators comprises configuring each partial product generator to provide a partial result that is m bits wide.

15. The non-transitory machine-readable data storage medium of claim 14 further comprising instructions to configure, on said programmable device, reduction circuitry that reduces width of said final result to m bits.

16. The non-transitory machine-readable data storage medium of claim 13 further comprising instructions to configure, on said programmable device, reduction circuitry that reduces bit width of said final result.

17. The non-transitory machine-readable data storage medium of claim 13 wherein said instructions to configure adder circuitry comprise instructions to configure each adder of said respective groups of adders using at least one look-up table of a programmable integrated circuit device.

18. The non-transitory machine-readable data storage medium of claim 17 wherein said instructions to configure adder circuitry comprise instructions to configure each adder of said respective groups of adders using at least one look-up table of a field-programmable gate array.