Approximating functions

Patent metadata

Field	Value
Publication number	US-9785406-B2
Application number	US-201514701818-A
Country	US
Kind code	B2
Filing date	May 1, 2015
Priority date	May 1, 2014
Publication date	Oct 10, 2017
Grant date	Oct 10, 2017

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

The invention 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 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 minimum Hamming weight of:
a binary representation of the fixed gradient;
a trinary representation of the fixed gradient; and
a representation of the fixed gradient as a product of two binary numbers, two trinary numbers, or a binary and a trinary number;

the h-1 binary adders being logically configured to perform the multiplication using the representation of the fixed gradient having that minimum Hamming weight h; and
a binary adder adapted to add a base value to one of the input and 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 each of the fixed gradients in the predetermined set of fixed gradients has a respective minimum Hamming weight, h, which is less than or equal to a threshold value, wherein the threshold value determines a limit on the number of adders that the binary multiplier is adapted to use for performing a multiplication.

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

4. A binary logic circuit as claimed in claim 1 , wherein the minimum Hamming weight h is less than or equal to 3.

5. A binary logic circuit as claimed in 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. A binary logic circuit as claimed in 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. A binary logic circuit as claimed in claim 5 , wherein each of the set of break values is used in the selection logic in the form of:
a binary representation of the break value;
a trinary representation of the break value; or
a representation of the break value as a product of two binary numbers, two trinary numbers, or a binary and a trinary number;

the form used for each break value being the representation of that break value having the minimum Hamming weight.

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

9. A binary logic circuit as claimed in claim 1 , the binary adder of each logic chain being arranged to add a respective base value to the output of the binary multiplier and, for a mathematical function expressed in the form y=f(x) with respect to Cartesian axes x and y, each linear segment represents part of a line that crosses the y axis at the base value.

10. A binary logic circuit as claimed in claim 1 , the binary adder of each logic chain being arranged to add a respective base value to the received input variable, and, for a mathematical function expressed in the form y=f(x) with respect to Cartesian axes x and y, each linear segment represents part of a line that crosses the x axis at the base value.

11. A binary logic circuit as claimed in claim 1 , wherein the mathematical function is a continuous smooth function over the predefined range.

12. A binary logic circuit as claimed in claim 1 , wherein at least one of the plurality of logic chains comprises a binary multiplier adapted to perform multiplication by a fixed gradient having a minimum hamming weight of greater than one.

13. 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:
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 adapted to perform multiplication by the selected fixed gradient of the segment using h-1 binary adders, where his the minimum Hamming weight of:
a binary representation of the fixed gradient;
a trinary representation of the fixed gradient; and
a representation of the fixed gradient as a product of two binary numbers, two trinary numbers, or a binary and a trinary number;
wherein the h-1 binary adders are logically configured to perform multiplication using the representation of the fixed gradient having the minimum Hamming weight h; and
a binary adder adapted to add the determined base value to the input or output of the binary multiplier; and
selection logic adapted 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.

14. The method of claim 13 , wherein each of the fixed gradients in the predetermined set of fixed gradients has a minimum Hamming weight, h, which is less than or equal to a threshold value, wherein the threshold value determines a limit on the number of adders that the binary multiplier is adapted to use for performing a multiplication.

15. The method of claim 14 , wherein the threshold value is 2 or 3.

16. The method of claim 13 , wherein the minimum Hamming weight h is less than or equal to 3.

17. The method of claim 13 , wherein the step of fitting the plurality of linear segments to the function over the predefined range further comprises:
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, the set of fixed gradients comprising gradients which are represented as binary representations, trinary representations and representations being the product of two binary numbers, two trinary numbers, or a binary and a trinary number.

18. The method of claim 13 , wherein the step of fitting the plurality of linear segments to the function over the predefined range further comprises 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.

19. The method of claim 13 , wherein the hardware representation is one or more of RTL, a hardware description language, and a gate-level description language.

20. A method of manufacturing a binary logic circuit comprising deriving a hardware representation of a binary logic circuit configured to approximate a mathematical function over a predefined range as a

Assignees

• Imagination Tech Ltd

Inventors

• Lee Tim

Classifications

• G06F7/523 Primary

  Multiplying only · 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/556

  Logarithmic or exponential functions · CPC title