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

• US 10,037,306 B2
• Filed: 09/01/2016
• Issued: 07/31/2018
• Est. Priority Date: 09/01/2016
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Lin, Dexu, Liao, Edward, Majumdar, Somdeb, Lamb, Aaron, Chatha, Karamvir
• Primary Examiner(s): Mai, Tan V.
• Application Number:
  US15/255,015
• Publication Number:
  US 20180060278A1
• Time in Patent Office: 698 Days
• Field of Search: 708270-277
• 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 2207/5354 Using table lookup, e.g. for digit selection in division by digit recurrence
• CPC Class Codes: G06F 7/544 for evaluating functions by calculation G06F7/4824 takes precedence
• CPC Class Codes: G06N 3/048 Activation functions
• CPC Class Codes: G06N 3/063 using electronic means

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).

Claims

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

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

, where n=pm,

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ⁿ, 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ⁿ.

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₂ 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

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

, where n=pm,

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ⁿ, and 2^nβ

, and the at least one processor determines the value for y(x) by determining the value for 2^nβ

associated with the at least one of n or 2ⁿ.

29. The apparatus of claim 26, wherein z(x)=z^β

, z∈

(1.0, 2.0^p), p is an integer.

30. The apparatus of claim 29, wherein the second look-up table provides a mapping between z and z^β

, and the at least one processor determines the value for z(x) by determining the value for z^β

associated with z.

31. The apparatus of claim 17, wherein the input variable x is a positive real number.

32. The apparatus of claim 17, wherein ƒ

(x)=y(x)+z(x), the non-linear function ƒ

(x) is equal to log₂ x, where x>

0.

33. An apparatus for computing a non-linear function ƒ

(x) for an input variable x, where ƒ

(x)=g(y(x),z(x), comprising;

means for determining an integer n by determining a position of a most significant bit (MSB) of the input variable x;

means for determining a value for y(x) based on a first look-up table and the determined integer n;

means for determining a value for z(x) based on n and the input variable x, and based on a second look-up table; and

means for computing ƒ

(x) based on the determined values for y(x) and z(x).

34. The apparatus of claim 33, 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.

35. The apparatus of claim 34, 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.

36. The apparatus of claim 35, wherein the means for determining the integer n further configured to:

determine a position of a decimal point in the binary representation of the input variable x;

determine the position of the MSB of the binary representation of the input variable x; and

determine a number t as being a number of numeral digits between the position of the MSB and the position of the decimal point.

37. The apparatus of claim 36, wherein the means for determining the integer n further configured to determine n as

38. The apparatus of claim 37, wherein y(x)=2^nβ

, where n=pm,

39. The apparatus of claim 34, wherein the means for determining the value for z(x) based on n further configured to:

move a decimal point in the binary representation of the input variable x by n positions to the left to determine z; and

look up z(x) in the second look-up table based on the determined z.

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

41. The apparatus of claim 33, further comprising means for receiving a value for the input variable x via an input device.

42. The apparatus of claim 33, 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.

43. The apparatus of claim 42, wherein y(x)=2^nβ

.

44. The apparatus of claim 43, wherein the first look-up table provides a mapping between at least one of n or 2ⁿ, and 2^nβ

, and the means for determining the value for y(x) further configured to determine the value for 2^nβ

associated with the at least one of n or 2ⁿ.

45. The apparatus of claim 42, wherein z(x)=z^β

, z∈

(1.0, 2.0^p), p is an integer.

46. The apparatus of claim 45, wherein the second look-up table provides a mapping between z and z^β

, and the means for determining the value for z(x) further configured to determine the value for z^β

associated with z.

47. The apparatus of claim 33, wherein the input variable x is a positive real number.

48. The apparatus of claim 33, wherein ƒ

(x)=y(x)+z(x), the non-linear function ƒ

(x) is equal to log₂ x, where x>

0.

49. A computer-readable medium storing computer executable code for execution on at least one processor, comprising code to:

determine an integer n by determining a position of a most significant bit (MSB) of an 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 a non-linear function ƒ

(x)=g(y(x),z(x)) based on the determined values for y(x) and z(x).