Page 551 - Introduction to Information Optics

536 9. Computing with Optics

Table 9.32
Reduced Truth Table for the Second Step Operation of the Recoded QSD
Addition [156]

Output literal Minterms a ib,a i__ib i_- l
3 1122 122d TO i2 12d Toi2 d 212d I012 21d I012d 2222
2 0122__022dioi2 02d Toi2 d 1022_ 112d To , 2 lld To ,d 112d 3To ,
1222_ 202d Toi2 _ 20dioi 2 d 2122
1 Tl22__l22d 70 i2 12d T(112d 0022 012d T(U2 Oldjoid _012d 2To!
0222 ll22_J02d I012 10d To! d 102d 5 toi 1122 2T2d To(2
2ld Toi2 2022

Since these algorithms are usually implemented by optical symbolic substi-
tution or content-addressable memory where the input numbers and the
minterms are spatially encoded and compared, the optical system can be
simplified by the use of fewer rules and fewer variables in a rule. For this
purpose, the number of minterms may be cut down further. Li et al. [73] have
proposed a simplified two-step QSD arithmetic by exploiting the redundant
representation of two single-digit sums. In this scheme, addition of two
numbers is realized by adding all digit pairs at each position in parallel. The
addition of a { and b t will yield an intermediate sum (s,-) and an intermediate
carry (c i+l) for the next higher order digit position. If s t and c i+l generated in
the first step are restricted to the sets {2, I, 0, 1, 2} and (T, 0, 1}, respectively,
then the addition of s, and c { in the second step becomes carry free. Conse-
quently, in the first step only 20 two-variable minterms are needed to produce
the intermediate sum and the intermediate carry, and in the second step only
12 two-variable minterms are required to generate the final sum. By taking the
complementary relationship into account, only 10 (6) minterms are required
for the outputs of 1 and 2 (1, 2, and 3) in the first (second)-step addition. These
minterms are shown in Table 9.33. Comparing Li's [73] technique with the
other QSD techniques [155-158], the information content of the minterms is
significantly reduced, which alleviates system complexity. For illustration,
consider the following numerical example for four-digit addition:

Augend A: 3223 (decimal — 165)
Addend B: 12T2 (decimal 94)
Intermediate sum S: 02011
Intermediate carry C: OlTl</>
Final sum S: TT21 (decimal —71)