Computer Arithmetic - Fundamentals of Computer Organization and Architecture - page 70

operation is shown in Figure 4.7. In this figure, the control logic is used to determine
the operation to be performed depending on the least significant bit in Q.Ann-bit
adder is used to add the contents of registers A and M.
In order to speed up the multiplication operation, a number of other techniques
can be used. These techniques are based on the observation that the larger the
number of consecutive zeros and ones, the fewer partial products that have to be gen-
erated. A group of consecutive zeros in the multiplier requires no generation of new
partial product. A group of k consecutive ones in the multiplier requires the gener-
ation of fewer than k new partial products. One technique that makes use of the
above observation is the Booth's algorithm. We discuss below the 2-bit Booth's
algorithm.

The Booth's Algorithm In this technique, two bits of the multiplier,

Q(i)Q(i 2 1), are inspected at a time. The action taken depends

on the binary values of the two bits, such that if the two values are respectively
01, then A A þ M; if the two values are 10, then A A M. No action is
needed if the values are 00 or 11. In all four cases, an arithmetic shift right oper-
ation on the concatenation of AQ is performed. The whole process is repeated n
times (n is the number of bits in the multiplier). The Booth's algorithm requires
the inclusion of a bit Q(

1), (0 i n

0 as the least significant bit in the multiplier Q at
the beginning of the multiplication process. The Booth's algorithm is illustrated
in Figure 4.8.
The following examples show how to apply the steps of the Booth's algorithm.

1)

2 ¼

A = 0, Q(−1) = 0
M

Multiplicand
Q = Multiplier
n = Count

=

= 01

= 10

Q(0), Q(−1)?

11 or 00

A = A − M A = A + M

ASR(A,Q)
n = n − 1

n = 0?

No

Ye s

Done

Figure 4.8 Booth's algorithm