Understanding Booth and Modified Booth Multipliers

Booth Multiplier

The Booth multiplier, or optimized multiplier, is a logic design that efficiently performs multiplication operations, especially for signed integers. Its main advantages are:

Reduces the number of addition operations required during multiplication.
Handles both positive and negative multipliers uniformly.

Previously, we explored array multipliers (combinational) and sequential multipliers (sequential), both of which primarily work with unsigned multiplication and have their own specific logic and design. The Booth multiplier, however, is algorithmic and specifically designed for signed multiplication, aiming to minimize the number of addition operations.

Key Concepts

The Booth algorithm reduces the multiplier to a simpler form called the Booth recoded form, using the Booth recoding method.
A reference bit is appended to the end of the multiplier bits. Then, moving from right to left, pairs of bits (i-th and (i-1)-th) are examined to determine their corresponding values.
The mapping is similar to XOR, but with a twist: for example, a pair of 1 0 maps to -1 instead of 1.
By processing each pair, we generate the Booth recoded form, which is then used in place of the original multiplier, reducing the number of required operations.

Note

Unlike partial product multiplication using two's complement, we only take the two's complement if the most significant bit (MSB) of the result is 1.

Modified Booth Algorithm

The Modified Booth Algorithm extends the original Booth algorithm by further optimizing the recoded form.

The multiplier, already in Booth recoded form, is transformed into a radix-4 representation.
Bits are paired from right to left (e.g., (1 0), (0 -1)), a process known as bit pairing.
Each pair is evaluated in radix-2, resulting in values like 2 and -1.
The resulting numbers form the radix-4 representation, which is equivalent to the original multiplier but allows for faster computation with fewer additions.

Example

Below is a sample question from CIE 01:

Danger

When multiplying the multiplicand by the radix-4 form of the multiplier, shift two bits to the left at each step of the partial product (instead of one). This is because multiplication is being performed with a radix-4 value, not a standard binary number.

Note

Regarding signed multiplication:
Multiplying the radix-4 value by the multiplicand means the operation is in base 4. For example, if the multiplier is 0 -2 1, then -2 * m is equivalent to 2 * (-m). In this case, take the two's complement of the multiplicand and multiply by 2.

After spending considerable time practicing, the algorithm finally clicked for me (though I wish I had paid more attention in class when it was first introduced).

Important Distinctions

Note

In the Modified Booth Algorithm, the final multiplier is the bit-pair sequence obtained from Booth recoding, i.e., the radix-4 representation.

Often, one of the numbers in the radix-4 multiplier is 2 or -2. When multiplying the multiplicand by -2, note that -2(m) == 2(-m). Therefore, take the two's complement of the multiplicand and multiply by 2.

Crucially, do not apply the two standard rules of signed multiplication at this stage, as we are only calculating partial products. These rules are applied in the main calculation. This distinction is essential for correct implementation.

Tip

A practical tip:
When analyzing the multiplier and multiplicand, determine the number of bits required for the result and add one additional bit at the MSB for sign representation. For example, if the multiplicand is 0101 and the multiplier is -1 -2 (in radix-4), the result will require 6 bits. The actual result may span 8-9 bits, but the significant portion is 6 bits.