Signed-digit representation

In mathematical notation for numbers, signed-digit representation is a positional system with signed digits.

Signed-digit representation can be used to accomplish fast addition of integers because it can eliminate chains of dependent carries. In the binary numeral system, a special case signed-digit representation is the non-adjacent form, which can offer speed benefits with minimal space overhead.

Notation and use

Denoting the positional notation number base as $b$, every integer $a$ can be written uniquely as

$a=\sum _{i=0}^{n}d_{i}(b)^{i}$

where each digit $d_{k}$ is an integer such that $-\alpha \leq d_{k}\leq \beta$. given that $-\alpha \leq 0$ is the minimum digit value and $\beta \geq 0$ is the maximum digit value, where the leading digit $d_{n}>0$ unless $n=0$, and where the base $b=\alpha +\beta +1$. Negative-integer digits are typically represented with a bar over the digit, i.e. $-\alpha ={\bar {\alpha }}$.

Balanced form

Balanced form representations are representations where $\alpha =\beta$, or equivalently, where there are an equal number of negative and positive digits in the set of digits for the representation. Only odd bases can have balanced form representations, as when $\alpha =\beta$, $b=\alpha +\beta +1$ is always an odd number.

For example, consider the ternary numeral system with only three digits. In standard ternary, the digits are $\lbrace 0,1,2\rbrace$; however, the balanced form of ternary, balanced ternary, uses digits $\lbrace {\bar {1}},0,1\rbrace$. This convention is adopted in finite fields of odd prime order $q$:

$GF(q)=\lbrace 0,1,{\bar {1}}=-1,...\beta ={\frac {q-1}{2}},\ {\bar {\beta }}={\frac {1-q}{2}}\ |\ q=0\rbrace .$

In balanced form, truncation and rounding become the same operation.

Signed-digit decimal

Signed-digits are commonly associated with the decimal number system. The following table displays the signed-digit representations of the integers $-10\leq n\leq 10$ for base $b=10=\alpha +\beta +1$.

Decimal for minimum digit value $0\leq \alpha <b$

$\alpha =0$ (Unsigned decimal)	$\alpha =1$	$\alpha =2$	$\alpha =3$	$\alpha =4$	$\alpha =5$	$\alpha =6$	$\alpha =7$	$\alpha =8$	$\alpha =9$
$-10$	${\bar {1}}0$	${\bar {1}}0$	${\bar {1}}0$	${\bar {1}}0$	${\bar {1}}0$	${\bar {1}}0$	${\bar {1}}0$	${\bar {1}}0$	${\bar {1}}0$
$-9$	${\bar {1}}1$	${\bar {1}}1$	${\bar {1}}1$	${\bar {1}}1$	${\bar {1}}1$	${\bar {1}}1$	${\bar {1}}1$	${\bar {1}}1$	${\bar {9}}$
$-8$	${\bar {1}}2$	${\bar {1}}2$	${\bar {1}}2$	${\bar {1}}2$	${\bar {1}}2$	${\bar {1}}2$	${\bar {1}}2$	${\bar {8}}$	${\bar {8}}$
$-7$	${\bar {1}}3$	${\bar {1}}3$	${\bar {1}}3$	${\bar {1}}3$	${\bar {1}}3$	${\bar {1}}3$	${\bar {7}}$	${\bar {7}}$	${\bar {7}}$
$-6$	${\bar {1}}4$	${\bar {1}}4$	${\bar {1}}4$	${\bar {1}}4$	${\bar {1}}4$	${\bar {6}}$	${\bar {6}}$	${\bar {6}}$	${\bar {6}}$
$-5$	${\bar {1}}5$	${\bar {1}}5$	${\bar {1}}5$	${\bar {1}}5$	${\bar {5}}$	${\bar {5}}$	${\bar {5}}$	${\bar {5}}$	${\bar {5}}$
$-4$	${\bar {1}}6$	${\bar {1}}6$	${\bar {1}}6$	${\bar {4}}$	${\bar {4}}$	${\bar {4}}$	${\bar {4}}$	${\bar {4}}$	${\bar {4}}$
$-3$	${\bar {1}}7$	${\bar {1}}7$	${\bar {3}}$	${\bar {3}}$	${\bar {3}}$	${\bar {3}}$	${\bar {3}}$	${\bar {3}}$	${\bar {3}}$
$-2$	${\bar {1}}8$	${\bar {2}}$	${\bar {2}}$	${\bar {2}}$	${\bar {2}}$	${\bar {2}}$	${\bar {2}}$	${\bar {2}}$	${\bar {2}}$
$-1$	${\bar {1}}$	${\bar {1}}$	${\bar {1}}$	${\bar {1}}$	${\bar {1}}$	${\bar {1}}$	${\bar {1}}$	${\bar {1}}$	${\bar {1}}$
$0$	$0$	$0$	$0$	$0$	$0$	$0$	$0$	$0$	$0$
$1$	$1$	$1$	$1$	$1$	$1$	$1$	$1$	$1$	$-{\bar {1}}$
$2$	$2$	$2$	$2$	$2$	$2$	$2$	$2$	$1{\bar {8}}$	$-{\bar {2}}$
$3$	$3$	$3$	$3$	$3$	$3$	$3$	$1{\bar {7}}$	$1{\bar {7}}$	$-{\bar {3}}$
$4$	$4$	$4$	$4$	$4$	$4$	$1{\bar {6}}$	$1{\bar {6}}$	$1{\bar {6}}$	$-{\bar {4}}$
$5$	$5$	$5$	$5$	$5$	$1{\bar {5}}$	$1{\bar {5}}$	$1{\bar {5}}$	$1{\bar {5}}$	$-{\bar {5}}$
$6$	$6$	$6$	$6$	$1{\bar {4}}$	$1{\bar {4}}$	$1{\bar {4}}$	$1{\bar {4}}$	$1{\bar {4}}$	$-{\bar {6}}$
$7$	$7$	$7$	$1{\bar {3}}$	$1{\bar {3}}$	$1{\bar {3}}$	$1{\bar {3}}$	$1{\bar {3}}$	$1{\bar {3}}$	$-{\bar {7}}$
$8$	$8$	$1{\bar {2}}$	$1{\bar {2}}$	$1{\bar {2}}$	$1{\bar {2}}$	$1{\bar {2}}$	$1{\bar {2}}$	$1{\bar {2}}$	$-{\bar {8}}$
$9$	$1{\bar {1}}$	$1{\bar {1}}$	$1{\bar {1}}$	$1{\bar {1}}$	$1{\bar {1}}$	$1{\bar {1}}$	$1{\bar {1}}$	$1{\bar {1}}$	$-{\bar {9}}$
$10$	$10$	$10$	$10$	$10$	$10$	$10$	$10$	$10$	$-{\bar {1}}0$

