Circuits and methods for implementing approximations to logarithms

• US 20040122878A1
• Filed: 12/24/2002
• Published: 06/24/2004
• Est. Priority Date: 12/24/2002
• Status: Active Grant

• Current Assignee: Lockheed Martin Corporation (Martin Marietta Corporation)
• Original Assignee: Lockheed Martin Corporation (Martin Marietta Corporation)
• Inventors: George, Richard V.
• Granted Patent: US 7,266,576 B2
• Time in Patent Office: Days
• US Class Current: 708/290
• CPC Class Codes: G06F 1/0307 Logarithmic or exponential functions G06F1/0314, G06F1/035 take precedence
• CPC Class Codes: G06F 7/483 Computations with numbers represented by a non-linear combination of denominational numbers, e.g. rational numbers, logarithmic number system or floating-point numbers G06F7/4806, G06F7/4824, G06F7/49, G06F7/491, G06F7/544 take precedence
• CPC Class Codes: G06F 7/556 Logarithmic or exponential functions

Abstract

A method for approximating a base 2 logarithm of a binary input and the circuit to implement the method are disclosed. The circuit comprises means for determining the integer portion of the logarithm, a lookup table module, a residual function module, an adder module and a register. This circuit performs the approximation in one system clock cycle time.

Claims

1. A method of approximating a base 2 logarithm of a binary input, the binary input comprised of a first binary number of bits, the method comprising the steps of:

partitioning the binary input into at least two partitions, each one of said at least two partitions comprised of a second binary number of bits, said second binary number being smaller than said first binary number of bits;

determining a most significant one of said at least two partitions;

determining an integer part of the approximation;

providing as input to a lookup table a binary representation of the bits in said second binary number of bits corresponding to said most significant one of said partitions;

obtaining an output from the lookup table, said output being a binary representation of a mantissa for the logarithm of base 2 of the input to the lookup table;

determining a second most significant one of said at least two partitions;

obtaining a third binary number by appending of portion of a binary representation of the bits in said second binary number of bits corresponding to the partition to the right of the second most significant one of said at least two partitions;

obtaining a residual binary output from shifting said third binary number by a shift determined by said integer portion of the base 2 logarithm of the binary input; and

,

adding the residual binary output to the output from the lookup table to obtain the mantissa of the approximation to the base 2 logarithm of the binary input;

whereby in said method a group of steps producing the lookup table output and a group of steps resulting in said residual binary output operate concurrently and there are no dependencies between the two groups of steps.

2. The method of claim 1 wherein the step of determining the integer part of the approximation comprises the step of:

determining from a binary representation of an indicator of placement of the most significant one of said partitions and from a binary representation of the binary bits in said second binary number of bits corresponding to said most significant one of said partitions, the integer part of the approximation.

3. The method of claim 1 wherein the first binary number of bits is 16, the partitions are comprised of nibbles, and the shift utilized in obtaining the residual binary output comprises a shift determined by bit 1 and bit 0 of the integer portion of the base 2 logarithm of the binary input.

4. The method of claim 2 wherein the first binary number of bits is 16, the partitions are comprised of nibbles, and the shift utilized in obtaining the residual binary output comprises a shift determined by bit 1 and bit 0 of the integer portion of the base 2 logarithm of the binary input.

5. A system for approximating a base 2 logarithm of a binary input, the binary input comprised of a first binary number of bits, the binary input capable of being expressed in terms of at least two partitions, said system comprising:

means for providing, from the binary input, an integer portion of the base 2 logarithm of said binary input;

a lookup table module receiving the binary input and a most significant part of said integer portion of the base 2 logarithm of the binary input;

a residual function module receiving the binary input and said integer portion of the base 2 logarithm of the binary input;

an adder function module receiving the output of the lookup table and the output of the residual function module and providing an output, said output of said adder function module comprising a mantissa of the approximation to the base 2 logarithm of the binary input; and

,

a clocked register receiving the integer portion of the base 2 logarithm of the binary input and the mantissa of the approximation to the base 2 logarithm of the binary input.

6. The system of claim 5 wherein said lookup table receives said binary input and a pointer to a most significant one of said partitions of the binary input and wherein said pointer is obtained from the most significant part of said integer portion of the base 2 logarithm of the binary input.

7. The system of claim 5 wherein said means for providing the integer portion of the base 2 logarithm comprise a scalar priority encoder and wherein said approximation is performed in one system clock cycle time.

8. The system of claim 5 the first binary number of bits is 16, the partitions are comprised of nibbles, the residual function module comprises a shift and said shift is determined by bit 1 and bit 0 of the integer portion of the base 2 logarithm of the binary input.

9. The system of claim 7 the first binary number of bits is 16, the partitions are comprised of nibbles, the residual function module comprises a shift and said shift is determined by bit 1 and bit 0 of the integer portion of the base 2 logarithm of the binary input.

10. A system for approximating a base 2 logarithm of a binary input, the binary input comprised of a first binary number of bits, the system comprising:

at least one processing sub-system; and

,

at least one computer usable memory having computer readable code embodied therein capable of causing the at least one processing sub-system to;

partition the binary input into at least two partitions, each one of said at least two partitions comprised of a second binary number of bits, said second binary number being smaller than said first binary number of bits;

determine a most significant one of said at least two partitions;

determine an integer part of the approximation;

provide as input to a lookup table a binary representation of the bits in said second binary number of bits corresponding to said most significant one of said partitions;

obtain an output from the lookup table, said output being a binary representation of a mantissa for the logarithm of base 2 of the input to the lookup table;

determine a second most significant one of said at least two partitions;

obtain a third binary number by appending of portion of a binary representation of the bits in said second binary number of bits corresponding to the partition to the right of the second most significant one of said at least two partitions;

obtain a residual binary output from shifting said third binary number by a shift determined by said integer portion of the base 2 logarithm of the binary input; and

,

add the residual binary output to the output from the lookup table to obtain the approximation to the mantissa of the base 2 logarithm of the binary input;

wherein the approximation to the base 2 logarithm of the binary input comprises said integer portion and said approximation to the mantissa.

11. The system of claim 10 where, in determining the integer part of the approximation, the computer readable code is capable of causing the at least one processing sub-system to:

determine from a binary representation of an indicator of placement of the most significant one of said partitions and from a binary representation of the binary bits in said second binary number of bits corresponding to said most significant one of said partitions, the integer part of the approximation.

12. The system of claim 11 wherein the at least one processing sub-system comprises at least one processing system having a substantially symmetrical architecture and wherein said computer readable code is capable of causing the at least one processing sub-system to perform the approximation in a minimal number of system clock cycle times.

13. The system of claim 10 wherein the first binary number of bits is 16, the partitions are comprised of nibbles, and the shift utilized in obtaining the residual binary output comprises a shift determined by bit 1 and bit 0 of the integer portion of the base 2 logarithm of the binary input.

14. The system of claim 11 wherein the first binary number of bits is 16, the partitions are comprised of nibbles, and the shift utilized in obtaining the residual binary output comprises a shift determined by bit 1 and bit 0 of the integer portion of the base 2 logarithm of the binary input.

15. The system of claim 12 wherein the first binary number of bits is 16, the partitions are comprised of nibbles, and the shift utilized in obtaining the residual binary output comprises a shift determined by bit 1 and bit 0 of the integer portion of the base 2 logarithm of the binary input.