Field of the invention
The present invention mainly relates to a logarithmic calculation and more particularly to a method for calculation of logarithmic value of any number represented in the fixed point format.
Background of the invention
The logarithm values are one of the most preferred forms ofrepresentations in various fields, especially in the areas of real time digital signal processing and image processing, for representing important parameters. The common methods used for the calculation of logarithms include the popular look-up table method, CORDIC, Taylor series expansion, etcetera. These methods are limited either due to the huge size of the look-up table involved (ex-look-up table method) or due to the complexity of the algorithm involved or reduced throughput. The size of the look-up table limits the input data width and hence the resolution of the calculation suffers. The platforms such as FPGA may end up using a lot of precious resources for this purpose. Hence, it is not suitable for a very high-resolution input that stretches up to 80-90 bit widths inputs and more. Both the factors mentioned here restrict the effectiveness of the aforementioned techniques by limiting the speed of operation (throughput), resource optimization and accuracy.
For example, document US5363321 titled “Digital circuit for calculating a logarithm of a number” describes a digital circuit that computes the logarithm of a number. The circuit makes the computation by first determining a multiplicity of factors fi from a predetermined set of factors such that the product of the multiplicity of factors fi and the number equals the base of the logarithm. A memory stores the logarithms of all the numbers in the predetermined set. The circuit then looks-up and sums the logarithms of the multiplicity of factors fi, and then subtracts the sum from one to yield the logarithm of the number.
Another, document US6587070 titled “Digital base-10 logarithm converter”uses the most significant bit of the binary number, which represents a base 2 logarithmic integer component of the number. A selects a predetermined number of bits to follow the base 2 integer Component is determined by the Priority encoder, the predetermined number of bits representing a base logarithmic fractional component following the integer component of the input binary signal. An adder combines the integer component with the fractional component to thereby output a base 2 logarithmic value of the input binary signal. A multiplier divides the base 2 logarithmic value of the input binary signal by a base 2 logarithmic value of 10 to thereby output a base 10 logarithmic value of the input binary Signal.
Further, document US8510360 titled “Calculating large precision common logarithms” describes the calculation of large precision common logarithms using addition and/ or subtraction of known logarithm values. Logarithms of real numbers are stored within character arrays, where each element of the array corresponds to a digit in the real number.
Therefore there is a need in the art with a method for calculation of logarithmic value of any number represented in the fixed point format and to solve the above mentioned limitations.
Summary of the Invention
An aspect of the present invention is to address at least the above-mentioned problems and/or disadvantages and to provide at least the advantages described below.
Accordingly, an aspect of the present invention is to provide acircuit for performing base 10 logarithmic calculations of a binary signal in a digital system to optimize system performance. The circuit including a priority encoder for determining a most significant bit position of the binary signal, the most significant bit (MSB) representing a base 2 logarithmic integer component of the input binary signal, an address extractor for extracting a predetermined number of bits to follow the base 2 logarithmic integer component determined by the priority encoder, wherein the predetermined number of bits serve as the address of the look up table that houses values corresponding to the base 10 log value of the decimal equivalent of the predetermined number of bits and an adder for combining the integer component of the priority encoder output with the fractional component of the lookup table output, to thereby output a base 10 logarithmic value of the input binary signal.
In another aspect of the present invention provides a method of calculating base 10 logarithmic values of a binary signal in a digital system to optimize system performance. The method including determining a most significant bit position of the binary signal, the most significant bit (MSB) representing a base 2 logarithmic integer component of the input binary signal, extracting 12 bits to follow the base 2 logarithmic integer component, wherein the 12 bits serve as the address of the look up table that houses values corresponding to the base 10 log value of the decimal equivalent of the predetermined number of bits and adding the integer component with the fractional component to thereby output a base 10 logarithmic value of said binary signal.
Other aspects, advantages, and salient features of the invention will become apparent to those skilled in the art from the following detailed description, which, taken in conjunction with the annexed drawings, discloses exemplary embodiments of the invention.
Brief description of the drawings
The above and other aspects, features, and advantages of certain exemplary embodiments of the present invention will be more apparent from the following description taken in conjunction with the accompanying drawings in which:
Figure 1 shows a block diagram of efficient method for logarithmic calculation according to one embodiment of the present invention.
Figure 2 shows flowchart of efficient method for logarithmic calculation according to one embodiment of the present invention.
Persons skilled in the art will appreciate that elements in the figures are illustrated for simplicity and clarity and may have not been drawn to scale. For example, the dimensions of some of the elements in the figure may be exaggerated relative to other elements to help to improve understanding of various exemplary embodiments of the present disclosure.
Throughout the drawings, it should be noted that like reference numbers are used to depict the same or similar elements, features, and structures.
Description of the invention
The following description with reference to the accompanying drawings is provided to assist in a comprehensive understanding of exemplary embodiments of the invention as defined by the claims and their equivalents. It includes various specific details to assist in that understanding but these are to be regarded as merely exemplary. Accordingly, those of ordinary skill in the art will recognize that various changes and modifications of the embodiments described herein can be made without departing from the scope and spirit of the invention. In addition, descriptions of well-known functions and constructions are omitted for clarity and conciseness.
The terms and words used in the following description and claims are not limited to the bibliographical meanings, but, are merely used by the inventor to enable a clear and consistent understanding of the invention. Accordingly, it should be apparent to those skilled in the art that the following description of exemplary embodiments of the present invention are provided for illustration purpose only and not for the purpose of limiting the invention as defined by the appended claims and their equivalents.
It is to be understood that the singular forms “a,” “an,” and “the” include plural referents unless the context clearly dictates otherwise.
The present methodology aims to improve the logarithmic calculations used in many applications by practically extending the throughput to the data rate of the input. The resources utilized are limited only to a 12 bit look up table and a priority encoder for fine and coarse approximations respectively. These two approximations are combined to achieve reasonably accurate logarithm values of the data. The method is very expedient because of its simplicity and ease of implementation both in software or hardware.
The present invention method enables the user to do logarithmic calculation in a single clock, making the use of this circuitry ideal for real time signal processing involved in various radars such as Weather Radars, Surveillance radars etcetera.
The present invention provides a method or a circuit or a system for performing base10 logarithm is composed mainly of:a.) A priority encoder for determining first approximation of log10 of given number, b.) A 12 bit look up table to estimate the error introduced in priority encoder approximation by an address extractor, c.) Adder for combining priority encoder output and look up table output and to thereby output a base 10 logarithm value of given number. The priority encoder gives the approximated value of logarithm of base 10 of given number based on position of first high bit with respect to MSB bit of binary equivalent of given number. The 12 bit look up table reduces approximation error of priority encoder of up to 4 significant digits when compared to actual logarithm value for the input that is represented in fixed point format. The look up table can be increased to any number of bits based on the accuracy requirement and resource available for computation. The priority encoder, look up table and adder operate in parallel and hence the entire calculation can be done in a single clock, making the use of this circuitry ideal for real time signal processing. The method enables the usage of minimum of minimum resources.
Now referring to Figure 1 which shows a block diagram of efficient method for logarithmic calculation according to one embodiment of the present invention.
The present disclosure relates to a method for efficient calculation of base 10 logarithmic value of any number represented in the fixed point format using a digital circuitry that involves a priority encoder, a 12 bit look up table and an adder. The fixed point format can be easily obtained by normalizing the digital input (data) using the maximum bit width. The method makes use of this format of digital data representation to estimate coarse value of the logarithm using a priority encoder. The first bit from the MSB (leaving sign bit) which is logic high,’1’, serves to determine a coarse approximation for the logarithm of the input data. The position of this bit relative to the length of the data and its associated decimal equivalent serves as the argument of the priority encoder that gives the logarithm of this value as the first approximation or the coarse value(X).For example, if the 3rd bit from MSB (leaving sign bit) is high while all other bits to the left of the 3rd bit is zero, we will use this bit(m=3) and the log equivalent of this bit as the coarse approximation or as X(= -mlog102).
Figure 2 shows flowchart of efficient method for logarithmic calculation according to one embodiment of the present invention.
The figure shows the flowchart of efficient method for logarithmic calculation. The encoder stores the log value corresponding to the MSB that is logic ‘1’. The next 12 bits from the first high bit used for coarse approximation will be used for fine approximations. These bits serve as the address of the look up table that houses values corresponding to the base 10 log value of the decimal equivalent of the 12 bits. For example, if the 12 bits happen to be “111100000001” (=3841). Then 3841 will be the address of the look up table that stores the value Y= log10n, where n=1+b11*2-1+b10*2-2+.......+b0*2-12, corresponding to their representation in the fixed point format. An important point to note here is that we have considered only 12 bits and not more. Strictly speaking, the choice of size of the look up table is dependent on the application that is employed. Nevertheless, we found that the 12 bits are good enough for high precision application.
Let us consider a number A=0.46893214. Equivalent binary (32 bit) for this value is "00111100000001011111011111100110".Since 2nd bit from MSB(leaving sign bit) is high hence m for this value is equal to 2, so using the above method X= -0.60205999132.Now from the above method address for look up table would be "111000000010" which will have value equal to log10(1+2-1+2-2+2-3+2-11). So Y=+0.27311435486. Finally adder will add X & Y and log10 (A) is thereby calculated as -0.32894563646 using the circuit described above. The actual value for log10 (A) = - 0.32889000026.The error in calculation is 0.0000556362, i.e., the calculation is correct to 4 significant digits after the decimal point which is very accurate for high resolution applications. Although the example above is of a 32 bit number, the data width can be as high as 90 bits which is very high for even a high resolution application requirement.
The accuracy can be further improved by using a bigger look-up table. For example, with a 16 bit look up table the accuracy is true up to 6 significant digits after the decimal point. Further accurate values are obtained if instead of saving log10(1+address) in the look up table , the value for both the coarse and fine data is multiplied by a constant factor ‘c’, where ‘c’ can be 2n. The choice of constant in the powers of two is especially useful with respect to digital domain such as FPGAs where multiplication and division by such numbers is equivalent to bit shifts in right and left respectively.The entire process can be accomplished in a single clock cycle, with a latency of two clock cycles, which makes it ideal for real time processing.
The invention makes it very expedientfor real time applications such as in Radar Signal Processing to estimate the strength of return echoes. The circuit can be realized easily in the hardware because of the simplicity of the methodology. The timing of the operation can be managed using a clock input to the components shown in figure. The clock makes enables the stabilization of the digital circuit and prevents glitches at the output, in addition to limiting the speed of operation. The logarithm using the above methodology can also be implemented in an FPGA environment which introduces added flexibility to the design and saves much needed hardware space thus enabling the miniaturization of the design.
The present invention is more advantageous than some of the more complex techniques available because of the simplicity of the design and the minimal usage of the resources. Hence the critical resources usage is less. The simplicity of design allows higher order timing constraints and thus the design is stable even at higher frequencies.
Those skilled in this technology can make various alterations and modifications without departing from the scope and spirit of the invention. Therefore, the scope of the invention shall be defined and protected by the following claims and their equivalents.
FIGS. 1-2 are merely representational and are not drawn to scale. Certain portions thereof may be exaggerated, while others may be minimized. FIGS. 1-2 illustrate various embodiments of the invention that can be understood and appropriately carried out by those of ordinary skill in the art.
In the foregoing detailed description of embodiments of the invention, various features are grouped together in a single embodiment for the purpose of streamlining the disclosure. This method of disclosure is not to be interpreted as reflecting an intention that the claimed embodiments of the invention require more features than are expressly recited in each claim. Rather, as the following claims reflect, inventive subject matter lies in less than all features of a single disclosed embodiment. Thus, the following claims are hereby incorporated into the detailed description of embodiments of the invention, with each claim standing on its own as a separate embodiment.
It is understood that the above description is intended to be illustrative, and not restrictive. It is intended to cover all alternatives, modifications and equivalents as may be included within the spirit and scope of the invention as defined in the appended claims. Many other embodiments will be apparent to those of skill in the art upon reviewing the above description. The scope of the invention should, therefore, be determined with reference to the appended claims, along with the full scope of equivalents to which such claims are entitled. In the appended claims, the terms “including” and “in which” are used as the plain-English equivalents of the respective terms “comprising” and “wherein,” respectively. ,CLAIMS:We Claim:
1. A circuit for performing base 10 logarithmic calculations of a binary signal in a digital system to optimize system performance, the circuit comprising:
a priority encoder for determining a most significant bit position of the binary signal, the most significant bit (MSB) representing a base 2 logarithmic integer component of the input binary signal;
an address extractor for extracting a predetermined number of bits to follow the base 2 logarithmic integer component determined by the priority encoder, wherein the predetermined number of bits serve as the address of the look up table that houses values corresponding to the base 10 log value of the decimal equivalent of the predetermined number of bits; and
an adder for combining the integer component of the priority encoder output with the fractional component of the lookup table output, to thereby output a base 10 logarithmic value of the input binary signal.

