Page 85 - Engineering Digital Design

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

Algorithm 2.10: A 2 x B 2
(1) Set n = 2k, where k is the number of bits of the larger number exclusive of leading
zeros.
(2) Set A = a n-i • • • a 2a\aQ and B = b n~\ • • • b 2bib® for an n-bit multiplier and an n-bit
multiplicand, respectively.
(3) Set p = 0 and i = 0.
(4) If a, = 1, calculate 2' x ,8 = (b n^i • • • b\b Q 00--0) and add it to P.
I zeros
(5) Increment i by 1.
(6) Repeat steps (3) and (4) for all 0 < i < (n — 1) ending with a product P 2 of n bits
or less.
k
If A 2 and B™ represent operands expressible by a different number of bits, k and ra,
exclusive of leading zeros, then their product is P 2" = A 2 x fi™ given in n < (k+m) bits. For
numbers containing both integers and fractions, k and m must each include all bits exclusive
of leading integer zeros. For example, if B™ = 1101.11 (m = 6) and A 2 = 110.1 (k = 4),
their product P% will be given inn = 6 + 4= 10 bits. The following example illustrates
the multiplication process for these two operands.

EXAMPLE 2.28
1101.11 Multiplicand fl
k
xllO.l Multiplier A 2
110111 2° x B
0000000
2
11011100 2 x B
3
110111000 2 x B
111011 Level 1 Carries
1 Level 2 Carries
1011001.011 Product P 2"

10-bit representation
2's Complement Multiplication To understand 2's complement multiplication it is help-
ful to introduce the concept of modulo 2" (Mod 2") arithmetic. In Mod 2" arithmetic multipli-
cation is carried out in 2's complement numbers (if negative) ignoring the overflow beyond
4
4
4
n bits. For example, 2 x 1111 (Mod 2 ) = 10000 = 2 or generally, for number B of n bits,
2" x B (Mod 2") = 2".
Consider the n-bit integer operands A 2 = a n-\ • • • a\a^ and BI = b n_\ • • • b\b 0. Then, if
the product isP = Ax(— B) , there results, after converting B to 2's complement,

P 2 = A 2 x (B 2C)
= A 2x (2" - B) Mod 2"
n
= A 2x 2 -A 2xB 2 Mod 2"
or P 2 = T - A 2 x B 2 Mod 2" (2.22)