Logarithmic number system

The $s_b(z)$ and $d_b(z)$ functions for $b = e$.

A logarithmic number system (LNS) is an arithmetic system used for representing real numbers in computer and digital hardware, especially for digital signal processing.

Theory

In LNS, a number, $X$, is represented by the logarithm, $x$, of its absolute value as follows:

$X\rightarrow\{s,x=\log_b(|X|)\},$

where $s$ is a bit denoting the sign of $X$ ($s=0$ if $X>0$ and $s=1$ if $X<0$).

The number $x$ is represented by a binary word which usually is in the two's complement format. LNS can be considered as a floating-point number with the significand being always equal to 1. This formulation simplifies the operations of multiplication, division, powers and roots, since they are reduced down to addition, subtraction, multiplication and division, respectively.

Gaussian logarithms

On the other hand, the operations of addition and subtraction are more complicated and they are calculated by the formula:

$\log_b(|X|+|Y|)=x+s_b(y-x)$

$\log_b(||X|-|Y||)=x+d_b(y-x),$

where the "sum" function is defined by $s_b(z)=\log_b(1+b^z)$, and the "difference" function by $d_b(z)=\log_b(|1-b^z|)$. These functions $s_b(z)$ and $d_b(z)$, depicted in the figures to the right, are also known as Gaussian logarithms. For natural logarithms we have the following identity with hyperbolic functions:

$s_e(z) = \ln 2 + \frac{z}{2} + \ln \left(\cosh\frac{z}{2}\right)$

$d_e(z) = \ln 2 + \frac{z}{2} + \ln \left|\sinh\frac{z}{2}\right|$

That shows, that $s_e$ has a Taylor expansion where all but the first term are rational and all odd terms except the linear one are zero.

The simplification of multiplication, division, roots, and powers is counterbalanced by the cost of evaluating these functions for addition and subtraction. This added cost of evaluation may not be critical when using LNS primarily for increasing the precision of floating-point math operations.

History

Logarithmic number systems have been independently invented and published at least three times, as an alternative to fixed-point and floating-point number systems.^[1]

Kingsbury and Rayner introduced "logarithmic arithmetic" for digital signal processing in 1971.^[2]

A similar LNS was described in 1975 by Swartzlander and Alexopoulos; rather than use two's complement notation for the logarithms, they offset them (scale the numbers being represented) to avoid negative logs.^[3]

Lee and Edgar described a similar system, which they called the "focus" number system, in 1977.^[4]

The mathematical foundations for addition and subtraction in an LNS trace back to Carl Friedrich Gauss and Z. Leonelli.^[5][6]

Applications

LNS has been used in the Gravity Pipe (GRAPE) special-purpose supercomputer^[7] that won the Gordon Bell Prize in 1999.

A substantial effort to explore the applicability of LNS as a viable alternative to floating point for general-purpose processing of single-precision real numbers is described in the context of the European Logarithmic Microprocessor (ELM).^[8] A fabricated prototype of the processor, which has a 32-bit cotransformation-based LNS arithmetic logic unit (ALU), demonstrated LNS as a "more accurate alternative to floating-point," with improved speed. Further improvement of the LNS design based on the ELM architecture has again shown its capability to offer significantly better in speed and more accurate than the floating-point.^[9]

LNS is sometimes used in FPGA-based applications where most arithmetic operations are multiplication or division.^[10]

See also

• Denormal number

References

1. S. C. Lee and A. D. Edgar (September 1979). "Addendum to "The Focus Number System"". IEEE Transactions on Computers C–28 (9): 693. doi:10.1109/TC.1979.1675442.
2. N. G. Kingsburg and P. J. W. Rayner (January 28, 1971). "Digital filtering using logarithmic arithmetic". Electronics Letters 7: 55. doi:10.1049/el:19710039.
3. E. E. Swartzlander and A. G. Alexopoulos (December 1975). "The Sign/Logarithm Number System". IEEE Transactions on Computers C–24 (12): 1238–1242. doi:10.1109/T-C.1975.224172.
4. S. C. Lee and A. D. Edgar (November 1977). "The focus number system". IEEE Transactions on Computers C–26 (11): 1167–1170. doi:10.1109/TC.1977.1674770.
5. "Logarithm: Addition and Subtraction, or Gaussian Logarithms". Encyclopædia Britannica Eleventh Edition.
6. G. Waldo Dunnington (2002). Carl Friedrich Gauss. MAA. ISBN 0-88385-547-X.
7. J. Makino and M. Taiji (1998). Scientific Simulations with Special Purpose Computers: The GRAPE Systems. Wiley. ISBN 978-0-471-96946-4.
8. J. N. Coleman, C. I. Softley, J. Kadlec, R. Matousek, M. Tichy, Z. Pohl, A. Hermanek, and N. F. Benschop (April 2008). "The European Logarithmic Microprocessor". IEEE Transactions on Computers 57 (4): 532–546. doi:10.1109/TC.2007.70791.
9. R. C. Ismail and J.N Coleman (July 2011). "ROM-less LNS". 2011 20th IEEE Symposium on Computer Arithmetic (ARITH): 43–51. doi:10.1109/ARITH.2011.15.
10. Haohuan Fu, Oskar Mencer, Wayne Luk (December 2006). "Comparing Floating-point and Logarithmic Number Representations for Reconfigurable Acceleration". IEEE Conference on Field Programmable Technology: 337. doi:10.1109/FPT.2006.270342.

External links

• A site that lists LNS papers
• A VHDL Library for LNS hardware generation