Logarithmic number system

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

Overview

A number, ${\displaystyle X}$, is represented in an LNS by two components: the logarithm (${\displaystyle x}$) of its absolute value (as a binary word usually in two's complement), and its sign bit (${\displaystyle s}$):

${\displaystyle X\rightarrow {\begin{cases}x=\log _{b}{\big |}X{\big |}\,,\\s={\begin{cases}0{\text{ if }}X>0\,,\\1{\text{ if }}X<0\,.\end{cases}}\end{cases}}}$

An LNS can be considered as a floating-point number with the significand being always equal to 1 and a non-integer exponent. This formulation simplifies the operations of multiplication, division, powers and roots, since they are reduced down to addition, subtraction, multiplication, and division, respectively.

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

${\displaystyle \log _{b}(|X|+|Y|)=x+s_{b}(y-x)\,,}$

${\displaystyle \log _{b}{\bigg |}|X|-|Y|{\bigg |}=x+d_{b}(y-x)\,,}$

where the "sum" function is defined by ${\displaystyle s_{b}(z)=\log _{b}(1+b^{z})}$, and the "difference" function by ${\displaystyle d_{b}(z)=\log _{b}{\big |}1-b^{z}{\big |}}$. These functions ${\displaystyle s_{b}(z)}$ and ${\displaystyle d_{b}(z)}$ are also known as Gaussian logarithms.

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 an 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]

Nicholas Kingsbury and Peter Rayner introduced "logarithmic arithmetic" for digital signal processing (DSP) in 1971.^[2]

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

Samuel Lee and Albert Edgar described a similar system, which they called the "Focus" number system, in 1977.^[4][1][5][6]

The mathematical foundations for addition and subtraction in an LNS trace back to Zecchini Leonelli and Carl Friedrich Gauss in the early 1800s.^{[7][8][9][10][11]}

Applications

In the late 1800s, the Spanish engineer Leonardo Torres Quevedo conceived a series of analogue calculating mechanical machines^[12][13] and developed one that could solve algebraic equations with eight terms, finding the roots, including the complex ones. One part of this machine called an "endless spindle" allowed the mechanical expression of the relation ${\displaystyle y=\log(1+10^{x})}$,^[14] with the aim of extracting the logarithm of a sum as a sum of logarithms.

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

A substantial effort to explore the applicability of LNSs 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).^[16][17] A fabricated prototype of the processor, which has a 32-bit cotransformation-based LNS arithmetic logic unit (ALU), demonstrated LNSs as a "more accurate alternative to floating-point", with improved speed. Further improvement of the LNS design based on the ELM architecture has shown its capability to offer significantly higher speed and accuracy than floating-point as well.^[18]

LNSs are sometimes used in FPGA-based applications where most arithmetic operations are multiplication or division.^[19]

See also

• Decibel
• Subnormal number
• Tapered floating point (TFP)
• Level-index arithmetic (LI) and symmetric level-index arithmetic (SLI)
• Gaussian logarithm
• Zech's logarithm
• ITU-T G.711
• A-law algorithm
• μ-law algorithm

References

Further reading

• Muller, Jean-Michel; Scherbyna, Alexandre; Tisserand, Arnaud (February 1998). "Semi-Logarithmic Number Systems" (PDF). IEEE Transactions on Computers. 47 (2): 145–151. doi:10.1109/12.663760. ISSN 0018-9340. Archived (PDF) from the original on 2018-07-13. Retrieved 2018-07-11. Previously published in: Muller, Jean-Michel; Scherbyna, Alexandre; Tisserand, Arnaud (July 1995). "Semi-Logarithmic Number Systems". Proceedings of the 12th IEEE Symposium on Computer Arithmetic (ARITH 12). Bath, UK.
• Kahrs, Mark; Brandenburg, Karlheinz, eds. (2002) [1998]. Applications of Digital Signal Processing to Audio and Acoustics (PDF). Kluwer Academic Publishing. ISBN 0-7923-8130-0. Archived (PDF) from the original on 2018-07-07. Retrieved 2018-07-07. (NB. Describes a 13-bit LNS used in Yamaha music synthesizers during the 1980s.)
• Kremer, Hermann (2002-08-29). "Gauss'sche Additionslogarithmen feiern 200. Geburtstag". de.sci.mathematik (in German). Archived from the original on 2018-07-07. Retrieved 2018-07-07.
• Zehendner, Eberhard (Summer 2008). "Rechnerarithmetik: Logarithmische Zahlensysteme" (PDF) (Lecture script) (in German). Friedrich-Schiller-Universität Jena. Archived (PDF) from the original on 2018-07-09. Retrieved 2018-07-09. [2]
• Hayes, Brian (September–October 2009). "The Higher Arithmetic". American Scientist. 97 (5): 364–368. doi:10.1511/2009.80.364. Archived from the original on 2018-07-09. Retrieved 2018-07-09. [3]. Also reprinted in: Hayes, Brian (2017). "Chapter 8: Higher Arithmetic". Foolproof, and Other Mathematical Meditations (1 ed.). The MIT Press. pp. 113–126. ISBN 978-0-26203686-3. ISBN 0-26203686-X.
• Amir Sabbagh, Molahosseini; de Sousa, Leonel Seabra; Chip-Hong Chang, eds. (2017-03-21). Embedded Systems Design with Special Arithmetic and Number Systems (1 ed.). Springer International Publishing AG. doi:10.1007/978-3-319-49742-6. ISBN 978-3-319-49741-9. LCCN 2017934074. (389 pages)

External links

• A site that lists LNS papers
• esprit – European Logarithmic Microprocessor (formerly the 'High Speed Logarithmic Arithmetic' (HSLA) project)
• A VHDL library for LNS hardware generation
• A Short Account on Leonardo Torres’ Endless Spindle

This page was last edited on 10 December 2023, at 21:00