Table

The following table displays the set of digits for each signed-digit representations for $\alpha \leq 5$ and $\beta \leq 5$.

Set of digits for $\alpha \leq 5$ and $\beta \leq 5$

$\alpha ,\beta$	0	1	2	3	4	5
0	$\lbrace 0\rbrace$	$\lbrace 0,1\rbrace$	$\lbrace 0,1,2\rbrace$	$\lbrace 0,1,2,3\rbrace$	$\lbrace 0,1,2,3,4\rbrace$	$\lbrace 0,1,2,3,4,5\rbrace$
1	$\lbrace {\bar {1}},0\rbrace$	$\lbrace {\bar {1}},0,1\rbrace$	$\lbrace {\bar {1}},0,1,2\rbrace$	$\lbrace {\bar {1}},0,1,2,3\rbrace$	$\lbrace {\bar {1}},0,1,2,3,4\rbrace$	$\lbrace {\bar {1}},0,1,2,3,4,5\rbrace$
2	$\lbrace {\bar {2}},{\bar {1}},0\rbrace$	$\lbrace {\bar {2}},{\bar {1}},0,1\rbrace$	$\lbrace {\bar {2}},{\bar {1}},0,1,2\rbrace$	$\lbrace {\bar {2}},{\bar {1}},0,1,2,3\rbrace$	$\lbrace {\bar {2}},{\bar {1}},0,1,2,3,4\rbrace$	$\lbrace {\bar {2}},{\bar {1}},0,1,2,3,4,5\rbrace$
3	$\lbrace {\bar {3}},{\bar {2}},{\bar {1}},0\rbrace$	$\lbrace {\bar {3}},{\bar {2}},{\bar {1}},0,1\rbrace$	$\lbrace {\bar {3}},{\bar {2}},{\bar {1}},0,1,2\rbrace$	$\lbrace {\bar {3}},{\bar {2}},{\bar {1}},0,1,2,3\rbrace$	$\lbrace {\bar {3}},{\bar {2}},{\bar {1}},0,1,2,3,4\rbrace$	$\lbrace {\bar {3}},{\bar {2}},{\bar {1}},0,1,2,3,4,5\rbrace$
4	$\lbrace {\bar {4}},{\bar {3}},{\bar {2}},{\bar {1}},0\rbrace$	$\lbrace {\bar {4}},{\bar {3}},{\bar {2}},{\bar {1}},0,1\rbrace$	$\lbrace {\bar {4}},{\bar {3}},{\bar {2}},{\bar {1}},0,1,2\rbrace$	$\lbrace {\bar {4}},{\bar {3}},{\bar {2}},{\bar {1}},0,1,2,3\rbrace$	$\lbrace {\bar {4}},{\bar {3}},{\bar {2}},{\bar {1}},0,1,2,3,4\rbrace$	$\lbrace {\bar {4}},{\bar {3}},{\bar {2}},{\bar {1}},0,1,2,3,4,5\rbrace$
5	$\lbrace {\bar {5}},{\bar {4}},{\bar {3}},{\bar {2}},{\bar {1}},0\rbrace$	$\lbrace {\bar {5}},{\bar {4}},{\bar {3}},{\bar {2}},{\bar {1}},0,1\rbrace$	$\lbrace {\bar {5}},{\bar {4}},{\bar {3}},{\bar {2}},{\bar {1}},0,1,2\rbrace$	$\lbrace {\bar {5}},{\bar {4}},{\bar {3}},{\bar {2}},{\bar {1}},0,1,2,3\rbrace$	$\lbrace {\bar {5}},{\bar {4}},{\bar {3}},{\bar {2}},{\bar {1}},0,1,2,3,4\rbrace$	$\lbrace {\bar {5}},{\bar {4}},{\bar {3}},{\bar {2}},{\bar {1}},0,1,2,3,4,5\rbrace$

