Page 534 - Introduction to Information Optics

9.4. Parallel Signed-Digit Arithmetic 5 19

The key feature of this algorithm lies in the utilization of the reference digits.
Their function is to determine the values transferred from one digit position of
the operand words to another digit position so that the digits of the formed
intermediate carry and sum words are all restricted to a smaller set and their
sum is equal to the sum of the operand words.

9.4.2.2.2. Algorithms with Digit-Set-Restricted Reference Digits
In the above-mentioned algorithm, the reference digits can contain the value
from the set [1,0,1} while the intermediate carry and sum digits are all digit-set
restricted. For the purpose of simplifying the algorithm, the reference digits can
also be restricted to the digit set (0,1}. The merit of this scheme is that each
of the intermediate carry and sum digits and the reference digits has only two
states; i.e., 1 and 0 or 0 and 1. Therefore, only a single binary bit may be
required for their representations independent of their signs. This makes it
possible to realize associated operations by binary logic [134]. Tables 9.18 and
9.19 are the truth tables for generating the digit-set-restricted reference digits,
intermediate carry, and sum digits, respectively. The reduced minterms for this
three-step scheme are listed in Table 9.20. Similarly, the first two steps can be
combined, as shown in Table 9.21. Furthermore, the three-step operations can
be completed in a single step. The logic minterms for the one-step digit-set
restricted MSD addition are shown in Table 9.22.
Now we discuss Eq. (9.41) again under the condition of digit-set-restricted
reference digits. According to the computation rule of digit pair (0,0) in Table
9.19, r v and S N are equal to each other and Eq. (9.41) is thus rewritten as

(9.47)

Table 9.18
Truth table for the Three-Step MSD
Digit-Set-Restricted Addition Based on
the Digit-Set-Restricted Reference
Digits: the First Step Rules [144]

1 1 0
I 0 0
0 I
0 0 0
1 I 1
I 1
) 0 1
0 1
1 1 1