Signed-digit representation

Signed-digit representation of numbers indicates that digits can be prefixed with a − (minus) sign to indicate that they are negative.

Signed-digit representation can be used in low-level software and hardware to accomplish fast addition of integers because it can eliminate carries^[1]. In the binary numeral system one special case of signed-digit representation is the non-adjacent form which can offer speed benefits with minimal space overhead.

Balanced form

In balanced form, the digits are drawn from a range $-k$ to $(b-1)-k$ , where typically $k=\left\lfloor {\frac {b}{2}}\right\rfloor$ . For balanced forms, odd base numbers are advantageous. With an odd base number, truncation and rounding become the same operation, and all the digits except 0 are used in both positive and negative form.

A notable example is balanced ternary, where the base is $b=3$ , and the numerals have the values −1, 0 and +1 (rather than 0, 1 and 2 as in the standard ternary numeral system). Balanced ternary uses the minimum number of digits in a balanced form. Balanced decimal uses digits from −5 to +4. Balanced base nine, with digits from −4 to +4 provides the advantages of an odd-base balanced form with a similar number of digits, and is easy to convert to and from balanced ternary.

Other notable examples include Booth encoding and non-adjacent form, both of which use a base of $b=2$ , and both of which use numerals with the values −1, 0 and +1 (rather than 0 and 1 as in the standard binary numeral system).

Non-unique representations

Note that signed-digit representation is not necessarily unique. For instance:

(0 1 1 1)₂ = 4 + 2 + 1 = 7

(1 0 −1 1)₂ = 8 − 2 + 1 = 7

(1 −1 1 1)₂ = 8 − 4 + 2 + 1 = 7

(1 0 0 −1)₂ = 8 − 1 = 7

The non-adjacent form does guarantee a unique representation for every integer value, as do balanced forms.

When representations are extended to fractional numbers, uniqueness is lost for non-adjacent and balanced forms; for example,

(0 . (1 0) …)_NAF = 2⁄3 = (1 . (0 −1) …)_NAF

and

(0 . 4 4 4 …)_(10bal) = 4⁄9 = (1 . -5 -5 -5 …)_(10bal)

Such examples can be shown to exist by considering the largest and smallest possible representations with integral parts 0 and 1 respectively, and then noting that they are equal. (Indeed, this works with any integral-base system.)

References

^ Dhananjay Phatak, I. Koren, Hybrid Signed-Digit Number Systems: A Unified Framework for Redundant Number Representations with Bounded Carry Propagation Chains, 1994, [1]

[1] Dhananjay Phatak, I. Koren, Hybrid Signed-Digit Number Systems: A Unified Framework for Redundant Number Representations with Bounded Carry Propagation Chains, 1994, [1]

[1]

Balanced form

Non-unique representations

See also

References