Page 519 - Introduction to Information Optics

504 9. Computing with Optics

where c, + 1 and s t are the intermediate carry digit and sum digit, respectively,
and they are also usually written as the transfer digit t i+ 1 and the weight digit
w ( , respectively. By exploiting the redundant representations of the sum 1 4 0
and 1 + 0 and using the property that 1+1 = 0, a carry can be absorbed
within two digits of its left neighbor. According to the number of steps needed
to yield the final sum, the algorithms for MSD addition can be classified into
three main categories: the three-step approach, two-step approach, and one-
step approach. According to the digit sets to which the intermediate carry and
sum belong, the algorithms can be classified into the digit-set- nonrestricted
approach and the digit-set-restricted approach. In the former approach, the
intermediate carry and sum are selected from the entire MSD set {1,0, 1 }, while
in the latter approach, the intermediate carry and sum digits are restricted to
the sets {1,0} and (0, 1), respectively. Subtraction can be implemented by first
digit-by-digit complementing the subtrahend and then performing addition:

x - y = x + Y = X (x,. + T-;). (9,26)
i = 0

The truth tables and the minimized minterms for the subtraction operation
can be easily obtained by following the same procedure used for addition.

9.4.2. 1 . Digit-Set- Unrestricted Addition/ Subtraction

9,4.2.1,1. Three-Step MSD Addition/ Subtraction

In this category [70, 71, 122-130], the first stage generates a transfer and a
weight string in parallel. These weight and transfer digits are then used to
generate a second set of transfer and weight digits. The first two operations
eliminate the occurrences of the (1,1) and (1, T) pairs at the same digit position,
so that the third-stage digitwise addition of the weight and transfer digits
becomes carry free. Therefore, the addition of two arbitrary MSD numbers can
be completed with three steps in constant time, independent of the operand
length.
MSD addition can be realized by an array of trinary logic elements, as
shown in Fig. 9.16, which depicts the addition of two five-digit MSD numbers
A and B. In Fig. 9.16, logic elements T and W are used in the first stage while
1 l
logic elements T and W are used in the second stage. The final sum S is
obtained in the third stage by applying the logic element T. The truth tables
for the above-mentioned four logic functions are shown in Table 9.6. Bocker
et al. [122] effectively transformed these truth tables into symbolic substitution
3
rules. Thus, a total of 3 = 27 rules corresponding to the nine input combina-
tions at each stage are required. A closer look at the truth tables corresponding