Approximation of non-linear functions in fixed point using look-up tables

Patent metadata

Field	Value
Publication number	US-10037306-B2
Application number	US-201615255015-A
Country	US
Kind code	B2
Filing date	Sep 1, 2016
Priority date	Sep 1, 2016
Publication date	Jul 31, 2018
Grant date	Jul 31, 2018

Abstract

Computing a non-linear function ƒ(x) in hardware or embedded systems can be complex and resource intensive. In one or more aspects of the disclosure, a method, a computer-readable medium, and an apparatus are provided for computing a non-linear function ƒ(x) accurately and efficiently in hardware using look-up tables (LUTs) and interpolation or extrapolation. The apparatus may be a processor. The processor computes a non-linear function ƒ(x) for an input variable x, where ƒ(x)=g(y(x),z(x)). The processor determines an integer n by determining a position of a most significant bit (MSB) of an input variable x. In addition, the processor determines a value for y(x) based on a first look-up table and the determined integer n. Also, the processor determines a value for z(x) based on n and the input variable x, and based on a second look-up table. Further, the processor computes ƒ(x) based on the determined values for y(x) and z(x).

First claim

What is claimed is:

1. A method of computing, in a processor, a non-linear function ƒ(x) for an input variable x, where ƒ(x)=g(y(x),z(x)), the method comprising:
determining an integer n by determining a position of a most significant bit (MSB) of the input variable x;
determining a value for y(x) based on a first look-up table and the determined integer n;
determining a value for z(x) based on n and the input variable x, and based on a second look-up table; and
computing ƒ(x) based on the determined values for y(x) and z(x).

2. The method of claim 1 , wherein the position of the MSB of the input variable x is the position of the MSB of a binary representation of the input variable x.

3. The method of claim 2 , wherein the position of the MSB of the binary representation of the input variable x is a position of a leading 1 in the binary representation of the input variable x.

4. The method of claim 3 , wherein the determining the integer n comprises:
determining a position of a decimal point in the binary representation of the input variable x;
determining the position of the MSB of the binary representation of the input variable x; and
determining a number t as being a number of numeral digits between the position of the MSB and the position of the decimal point.

5. The method of claim 4 , wherein the determining the integer n further comprises determining n as

n
=

⌊

t
p

⌋

·
p

,

where p≥1 and is an integer, z(x) is a function of z, and z∈(1.0, 2.0 p ).

6. The method of claim 5 , wherein y(x)=2 nβ , where n=pm,

m
=

⌊

t
p

⌋

,

β is a constant, and β∈ , is a set of real numbers.

7. The method of claim 2 , wherein the determining the value for z(x) based on n comprises:
moving a decimal point in the binary representation of the input variable x by n positions to the left to determine z; and
looking up z(x) in the second look-up table based on the determined z.

8. The method of claim 1 , wherein the value for z(x) is determined based on a binary representation of the input variable x.

9. The method of claim 1 , further comprising receiving by the processor a value for the input variable x via an input device.

10. The method of claim 1 , wherein ƒ(x)=y(x)*z(x), the non-linear function ƒ(x) is equal to x β , where x>0, β is a constant and β∈ , is a set of real numbers.

11. The method of claim 10 , wherein y(x)=2 nβ .

12. The method of claim 11 , wherein the first look-up table provides a mapping between at least one of n or 2 n , and 2 nβ , and the determining the value for y(x) comprises determining the value for 2 nβ associated with the at least one of n or 2 n .

13. The method of claim 10 , wherein z(x)=z β , z∈(1.0, 2 p ), p is an integer.

14. The method of claim 13 , wherein the second look-up table provides a mapping between z and z β , and the determining the value for z(x) comprises determining the value for 2 β associated with z.

15. The method of claim 1 , wherein the input variable x is a positive real number.

16. The method of claim 1 , wherein ƒ(x)=y(x)+z(x), the non-linear function ƒ(x) is equal to log 2 x, where x>0.

17. An apparatus for computing a non-linear function ƒ(x) for an input variable x, where ƒ(x)=g(y(x),z(x), comprising:
a memory; and
at least one processor coupled to the memory and configured to:
determine an integer n by determining a position of a most significant bit (MSB) of the input variable x;
determine a value for y(x) based on a first look-up table and the determined integer n;
determine a value for z(x) based on n and the input variable x, and based on a second look-up table; and
compute ƒ(x) based on the determined values for y(x) and z(x).

18. The apparatus of claim 17 , wherein the position of the MSB of the input variable x is the position of the MSB of a binary representation of the input variable x.

19. The apparatus of claim 18 , wherein the position of the MSB of the binary representation of the input variable x is a position of a leading 1 in the binary representation of the input variable x.

20. The apparatus of claim 19 , wherein the at least one processor determines the integer n by:
determining a position of a decimal point in the binary representation of the input variable x;
determining the position of the MSB of the binary representation of the input variable x; and
determining a number t as being a number of numeral digits between the position of the MSB and the position of the decimal point.

21. The apparatus of claim 20 , wherein the at least one processor determines the integer n by further determining n as

n
=

⌊

t
p

⌋

·
p

,

where p≥1 and is an integer, z(x) is a function of z, and z∈(1.0, 2.0 p ).

22. The apparatus of claim 21 , wherein y(x)=2 nβ , where n=pm,

m
=

⌊

t
p

⌋

,

β is a constant, and β∈ , is a set of real numbers.

23. The apparatus of claim 18 , wherein the at least one processor determines the the value for z(x) based on n by:
moving a decimal point in the binary representation of the input variable x by n positions to the left to determine z; and
looking up z(x) in the second look-up table based on the determined z.

24. The apparatus of claim 17 , wherein the value for z(x) is determined based on a binary representation of the input variable x.

25. The apparatus of claim 17 , wherein the at least one processor is further configured to:
receive a value for the input variable x via an input device.

26. The apparatus of claim 17 , wherein ƒ(x)=y(x)*z(x), the non-linear function ƒ(x) is equal to x β , where x>0, β is a constant and β∈ , is a set of real numbers.

27. The apparatus of claim 26 , wherein y(x)=2 nβ .

28. The apparatus of claim 27 , wherein the first look-up table provides a mapping between at least one of n or 2 n , and 2 nβ , and the at least one processor determines the value for y(x) by determining the value for 2 nβ associated w

Assignees

• Qualcomm Inc

Inventors

• Lin Dexu
• Liao Edward
• Majumdar Somdeb
• Lamb Aaron
• CHATHA Karamvir

Classifications

• G06N3/063

  using electronic means · CPC title

• G06F2207/5354

  Using table lookup, e.g. for digit selection in division by digit recurrence · 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

• G06N3/048

  Activation functions · CPC title