Page 87 - Engineering Digital Design

58 CHAPTER 2 / NUMBER SYSTEMS, BINARY ARITHMETIC, AND CODES

(2) Generate the 2's complement of the negative number(s) by applying Eq. (2.14).
(3) Cany out steps (3) through (6) of Algorithm 2.10 applied to operands A2 and
or
or AIC and B2c-> represented as n-bit operands, to generate the product P 2 "c ^2 •
Mod 2" arithmetic where applicable.

2.9.5 Binary Division
The division operation is generally more complex than that for multiplication. This is so
because the result is often not an integer, though the dividend and divisor may be. Consider
that A 2 and 62 are binary operands each of n bits and that

A + B = Qi? + R/B, (2-24)
7=0
where A is the dividend, B is the divisor, Q is the quotient, and R is the remainder such
that 0 < R < B. An integer quotient is expressed as the binary number Q n-\ • • • Q\ <2o-
From Eq. (2.24) there results the expression

(2.25)

which forms the basis for a restoring type of binary division procedure:
Begin with n — 1 for a k-bit divisor and a (k + «)-bit dividend to yield an n-bit quotient
and a k-bit remainder. If

1
A-2"~ B = A-b n-i •••bibo 00---0>0 ,
n — 1 zeros
Q n-\ = 1 or otherwise Q n-\ — 0. If Q n-\ = 1, the remaining quotient bits Q n-\ • • • QiQo
n [
n 2
are found beginning with A' = A-2 ~ B.Then,ifA'-2 ~ B > 0, Q n- 2 = lorotherwise
Q n_2 = 0. Consequently, if Q n-2 = 1, the remaining quotients <2«-3 • • • Q\ Qo are found
2
beginning with A" = A' — 2"~ B, etc. The procedure just described mimics the familiar
pencil-and-paper division method.
As an example, consider the following division operation A -=- B with 5-bit operands:
EXAMPLE 2.30

00000101 = Q
fl=010lV00011011 = A
2
-00010100 = 2 • B
2
00000111 = A'= A-2 fi
-00000101= 2° • B
/
0010 =/? = A -2°5