Digital Implementation of Fractional Exponentiation

• US 20070282936A1
• Filed: 05/31/2006
• Published: 12/06/2007
• Est. Priority Date: 05/31/2006
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Via Telecom Co., Ltd.
• Inventors: Tandon, Tarun K., Kang, Insung, Manzella, Vic
• Granted Patent: US 7,644,116 B2
• Time in Patent Office: Days
• US Class Current: 708/277
• CPC Class Codes: G06F 7/556 Logarithmic or exponential functions

Abstract

Provided are digital processing apparatuses and techniques for estimating the fractional exponentiation of the base number 2, i.e., 2^f where f is a fractional value. In one representative embodiment, a calculation is made of a folded quantity, which is equal to 1−f if f is greater than a specified threshold and is equal to f otherwise; then, a function of the folded quantity is calculated; and finally, the function of the folded quantity is subtracted from the fraction f and 1 is added. In another embodiment, 2^f is approximated by calculating 1+f′ in the binary numbering system.

Claims

1. A digital processing apparatus configured to approximate a fractional exponentiation of the base number 2, comprising:

(a) an input section configured to obtain a fraction f that is expressed in a binary numbering system; and

(b) a processing section, coupled to the input section and configured to approximate 2^f in the binary numbering system, comprising;

(i) folding means for calculating a folded quantity, which is equal to 1−

f if f is greater than a specified threshold and is equal to f otherwise;

(ii) function means for calculating a function of the folded quantity; and

(iii) subtraction means for subtracting the function of the folded quantity from the fraction f and adding 1.

2. A digital processing apparatus according to claim 1, wherein the function means comprises division means for dividing the folded quantity solely by (i) truncating a specified number of least-significant bits of the folded quantity or (ii) right-shifting a specified argument.

3. A digital processing apparatus according to claim 2, wherein the function means further comprises means for limiting an output of the division means to a maximum value.

4. A digital processing apparatus according to claim 3, wherein the maximum value has been selected so as to reduce approximation error, such that positive approximation errors are equal to an absolute value of negative approximation errors.

5. A digital processing apparatus according to claim 2, wherein each of the specified number and the specified argument is less than 5.

6. A digital processing apparatus according to claim 1, wherein the specified threshold is equal to ½

.

7. A digital processing apparatus according to claim 1, wherein the processing section further comprises means for estimating an arctangent based on the approximation of 2^f, and wherein the arctangent is estimated as tan⁻

1(f)≅

f·

α

−

(2^f−

1), where α

=2·

Q(0.8816) and Q(0.8816) is the appropriately quantized value of 0.8816 in a desired digital precision.

8. A digital processing apparatus according to claim 1, wherein said folding means, function means and subtraction means collectively comprise means for approximating 2^f by calculating 1+f′

in the binary numbering system, and wherein f′

is determined as a piecewise linear approximation of 2^f−

1 consisting of a plurality of linear segments, with each linear segment having a slope that is defined by

$\underset{j=0}{\overset{J-1}{\sum <br><br>}}<br><br><br><br>k_j·<br><br>2^{-j},$

where J is an arbitrary positive integer, each k_j has a value of −

1, 0 or +1, and the total number of nonzero k_j, across all segments, is less than 5.

9. A method for use in approximating a fractional exponentiation of the base number 2, comprising:

(a) inputting a fraction f represented in base 2 by N bits;

(b) inputting the N−

1 least-significant bits of the fraction f into an inverter;

(c) inputting a value of the most-significant bit of the fraction f into a multiplexer to select either (i) the N−

1 least-significant bits of the fraction for (ii) the inverted N−

1 least-significant bits of the fraction f output from the inverter, thereby obtaining a selected quantity;

(d) inputting the most-significant bit of the fraction f and the selected quantity into an adder, thereby obtaining a folded quantity;

(e) inputting the folded quantity into a truncator that truncates a specified number of least-significant bits, thereby obtaining a truncated quantity;

(f) inputting the truncated quantity into a thresholding component that takes a minimum of the truncated quantity and a specified value E_max, thereby obtaining a value of E; and

(g) inputting E and the fraction f into a subtractor that computes f−

E.

10. The method of claim 9, further comprising a step of appending a most-significant bit of 1 to an output of the subtractor, thereby obtaining an approximation of 2^f.

11. The method of claim 9, wherein the specified value E_max has been selected so as to reduce approximation error, such that positive approximation errors are equal to an absolute value of negative approximation errors.

12. The method of claim 9, wherein the specified number is less than 5.

13. The method of claim 9, further comprising:

(h) inputting an output of the subtractor and a value α

*f, where α

is a predetermined constant, into a second subtractor that computes a difference between α

*f and the output of the subtractor, thereby obtaining an approximation of arctan(f).