Page 529 - Introduction to Information Optics

514 9. Computing with Optics

| —2, —1,0,1). Obviously, the operation 2c, + ] + s t cannot produce the value
2. Some modifications are thus necessary to be made in Eq. (9.25). In order to
ensure that each formed intermediate carry digit is nonpositive and each
formed intermediate sum digit is nonnegative, a reference digit r, is employed
to transfer quantities from one digit position of the input operand digits to
another position to keep the identity. For any digit position /, there exists an
output value, which is equal to 2r 1 + 1, to the next higher order digit position
and an incoming value, which is equal to r,, from the next lower order digit
position. The sum of the input operand digits at the zth position can be
represented in terms of the reference digit values mentioned above and the
values of the intermediate carry and sum digits. So a new algebraic equation
is written as

(9.36)

The reference digit r, may be either nonrestricted, belonging to the digit set
(1,0, 1), or restricted to a smaller set (0, 1}. The addition algorithm based on
this scheme consists of three steps for generating the reference digits, the
intermediate sum and carry, and the final sum, respectively. The three-step
algorithm with nonrestricted reference digits is developed in Sec. 9.3.2.2.1 and
that with digit-set-restricted reference digits in Sec. 9.3.2.2.2. Through the
proposed encoding scheme, the algorithms can be completed within two steps,
presented in Sec. 9.3.2.2.3.

9.4.2.2.1, Algorithms with Nonrestricted Reference Digits
The first step is to generate the reference digits, which are of the set {1,0, 1).
The reference digit at the ith position depends only upon the addend and
augend digits at the (i — l)th digit position. It should be mentioned that for a
fixed input digit pair (x (.,y (-), the reference digit r i+l has a unique value,
otherwise there maybe no solutions for c i+l and s,- to satisfy their digit-set
constraints. For example, if (x,-,.y ;-) is (1, 1), then the reference digit r i+ { must
be 1. Provided that r i+1 and r t- are T and 0, respectively, from Eq. (4.36), we
can deduce that c i+l and s t satisfy the equation 2c i+l + s { = 4. There are no
solutions for c i + 1 and s t since c i + 1 is of the set (I, 0} and s f is of the set (0, 1 }.
If r i + i and r i are 0 and 1, respectively, the same contradiction will occur.
Hence, the reference digit r t - +1 based on the digit pair (1, 1) cannot be I or 0.
Similarly, the reference digits generated by other fixed-input digit pairs also
have the corresponding unique values. Table 9.15 shows the computation rules
for the reference digit r i+l based on the operand digit pair (x, :, y,). The addend
and augend digits are classified into six groups since they can be interchanged.
After this step, a reference word has been obtained.