Booth's Multiplication Algorithm: Efficient Multiplication of Signed Binary Numbers

Learn how Booth's multiplication algorithm efficiently multiplies signed binary integers in two's complement representation. Understand the steps involved, its advantages in terms of speed and efficiency, and its significance in computer arithmetic.

Booth's Multiplication Algorithm

The Booth algorithm is an efficient method for multiplying two signed binary integers in 2's complement representation. It optimizes the multiplication process, speeding up the calculation. The algorithm works by utilizing sequences of 0's and 1's in the multiplier, with no additional bits required for the 0's, while handling strings of 1's as part of the algorithm's bit manipulation process.

Booth's Multiplication Flowchart

In the Booth's multiplication algorithm, initially, the accumulator (AC) and the Qn + 1 bits are set to 0. The sequence counter (SC) keeps track of the total number of bits in the multiplier (n). The algorithm involves working with the multiplicand (M) and the multiplier (Q), and it is driven by the two bits of the multiplier, Qn and Qn + 1. These bits dictate whether we add or subtract the multiplicand (M) from the accumulator (AC) before performing an arithmetic shift right (ASHR) operation.

Working of the Booth's Algorithm

To begin with:

• The multiplicand (M) and the multiplier (Q) are represented in binary.
• The accumulator (AC) and Qn + 1 are initialized to 0.
• The sequence counter (SC) represents the number of bits in the multiplier and decreases after each iteration until it reaches 0.
• Qn represents the last bit of the multiplier (Q), and Qn+1 represents the bit next to Qn.

On each cycle, the algorithm checks the two bits Qn and Qn + 1. Based on their values, the following steps are taken:

• If Qn and Qn + 1 are 00 or 11, an arithmetic shift right (ASHR) is performed on the accumulator and the multiplier.
• If Qn and Qn + 1 are 01, the multiplicand (M) is added to the accumulator (AC) and an arithmetic right shift is performed.
• If Qn and Qn + 1 are 10, the multiplicand (M) is subtracted from the accumulator (AC) and an arithmetic right shift is performed.

The operation continues until the sequence counter reaches 0, and the result is stored in the accumulator (AC) and the multiplier (Q).

Booth's Algorithm Methods

There are two methods used in Booth's Algorithm for shifting:

• RSC (Right Shift Circular): The right-most bit of the binary number is shifted to the beginning of the binary sequence.
• RSA (Right Shift Arithmetic): The binary number is added together and the result is shifted right by 1 bit position.

Example 1: Multiplying 7 and 3

To multiply the numbers 7 and 3 using Booth's algorithm, we first convert them into binary:

• 7 in binary: 0111
• 3 in binary: 0011

Here, the multiplicand (M) is 7, and the multiplier (Q) is 3. The sequence count (SC) is 4 (since we have 4 bits), and the cycles of the algorithm will run SC times.

The final result is 7 x 3 = 21. The binary representation of 21 is 10101, and in 4-bit format, it is 00010101.

Example 2: Multiplying 23 and -9

Now, let's use Booth's algorithm to multiply 23 and -9. First, we convert the numbers into binary:

• 23 in binary: 010111
• -9 in binary: 110111 (2's complement)

The result is 23 x -9 = -207. The 2's complement of 111100110001 gives the binary result of 00001100111.