Next: Floating-Point Representation Up: arithmetic_html Previous: Signed Multiplication

# Fast Multiplication -- Booth's Algorithm

The Booth's algorithm serves two purposes:
1. Fast multiplication (when there are consecutive 0's or 1's in the multiplier).
2. Signed multiplication.

First consider two decimal multiplications: and . It is obvious that If straight forward multiplication is used, the first one is easier than the second as only two single-digit multiplications are needed for the first while four are needed for the second. However, as we also realize that:

the two multiplications should be equally easy.

Example 1

If there is a sequence of 0's in the multiplier, the multiplication is easy as all 0's can be skipped.

Example 2

However, it does not help if there is a sequence of 1's in the multiplier. We have to go through each one of them:

How can we enjoy a sequence of 1's as well as a sequence of 0's? We first Realize that , or in general a string of 1's in the multiplier A can be written as:

where d is don't care'' (either 0 or 1). If we define the first part of the above as and the second part as , then the multiplication becomes

In other words, only the two ends of a string of 1's in the multiplier need to be taken care of. At the left end the multiplicand is added to the partial product, while at the right end the multiplicand is subtracted from the partial product. The above multiplication can therefore be written as:

On the right side above the subtraction is carried out by adding 2's complement. We observe that there is a sequence of 1's in the multiplier, only the two ends need to be taken care of, while all 1's in between do not require any operation. The Booth's algorithm for multiplication is based on this observation. To do a multiplication , where
• is the multiplicand
• is the multiplier
we check every two consecutive bits in at a time:

where , and when , .

Why does it work? What we did can be summarized as the following

* Recall that the value of a signed-2's complement number (either positive or negative) can be found by:

Another Example:

Assume bits available. Multiply by . First represent both operands and their negation in signed 2's complement:

Then carry out the multiplication in the hardware:

The upper half of the final result is in register [A] while the lower half is in register [Q]. The product is given in signed 2's complement and its actual value is negative of the 2's complement:

Also note that:

• As the operands are in signed 2's complement form, the arithmetic shift is used for the right shifts above, i.e., the MSB bit (sign bit) is always repeated while all other bits are shifted to the right. This guarantees the proper sign extension for both positive and negative values represented in signed 2's complement.

• When the multiplicand is negative represented by signed 2's complement, it needs to be complemented again for subtraction (when the LSB of multiplier is 1 and the extra bit is 0, i.e., the beginning of a string of 1's).

Next: Floating-Point Representation Up: arithmetic_html Previous: Signed Multiplication
Ruye Wang 2013-01-25