2. The circuit as claimed in claim 1, wherein the predetermined number of bits is 12 bits.

3. The circuit as claimed in claim 1, wherein the 12 bit look up table is to estimate the error introduced in priority encoder approximation.

4. The circuit as claimed in claim 1, further comprising a bit shifter for shifting the base 2 logarithmic integer component by a predetermined number of bits.
5. The circuit of claim 1, wherein the look-up table for determining an optimum bit value for the decimal selector by referencing number of bits versus offset value calculated data.
6. The circuit as claimed in claim 1, wherein the priority encoder, the lookup table and the adder are operated in parallel in a single clock which makes the circuitry ideal for real time signal processing.
7. A method of calculating base 10 logarithmic values of a binary signal in a digital system to optimize system performance, the method comprising:
determining a most significant bit position of the binary signal, the most significant bit (MSB) representing a base 2 logarithmic integer component of the input binary signal;
extracting 12 bits to follow the base 2 logarithmic integer component, wherein the 12 bits serve as the address of the look up table that houses values corresponding to the base 10 log value of the decimal equivalent of the predetermined number of bits; and
adding the integer component with the fractional component to thereby output a base 10 logarithmic value of said binary signal.
8. The method as claimed in claim 7, wherein the step of determining gives the approximated value of logarithm of base 10 of given number on position of first high bit with respect to MSB bit of binary equivalent of given number.
9. The method as claimed in claim 7, wherein 12 bit lookup table reduces approximation error in determining MSB of up to 4 significant digits, and wherein the look up table can be increased to any number of bits based on the accuracy requirement and resource available for computation.
10. The method as claimed in claim 7, wherein the circuitry enables the usage of minimum of minimum resources.