Signed-digit representation: Difference between revisions
→Balanced form: clarification of my previous edit |
|||
| Line 5: | Line 5: | ||
Signed-digit representation can be used in low-level software and hardware to accomplish fast high speed addition of integers because it can eliminate carries<ref>Dhananjay Phatak, I. Koren, '''Hybrid Signed-Digit Number Systems: A Unified Framework for Redundant Number Representations with Bounded Carry Propagation Chains''', 1994, [[http://citeseer.ist.psu.edu/phatak94hybrid.html]]</ref>. 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. |
Signed-digit representation can be used in low-level software and hardware to accomplish fast high speed addition of integers because it can eliminate carries<ref>Dhananjay Phatak, I. Koren, '''Hybrid Signed-Digit Number Systems: A Unified Framework for Redundant Number Representations with Bounded Carry Propagation Chains''', 1994, [[http://citeseer.ist.psu.edu/phatak94hybrid.html]]</ref>. 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. |
||
Hi. Good site. |
|||
==Balanced form== |
|||
In balanced form, the digits are drawn from a range <math>-k</math> to <math>(b-1) - k</math>, where typically <math>k = \left\lfloor\frac{b}{2}\right\rfloor</math>. 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 <math>b=3</math>, 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 a odd-base balanced form with a similar number of digits, and is easy to convert to and from balanced ternary. |
|||
==Non-unique representations== |
==Non-unique representations== |
||
Revision as of 11:07, 3 January 2009
| Part of a series on |
| Numeral systems |
|---|
| List of numeral systems |
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 high speed 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.
Hi. Good site.
Non-unique representations
Note that signed-digit representation is not necessarily unique. For instance:
- (0 1 1 1)2 = 4 + 2 + 1 = 7
- (1 0 −1 1)2 = 8 − 2 + 1 = 7
- (1 −1 1 1)2 = 8 − 4 + 2 + 1 = 7
- (1 0 0 −1)2 = 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.)