Page 554 - Introduction to Information Optics

9.4. Parallel Signed-Digit Arithmetic 539
lo this problem is to arrange the partial products and the partial carries
as separate numbers, as shown in Fig. 9.22.

When all the partial products are formed in parallel, we can use the simplified
nonrecoded QSD addition algorithm to sum them in a tree structure. However,
the third scheme just discussed is simpler than alternate techniques to generate
the partial products, although it requires an additional step to add the partial
products compared to the other schemes.

9.4.5. NSD ARITHMETIC OPERATIONS

In [50], a two-step parallel negabinary addition and subtraction algorithm
is proposed, in which the sum of two negabinary numbers is represented in
NSD form. As shown in Table 9.35, in the first step the transfer and weight
digits are generated by signed AND and XOR operations. In the second step,
the final sum is obtained by signed XOR operation. The algorithm can be
performed by spatial encoding and space-variant decoding technique. Later the
two-step algorithm was combined into a single step [161] and implemented
with space-polarization encoding and decoding. For multiple addition and
multiplication, Li et al. [162] developed a generalized algorithm for NSD
arithmetic. As discussed in the following sections, the former algorithm is a
special case of generalized NSD arithmetic.
In NSD arithmetic, the digits of the operands belong to the set (I, 0, 1). For
a digitwise operation, there are nine possible combinations; i.e., (a ;, b^ — (1, 1),
(1, 0), (1, I), (0, 1), (0, 0), (0, I), (I, 1), (1, 0), and (T, I). For addition, at each
position an intermediate sum (defined by a weight function, W) w £ e{l,0, 1}
and an intermediate carry (defined by a transfer function, T) f,e (I, 0, 1} will
be produced, satisfying the condition a i + h s = ( — 2)t i+1 + w,-. The digit com-
binations (1,1) and (I, T) generate a T and a 1 carry, respectively, while the
combinations (0, 0), (1, 1), and (1, T) do not generate any carry. The remaining
combinations, however, can yield two different results based on the redundancy
of NSD: 0 + 1 = 1 + 0 = 01 or IT, and 0 + I = T + 0 = 01" or 11. For subtrac-

Table 9.35
Truth Table for Logic Functions in Two-Step Addition and One-Step Subtraction [50]
. T . W , S . D
u,\ 0 1 »A 0 1 \ 0 1 a \ 0 1
0 0 0 0 0 1 0 0 1 0 0 1
1 0 1 1 1 0 1 1 0 1 1 0
Signed AND XOR Signed XOR Signed XOR