Logarithmic Number System
Encyclopedia
A logarithmic number system (LNS) is an arithmetic system used for representing real numbers in computer and digital hardware, especially for digital signal processing
.
, is represented by the logarithm
,
, of its absolute value
as follows:
where
is a bit denoting the sign of 
(
if 
and 
if 
).
The number
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.
On the other hand, the operations of addition and subtraction are more complicated and they are calculated by the formula:
where
is the difference between the logarithms of the operands, the "sum" function is 
, and the "difference" function is 
. These functions 
and 
, depicted in the figures to the right, 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 LNS primarily for increasing the precision of floating-point math operations.
and floating-point number systems.
Kingsbury and Rayner introduced "logarithmic arithmetic" for digital signal processing
in 1971.
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.
Lee and Edgar described a similar system, which they called the "focus" number system, in 1977.
The mathematical foundations for addition and subtraction in an LNS trace back to Carl Friedrich Gauss
and Z. Leonelli.
(GRAPE) special-purpose supercomputer that won the Gordon Bell Prize
in 1999. LNS is commonly used as part of hidden Markov models, such as the Viterbi algorithm
, with applications in speech recognition and DNA sequencing.
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). 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.
LNS is sometimes used in FPGA-based applications where most arithmetic operations are multiplication or division.
Digital signal processing
Digital signal processing is concerned with the representation of discrete time signals by a sequence of numbers or symbols and the processing of these signals. Digital signal processing and analog signal processing are subfields of signal processing...
.
Theory
In LNS, a number,, is represented by the logarithmLogarithm
The logarithm of a number is the exponent by which another fixed value, the base, has to be raised to produce that number. For example, the logarithm of 1000 to base 10 is 3, because 1000 is 10 to the power 3: More generally, if x = by, then y is the logarithm of x to base b, and is written...
,
, of its absolute valueAbsolute value
In mathematics, the absolute value |a| of a real number a is the numerical value of a without regard to its sign. So, for example, the absolute value of 3 is 3, and the absolute value of -3 is also 3...
as follows:
where
is a bit denoting the sign of ( if and if ).The number
is represented by a binary word which usually is in the two's complementTwo's complement
The two's complement of a binary number is defined as the value obtained by subtracting the number from a large power of two...
format. LNS can be considered as a floating-point number with the significand
Significand
The significand is part of a floating-point number, consisting of its significant digits. Depending on the interpretation of the exponent, the significand may represent an integer or a fraction.-Examples:...
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.
On the other hand, the operations of addition and subtraction are more complicated and they are calculated by the formula:
where
is the difference between the logarithms of the operands, the "sum" function is , and the "difference" function is . These functions and , depicted in the figures to the right, 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 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-pointFixed-point arithmetic
In computing, a fixed-point number representation is a real data type for a number that has a fixed number of digits after the radix point...
and floating-point number systems.
Kingsbury and Rayner introduced "logarithmic arithmetic" for digital signal processing
Digital signal processing
Digital signal processing is concerned with the representation of discrete time signals by a sequence of numbers or symbols and the processing of these signals. Digital signal processing and analog signal processing are subfields of signal processing...
in 1971.
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.
Lee and Edgar described a similar system, which they called the "focus" number system, in 1977.
The mathematical foundations for addition and subtraction in an LNS trace back to Carl Friedrich Gauss
Carl Friedrich Gauss
Johann Carl Friedrich Gauss was a German mathematician and scientist who contributed significantly to many fields, including number theory, statistics, analysis, differential geometry, geodesy, geophysics, electrostatics, astronomy and optics.Sometimes referred to as the Princeps mathematicorum...
and Z. Leonelli.
Applications
LNS has been used in the Gravity PipeGravity Pipe
Gravity Pipe, otherwise known as GRAPE, is a project which uses hardware acceleration to perform gravitational computations. Integrated with Beowulf-style commodity computers, the GRAPE system calculates the force of gravity that a given mass, such as a star, exerts on others...
(GRAPE) special-purpose supercomputer that won the Gordon Bell Prize
Gordon Bell Prize
The Gordon Bell Prizes are a set of awards awarded by the Association for Computing Machinery in conjunction with the Institute of Electrical and Electronics Engineers each year at the Supercomputing Conference to recognize outstanding achievement in high-performance computing applications...
in 1999. LNS is commonly used as part of hidden Markov models, such as the Viterbi algorithm
Viterbi algorithm
The Viterbi algorithm is a dynamic programming algorithm for finding the most likely sequence of hidden states – called the Viterbi path – that results in a sequence of observed events, especially in the context of Markov information sources, and more generally, hidden Markov models...
, with applications in speech recognition and DNA sequencing.
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). 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.
LNS is sometimes used in FPGA-based applications where most arithmetic operations are multiplication or division.