Page 555 - Introduction to Information Optics

540 9. Computing with Optics

Table 9.36
Truth Table for the First Step Operation in NSD
Addition [162]

(ft) T i+l
1 1 (1 0) Don't care 3 0
1 0 (1 0) Both are (D 0 1
0 1 nonnegative
Otherwise (0) I I
0 0 (1 0) Don't care 0 0
] I (0 0) Don't care 0 0
1
7 I i
0 I (0 0) Both are 0) 1 1
I 0 nonnegative
Otherwise (0) 0 I
1 I (0 1) Don't care 1 0

tion, on the other hand, the condition a ( — b ( = ( — 2)t i + 1 + w,- should be
satisfied. The combinations (1,1) and (1,1) generate a I and a 1 carry, respec-
tively, while the combinations (0, 0), (1, 1), and (T, T) do not generate a carry.
The remaining combinations, however, have two different redundant results:
0 - 1 = I - 0 = Ol or 11, and 0 - I = 1 - 0 = 01 or TT. By exploiting this
redundancy, it is possible to perform addition (subtraction) in two steps.
Addition is considered first. To avoid generating a carry in the second step,
the first step should guarantee that identical nonzero digits t { and w, do not
occur at the same position; i.e., both w, and t t are neither Is nor Is. The
optimized rules are shown in Table 9.36, in which the augend and the addend
digits are classified into six groups since they can be interchanged. For the
second and the fifth groups, the two halves having two different outputs can
be distinguished by examining whether both a i_ l and 6,_ t are binary. It is
helpful to introduce a reference bit /•, 1 for binary and 0 for the other cases.
With this reference bit, the number of variables in a minterm can be reduced
from four to three. In the second step, carry-free addition at each position
results in the final sum. The corresponding rules are shown in Table 9.37.
Subtraction can be performed by addition after complementing the subtra-
hend, and this requires three steps. The direct implementation can be per-
formed in two steps. The first step transforms the subtraction into addition,
generating the transfer t i + 1 and the weight w (- at all positions. The substitution
rules for subtraction in the first step are listed in Table 9.38. There are nine
rows in the table since the minuend and the subtrahend cannot be inter-
changed. The reference bit f t is true if both a i_ l and the complement of b i_ l
are nonnegative. These rules also ascertain that the second-step addition is
carry free, according to Table 9.37.