Considered as a matrix, the table itself is a skew-symmetric matrix. The representations down the diagonal are the balanced form signed-digit representations, while the representations on either side of the diagonal are isomorphic to its counterpart on the other side of the diagonal by negation, where positive numbers on one side correspond to negative numbers on the other, and vice versa. When $\alpha =0$, the representation can only represent non-negative integers without the use of a sign, and when $\beta =0$, the representation can only represent non-positive integers without the use of a sign. When both $\alpha =0$ and $\beta =0$, only zero can be represented, yielding the trivial ring.

Non-uniqueness of rationals

Just as with unsigned positional number systems, when the representations are extended to rational numbers, uniqueness is lost. For example, consider signed-digit decimal with $\alpha =5$

${(0.4444\ldots )}_{10}={\frac {4}{9}}={(1.{\bar {5}}{\bar {5}}{\bar {5}}{\bar {5}}\ldots )}_{10}$

Such examples can be shown to exist by considering the greatest and smallest possible representations with integral parts 0 and 1 respectively, and then noting that they are equal.

History

Challenges in calculation stimulated early authors Colson (1726) and Cauchy (1840) to use signed-digit representation. The further step of replacing negated digits with new ones was suggested by Selling (1887) and Cajori (1928).

In 1928, Florian Cajori noted the recurring theme of signed digits, starting with Colson (1726) and Cauchy (1840). In his book History of Mathematical Notations, Cajori titled the section "Negative numerals". For completeness, Colson uses examples and describes addition (pp 163,4), multiplication (pp 165,6) and division (pp 170,1) using a table of multiples of the divisor. He explains the convenience of approximation by truncation in multiplication. Colson also devised an instrument (Counting Table) that calculated using signed digits.

Eduard Selling advocated inverting the digits 1, 2, 3, 4, and 5 to indicate the negative sign. He also suggested snie, jes, jerd, reff, and niff as names to use vocally. Most of the other early sources used a bar over a digit to indicate a negative sign for a it. Another German usage of signed-digits was described in 1902 in Klein's encyclopedia.

Other systems

There exist other signed-digit bases such that the base $b\neq \alpha +\beta +1$. A notable examples of this is Booth encoding, which has $\alpha =1$ and $\beta =1$, with digits of value $\lbrace {\bar {1}},0,1\rbrace$, but which uses a base $b=2<3=\alpha +\beta +1$. The standard binary numeral system would only use digits of value $\lbrace 0,1\rbrace$.

Note that non-standard signed-digit representations are not unique. For instance:

$0111_{2}=4+2+1=7$

$10{\bar {1}}1_{2}=8-2+1=7$

$1{\bar {1}}11_{2}=8-4+2+1=7$

$100{\bar {1}}_{2}=8-1=7$

The non-adjacent form (NAF) of Booth encoding does guarantee a unique representation for every integer value. However, this only applies for integer values. For example, consider the following repeating binary numbers in NAF,

$(0.101010\ldots )_{2}={\frac {2}{3}}=(1.0{\bar {1}}0{\bar {1}}0{\bar {1}}\ldots )_{2}$

In written and spoken language

The oral and written forms of numbers in the Punjabi language use a form of a negative numeral one written as una or un. This negative one is used to form 19, 29, …, 89 from the root for 20, 30, …, 90. Explicitly, here are the numbers:

• 19 unni, 20 vih, 21 ikki
• 29 unatti, 30 tih, 31 ikatti
• 39 untali, 40 chali, 41 iktali
• 49 unanja, 50 panjah, 51 ikvanja
• 59 unahat, 60 sath, 61 ikahat
• 69 unattar, 70 sattar, 71 ikhattar
• 79 unasi, 80 assi, 81 ikiasi
• 89 unanve, 90 nabbe, 91 ikinnaven.

Similarly, the Sesotho language utilizes negative numerals to form 8's and 9's.

• 8 robeli (/Ro-bay-dee/) meaning "break two" i.e. two fingers down
• 9 robong (/Ro-bong/) meaning "break one" i.e. one finger down

In the English language it is common to refer to times as, for example, 'seven til three', 'til' performing the negation.

See also

• Negative base
• Redundant binary representation

Notes and references

• J. P. Balantine (1925) "A Digit for Negative One", American Mathematical Monthly 32:302.
• Lui Han, Dongdong Chen, Seok-Bum Ko, Khan A. Wahid "Non-speculative Decimal Signed Digit Adder" from Department of Electrical and Computer Engineering, University of Saskatchewan.