Approximating functions

• US 10,268,450 B2
• Filed: 09/06/2017
• Issued: 04/23/2019
• Est. Priority Date: 05/01/2014
• Status: Active Grant

• Current Assignee: Imagination Technologies Limited (Imagination Technologies Group Ltd.)
• Original Assignee: Imagination Technologies Limited (Imagination Technologies Group Ltd.)
• Inventors: Lee, Tim
• Primary Examiner(s): Malzahn, David H
• Application Number:
  US15/696,385
• Publication Number:
  US 20170364329A1
• Time in Patent Office: 594 Days
• Field of Search: None
• CPC Class Codes: G06F 17/17 Function evaluation by approximation methods, e.g. inter- or extrapolation, smoothing, least mean square method G06F17/18 takes precedence ; interpolation for numerical control G05B19/18
• CPC Class Codes: G06F 7/523 Multiplying only
• CPC Class Codes: G06F 7/544 for evaluating functions by calculation G06F7/4824 takes precedence

Abstract

A binary logic circuit for approximating a mathematical function over a predefined range as a series of linear segments, each linear segment having one of a predetermined set of fixed gradients and a corresponding base value, the binary logic circuit comprising: an input for receiving an input variable in the predefined range; a plurality of logic chains each comprising: a binary multiplier adapted to perform multiplication by a respective one of the set of fixed gradients using h-1 binary adders, where h is the extended Hamming weight; and a binary adder adapted to add a base value to the input or output of the binary multiplier; and selection logic configured to select one of the logic chains in dependence on the input variable so as to provide, for the received input variable, an approximate value of the mathematical function.

Claims

1. A binary logic circuit for approximating a mathematical function over a predefined range as a series of linear segments, each linear segment having one of a predetermined set of fixed gradients and a corresponding base value, wherein each of the fixed gradients in the predetermined set of fixed gradients has a respective minimum extended Hamming weight which is less than or equal to a threshold value, the binary logic circuit comprising:

an input for receiving an input variable in the predefined range;

a plurality of logic chains each comprising;

a binary multiplier configured to perform multiplication by a respective fixed gradient of the set of fixed gradients using a number of binary adders, wherein said number is one less than the minimum extended Hamming weight for the respective fixed gradient, and

a binary adder configured to add a base value to an input or output of the binary multiplier; and

selection logic configured to select one of the logic chains in dependence on the input variable so as to provide, for the received input variable, an approximate value of the mathematical function.

2. The binary logic circuit of claim 1, wherein the threshold value determines a limit on the number of adders that a binary multiplier is configured to use for performing a multiplication.

3. The binary logic circuit of claim 1, wherein the threshold value is 2 or 3.

4. The binary logic circuit of claim 1, wherein the extended minimum Hamming weights of the respective fixed gradients of the predetermined set are less than or equal to 3.

5. The binary logic circuit of claim 1, the selection logic being configured to select one of the logic chains by comparing the received input variable to a predetermined set of break values, each break value representing a value of the input variable delimiting one or more linear segments.

6. The binary logic circuit of claim 5, the selection logic being configured to determine a pair of adjacent break values between which the received input variable lies and, responsive to that determination, select the logic chain corresponding to the linear segment lying between that pair of adjacent break values.

7. The binary logic circuit of claim 5, wherein each of the set of break values is used in the selection logic in the form of a representation of that break value having a minimum extended Hamming weight for that break value.

8. The binary logic circuit of claim 7, wherein the minimum extended Hamming weight of each of the set of break values is less than or equal to 3.

9. The binary logic circuit of claim 1, wherein the mathematical function is expressed in the form y=f(x), where x and y represent values along respective Cartesian axes.

10. The binary logic circuit of claim 9, the binary adder of each logic chain being arranged to add the respective base value to the output of the binary multiplier.

11. The binary logic circuit of claim 10, wherein each linear segment represents part of a line that crosses the y axis at the base value.

12. The binary logic circuit of claim 9, the binary adder of each logic chain being arranged to add the respective base value to the received input variable.

13. The binary logic circuit of claim 12, wherein each linear segment represents part of a line that crosses the x axis at the base value.

14. The binary logic circuit of claim 1, wherein the mathematical function is a continuous smooth function over the predefined range, or wherein the mathematical function is a base 2 logarithm and the predefined range is between 1 and 2, or wherein the mathematical function is a gamma function and the predefined range is between 0 and 1.

15. The binary logic circuit of claim 1, wherein at least one of the plurality of logic chains comprises a binary multiplier configured to perform multiplication by a fixed gradient having a minimum extended Hamming weight of greater than one.

16. A method of deriving a hardware representation of a binary logic circuit configured to approximate a mathematical function over a predefined range as a series of linear segments, the method comprising:

fitting a plurality of linear segments to the function over the predefined range, each segment extending between a pair of break points and having a fixed gradient selected from a predetermined set of fixed gradients, wherein each of the fixed gradients in the predetermined set of fixed gradients has a minimum extended Hamming weight which is less than or equal to a threshold value,

determining a base value for each of the segments; and

deriving a hardware representation for a binary logic circuit which comprises;

for each of the plurality of linear segments;

a binary multiplier configured to perform multiplication by the selected fixed gradient of the segment using a number of binary adders, wherein said number is one less than the minimum extended Hamming weight for the selected fixed gradient, and

a binary adder configured to add the determined base value for the segment to an input or output of the binary multiplier; and

selection logic configured to select, for a given input variable in the predefined range, one of the plurality of binary multipliers in dependence on the determined break points.

17. The method of claim 16, wherein the threshold value determines a limit on the number of adders that a binary multiplier is configured to use for performing a multiplication.

18. The method of claim 16, further comprising:

for each of the plurality of linear segments, calculating an average gradient between the break points delineating that linear segment; and

selecting the closest fixed gradient to the calculated average gradient from the predetermined set of fixed gradients.

19. The method of claim 16, further comprising selecting a sufficient number of the plurality of linear segments such that the binary logic circuit achieves at least a predetermined accuracy substantially over the predefined range of values for the input variable.

20. A method of manufacturing a binary logic circuit in accordance with a hardware representation derived using a method configured to approximate a mathematical function over a predefined range as a series of linear segments, comprising the steps of:

fitting a plurality of linear segments to the function over the predefined range, each segment extending between a pair of break points and having a fixed gradient selected from a predetermined set of fixed gradients, wherein each of the fixed gradients in the predetermined set of fixed gradients has a minimum extended Hamming weight which is less than or equal to a threshold value,

determining a base value for each of the segments; and

deriving a hardware representation for a binary logic circuit which comprises;

for each of the plurality of linear segments;

a binary multiplier configured to perform multiplication by the selected fixed gradient of the segment using a number of binary adders, wherein said number is one less than the minimum extended Hamming weight for the selected fixed gradient, and

a binary adder configured to add the determined base value for the segment to an input or output of the binary multiplier; and

selection logic configured to select, for a given input variable in the predefined range, one of the plurality of binary multipliers in dependence on the determined break points.