Page 530 - Introduction to Information Optics

9.4. Parallel Signed-Digit Arithmetic
Table 9.15
Truth Table for the Nonrestricted
Reference Digits in the Three-Step
Digit-Set-Restricted MSD Addition [144]

1 1 1
1 0 0
0 T
0 0 0
1 I 0

The second step is to generate the digit-set-restricted intermediate carry
and sum digits based on the reference digits. At each digit position, according
to the digit pair (x^yj and the determined reference digits r i+i and r,-, the
unique solutions of c t + 1 and s,- will be calculated. For example, if the pair is
(1,1), r ( + 1 and r { are 1 and T, respectively, we can produce an equation:
2c J + , + s f = — 1 from Eq. (9.36). So c l + 1 and s t must be 1 and 1, respectively,
to satisfy this equation. Actually, the formation of the intermediate carry and
sum is dependent on two consecutive input digit pairs. Table 9.16 is the truth
table for this step.
The last step is to generate the final result by adding the intermediate carry
and sum words digit-by-digit in parallel. The principle is proven below. The
summation of two N-digit MSD numbers X and Y can be expressed as

X + Y = £ 2ix,. + >',.). (9.37)
i = 0

A substitution of Eq. (9.36) into Eq. (9.37) leads to

(9.38)

The first term of Eq. (9.38), which is equivalent to C N ... c 2c lQ, can be rewritten