Page 86 - Engineering Digital Design

2.9 BINARY ARITHMETIC 57

Thus, PI = A 2 x (Z?2c) generates the 2's complement of A 2 x ,62 — the form in which a
computer stores the results. The "true" value of PI can be obtained by negation, which is
the 2's complement of the result, that is, P 2) 2c = (2" — A 2 x B 2) 2C.
Likewise, if both A 2 and B 2 are negative n-bit operands, then the product (— A 2 ) x (— B 2)
becomes, after conversion to 2's complement by Eq. (2.14),

P 2 = A 2C x

= (2" - A 2 ) x (2" - B) Mod 2 n
n
= 2" x 2" - 2"A 2 - 2 B 2 + A 2 x £ 2 Mod 2
2n n n
= 2 - 2 - 2 + A 2 x B 2 Mod 2"
or P 2 = A 2 x B 2, (2.23)

2
where 2 " — 2" — 2" (Mod 2") = 0. Thus, the product of two negative binary numbers
in 2's complement notation is the positive product of the two numbers. In dealing with
numbers whose bit representations are, say, k > m, excluding leading zeros for both, the
2's complement product P^ must be given in n — 2k bits. This count for k must include
fraction bits, if present, but exclude both leading and trailing zeros.
The following example illustrates 2's complement multiplication of two numbers with
fractions each of k = m = 4 bits and represented as k + m = 8-bit operands:
EXAMPLE 2.29
-2.25 -000010.01 111101.11 Multiplicand, B 2C
x6.5 xOOOOllO.l * xOOOOllO.l Multiplier, A 2
-14.625 11110111 2° x B
000000000
2
1111011100 2 x B
3
11110111000 2 x B
1010101100 Level 1 Carries
10101 Level 2 Carries
1 1001000101 1 Product, P 2C Mod 2 8

8-bit representation
The true value of the 8-bit representation is obtained by negation,

10001. 01 1 2C) 2C = 01110.101 2 = 14.625,

which, of course, is a negative number. This example illustrates what is called Booth 's
algorithm for fast signed multiplication, and is expressed as follows:

Algorithm 2.11: A 2 x B 2c or A 2c x
2
(1) Set n = 2k, where k(>m) is the larger of two numbers counting both integer and
fraction bits in k but excluding leading and trailing zeros.

The two numbers are initially | A£ I of k bits and | B^ \ of m bits or vice versa.