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 = ⅔ = (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 greatest 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.)
Read more about this topic: Signed-digit Representation