Page 540 - Introduction to Information Optics

9.4. Parallel Signed-Digit Arithmetic

Step 2: Summation of the partial products

0001 01 1\
oolono/' -+00000111
00100101 = 35 10.
0000000\ -» iTToiooo
loTTooo/

9.4.2.4. Division
Conventional storing and nonstoring division methods require knowledge
of the sign of the partial remainder for exact selection of the quotient digits.
However, in MSD the sign of a partial remainder is not always readily
available. Therefore, we must seek an effective division algorithm which can
overcome this difficulty and use the parallel addition and multiplication
arithmetic operations developed in the previous sections. To this end, two
different approaches have been proposed: the convergence approach [123] and
the quotient-selected approach [145].

9,4.2.4.1, Convergence Division
A parallel MSD division algorithm which meets the aforementioned require-
ments is based on a convergence approach [123]. Consider a dividend X and
a divisor D in normalized form, 1/2 ^ \X\ < \D\ < 1. We want to compute the
quotient Q = X/D without a remainder. The algorithm utilizes a sequence of
l n
multiply factors m 0, m ls . . . , m n so that D x (H i^ 0m i) converges to 1 within an
acceptable error criterion. Initially, we set X 0 — X and D Q — D. The algorithm
repeats the following recursions:

X i+l= Xi x m,., D i+ , - D f x m f , (9.57)

so that for all n

(9.58)

The effectiveness of this convergence method relies on the ease of computing
the multiply factors m, using only the MSD addition and multiplication. It is
found that for D i+i to converge quadratically to 1, the factors m t should be
chosen according to the following equation:

m i = 2-D i,Q<D i<2. (9.59)