Approximating functions

Patent metadata

Field	Value
Publication number	US-10402167-B2
Application number	US-201916351159-A
Country	US
Kind code	B2
Filing date	Mar 12, 2019
Priority date	May 1, 2014
Publication date	Sep 3, 2019
Grant date	Sep 3, 2019

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.

First claim

What is claimed is:

1. A binary logic circuit for approximating a mathematical function over a predefined range as a series of linear segments, each linear segment extending between a pair of break points and having a gradient and a 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 configured to perform multiplication by a 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,
wherein each of the break points has a minimum extended Hamming weight which is less than or equal to a threshold value.

2. The binary logic circuit of claim 1 , wherein each linear segment has one of a predetermined set of fixed gradients, and 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 further threshold value.

3. The binary logic circuit of claim 2 , wherein the binary multiplier is configured to perform multiplication by a respective fixed gradient of the set of fixed gradients using a number of binary adders, wherein said number of binary adders is one less than the minimum extended Hamming weight for the respective fixed gradient.

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

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

6. 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 associated with the break points, each break value representing a value of the input variable delimiting one or more linear segments.

7. The binary logic circuit of claim 6 , the selection logic being configured to determine the 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.

8. The binary logic circuit of claim 6 , 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.

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

10. 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, and wherein the binary adder of each logic chain is 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 1 , wherein the mathematical function is expressed in the form y=f(x), where x and y represent values along respective Cartesian axes, and wherein the binary adder of each logic chain is 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 linear segment extending between a pair of break points and having a gradient and a base value; 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 gradient of the segment, and
a binary adder configured to add the 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 break points,

wherein each of the break points has a minimum extended Hamming weight which is less than or equal to a threshold value.

17. The method of claim 16 , wherein each of the linear segments has one of a predetermined set of fixed gradients, and 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 further threshold value, and
wherein the binary multiplier is configured to perform multiplication by a respective fixed gradient of the set of fixed gradients using a number of binary adders, wherein said number of binary adders is one less than the minimum extended Hamming weight for the selected fixed gradient.

18. The method of claim 17 , 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 linear segment extending between a pair of break points and having a gradient and a base value; 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 gradient of the segment, and
a binary adder configured to add the 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 break points,

wherein each of the break points has a minimum extended Hamming weight which is less than or equal to a threshold value.

Assignees

• Imagination Tech Ltd

Inventors

• Lee Tim

Classifications

• G06F7/556

  Logarithmic or exponential functions · CPC title

• G06F17/17 Primary

  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 title

• G06F7/544

  for evaluating functions by calculation {(G06F7/4824 takes precedence)} · CPC title

• G06F7/523 Primary

  Multiplying only · CPC title