numeration system

A numeration system is a triple $N=(b,\Sigma,d)$, where $b>1$ is a positive integer, $\Sigma$ is a non-empty alphabet, and $d$ is a one-to-one function from $\Sigma$ to the set of non-negative integers $\mathbb{N}\cup\{0\}$. Order elements of $\Sigma$ so that their values are in increasing order:

$\Sigma=\{a_{1},\ldots,a_{k}\}$, where $d(a_{i}) for $i=1,\ldots,k-1$.

$b$ is called the base of numeration system $N$, and the elements $a_{1},\ldots,a_{k}$ the digits of $N$. Words over $\Sigma$ are called numeral words.

Given a numeral word $u=c_{1}\cdots c_{m}$ with $c_{j}\in\Sigma$, the integer non-negative $n$ is said to be represented by $u$ if

 $n=c_{1}b^{m-1}+\cdots+c_{j}b^{m-j}+\cdots+c_{m}.$

An integer $n$ is said to be representable in $N$ if there is a numeral word $u$ representing $n$.

Examples.

• The most common numeration system is the decimal system:

 $D=(10,\{0,1,2,3,4,5,6,7,8,9\},d)$

where $d(i)=i$ is the identity function.

• Just as common is the binary digital system: $B=(2,\{0,1\},d)$ where $d$ again is the identity function.

• In fact, any digital system is a numeration system $(n,\Sigma,d)$, where $\Sigma=\{a_{0},\ldots,a_{n-1}\}$ and $d(a_{i})=i$.

• Consider the system $B_{1}=(2,\{1\},d)$, where $d(1)=1$. Since any word over $\{1\}$ is just a string of $1$’s, $n$ consecutive strings of $1$ represent $1+2+\cdots+2^{n-1}=2^{n-1}$. We conclude that the integers representable by $N$ have the form $2^{n}-1$ for any positive integer $n$.

• Consider the system

 $D_{1}=(10,\{[0],[1],\ldots,[9],[10],[100],[1000],[10000],[10000000],[100000000% 00]\},d)$

where $d([i])=i$. It is easy to see that every integer is representable by $D_{1}$. However, some integers may be represented by more than one numeral words. For example,

 $[1000]=[100][0]=[10][0][0]=[1][0][0][0].$

The numeration system $D_{1}$ is used by the Chinese.

• Consider the system $N=(3,\{[1],[2],[4]\},d)$ where $d([i])=i$. Then $[2][1][4][1]=2\times 3^{3}+1\times 3^{2}+4\times 3+1=184$. Notice that $0$ can not be represented $N$. Also, note that $[4]=4=1\times 3+1=[1][1]$.

A numeration system $N$ is said to be complete if every non-negative integer has at least one representation in $N$; and unambiguous if every non-negative integer has at most one representation in $N$. $N$ is ambiguous if $N$ is not unambiguous. Every digital system is complete and unambiguous. In the examples above, $D_{1}$ is complete but ambiguous; $B_{1}$ is unambiguous but not complete; $N$ is neither complete nor unambiguous.

Remark. Representation non-negative integers by a numeration system can be extended to rational numbers. The corresponding concepts of completeness and ambiguity may be defined similarly.

References

• 1 A. Salomaa Computation and Automata, Encyclopedia of Mathematics and Its Applications, Vol. 25. Cambridge (1985).
 Title numeration system Canonical name NumerationSystem Date of creation 2013-03-22 18:57:46 Last modified on 2013-03-22 18:57:46 Owner CWoo (3771) Last modified by CWoo (3771) Numerical id 8 Author CWoo (3771) Entry type Definition Classification msc 11A67 Synonym numeral system Synonym number system Related topic Base3 Defines base Defines digit Defines complete numeration system Defines unambiguous numeration system Defines ambiguous numeration system