Page 84 - Engineering Digital Design

2.9 BINARY ARITHMETIC 55

In this latter case the result is given in 1's complement. The true value for the difference is
obtained by negation and is 1-1001 -> 0:01102 = 610, which is known to be negative.

2.9.4 Binary Multiplication
Like binary addition and subtraction, binary multiplication closely follows base 10 multi-
plication. Consider two n-bit binary integers A2 = (a,,-i • • • aia\a$) and 82 = (b n-\ • • • bi
b\bo)2- Their product A2 x 5? is expressed in n-bits assuming that both numbers are ex-
pressible in n/2 bits excluding leading zeros. Under this assumption the product is

/^ \
aP = A x B = ( > a t•• 2' I • B
\f=t I

meaning that if B = b n-\ • • • b 2b\bQ, the product 2' x B is
!
2 x B = b n-\ •••b 2b ]b 0 00---0.
/ zeros
Thus, the product A x B is expressed as the sum of the partial products /?, in the form

Therefore it should seem clear that binary multiplication requires addition of all terms
of the form 2' x B for all i for which a, = 1. The following example illustrates this
process.

EXAMPLE 2.27
A 00001111 = Multiplicand
xB xOOOOlOll = Multiplier
00001111 2° x B
1
000011110 2 x B
0000000000
3
00001111000 2 x B
111011 Level 1 Carries
1 Level 2 Carries
000 10100101 = Product P 2

Notice that the carry process may involve more than one level of carry as is true in this
example. The following algorithm avoids multiple levels of carry by adding each product
to P as it is formed.