Page 552 - Introduction to Information Optics

9.4. Parallel Signed-Digit Arithmetic

Table 9.33
Reduced Truth Table for the Simplified Two-Step Nonrecoded QSD
Addition [73]
Step number Output literal Minterms «,./>(
i , : = 2 d 3l d3i, 20, 02

;-, i = 1 3d 3 2io, d 3210 3, d, 2 d, 2
2 ,. = 3 21
, = 2 20, 1 1
i = 1 21, 10,01

The minterms for QSD subtraction can be derived in a similar fashion.
Alternatively, we can complement the subtrahend and then apply the addition
truth table.

9.4.4.2. Multiplication
Usually the multiplication of two JV-digit QSD numbers A and B produces
a 2N-digit product P — p 2N-iP2N-2---PiPo- For fast multiplication [160], we
need to generate all N partial products in parallel and add them in a tree
(l}
structure. Each partial product p (i = 0, 1, . . . , N — 1) is formed by multiply-
ing the multiplicand A and the ith digit of the multiplier B and shifting i digits
(l)
l
to the left; i.e., p = Ab t4 . Thus, the product P can be computed from the
summation
- i
!
1
9 65
4
P = AB = V p<'> = £ Ab {4 = X P/ ''- ( - )
The difficulty lies in how to generate all the partial products in parallel
for jhigher-radix multiplication. In QSD multiplication with the digit set
(3, 2, 1,0, 1, 2, 3}, carries may be transmitted to the next higher digit positions
when both digits a, and b { to be multiplied take the values 3, 2, 2, 3. Notice
l+j
that the digits of the product whose weights are larger than 4 are called
carries herein. The carry propagation prevents us getting the partial products
Abf directly and sequential additions are required. To overcome this problem
and lessen complexity, three methods can be chosen:
• Recode the operands to map the digit set from (3, 2, I, 0, 1, 2, 3} to a
smaller one (2, I, 0, 1, 2}. The multiplication can thus be simplified. The
product can be represented by two digits (partial carry and partial
product), with the partial-product digit limited to (2, I, 0, 1, 2} and the
partial-carry digit limited to (I, 0, 1}. This property guarantees that