Signed-Digit Number Operations

In a signed-digit (SD) number system, carry propagation can be limited to one position to the left during the digit-wise addition and subtraction. The addition time is independent of the word length since the chains of carry-propagations are eliminated.


In a conventional number representation with an integer radix r > 1, each digit is allowed to have exactly r values: 0,1, · · · , r − 1. In an SD representation with the same radix r, each digit is allowed to have more than r values. In the method of addition described below, each digit is allowed to have q different values where


Obviously q is more than r. Redundancy in the number representation allows a method of fast addition/subtraction called totally parallel addition/subtraction.

In the totally parallel addition/subtraction, the signed-digit representations are required to have a unique representation of zero. Thus the magnitude of allowed digit values may not exceed r − 1, since otherwise we could let a digit equal to r and represent zero by imager as well as 00.

Some characteristics of the SD numbers are as follows.

Let A = (an−1 · · · ak) be an SD number, we have

  1. where
  2. Let p = max{i|ai ≠ 0}, sign(an−1 · · · ak) = sign(ap) for (an−1 · · · ak) ≠ 0.

11.2 ...

Get Arithmetic and Logic in Computer Systems now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.