Page 541 - Introduction to Information Optics

526 9. Computing with Optics

It is just the 2's complement of the previous denominator D^ In the MSD
system, the subtraction can be computed in constant time by complement and
addition. Since the convergence is quadratic, the accumulated denominator
length is doubled after each iteration. Thus, for a desired quotient of length «,
the maximum number of iterations needed is Iog 2n. In each iteration, three
operations are involved; i.e., two MSD multiplication and an MSD subtrac-
tion. If the binary-tree architecture is employed to perform a multiplication, a
total of Iog 2nn steps are required and up to m/2 additions are needed in each
step.

9.4.2.4.2. Quotient-Selected Division
MSD division based on the conventional add/subtract-and-shift-left prin-
ciple is realized by shifting the partial remainder, generating a quotient digit,
and then performing an addition or subtraction operation to produce the next
partial remainder. It generates one quotient digit per iteration from the most
significant digit toward the least significant digit. The number of required
iterations is n. The conventional algorithm requires knowledge of the sign of
the partial remainder for selecting a quotient digit, and it is necessary to check
all digits of the partial remainder. Recently a novel quotient-selected MSD
division algorithm [145] has been proposed in which we only need to know
the range rather than the exact value of the partial remainder. The selection
function is realized by checking only several of its most significant digits.
The algorithm based on the add/subtract-and-shift-left principle to compute
the division X/D relies on the following equations:

(9.60)

e,.= £2-^, e = o, (9.61)
0
1 = 0

where / is the iteration step, w f is the partial remainder at step / having the form
vv
vv
W
of w,-.o' u' i,2--- M>-i> q { is the quotient digit, and Q f is the value of the
quotient after the ith iteration.
In any signed-digit-based division scheme with quotient digits selected from
the set { — s,..., 0,..., s}, the range of the partial remainder in the (i — l)th
iteration is —rjD < w i^. l < qD, where rj = s/(r — 1) is called the index of
redundancy. For MSD numbers with radix r = 2, the quotient digits belong to
the set {1,0, 1} and thus rj = 1. So the partial remainder w,_j should be
restricted to the range ( — D,D) and the range of 2w i _ 1 is ( — 2D, 2D). To
guarantee w,-e( — D, D), the rules determining the three possible values of q t are