ArchitectureBooth's Algorithm

✖️ Booth's Algorithm

Signed binary multiplication using bit shifting and addition/subtraction. Reduces the number of partial products for efficient hardware implementation.

What is Booth's Algorithm?

ℹ️

Purpose

Booth's Algorithm multiplies signed binary numbers in two's complement form. It works by examining adjacent bit pairs of the multiplier to determine whether to add, subtract, or just shift the multiplicand.

Invented by Andrew Donald Booth in 1951, the algorithm handles both positive and negative multipliers uniformly and reduces the number of add/sub operations when there are consecutive 1s or 0s.

Booth's Algorithm Flowchart

Interactive Simulator

Multiplicand (M):

Multiplier (Q):

How Booth's Algorithm Works

The algorithm operates on n-bit signed binary numbers in two's complement form. Three registers are used:

A (Accumulator): n-bit register, initialized to 0
Q (Multiplier): n-bit register holding the multiplier
Q₋₁: 1-bit register, initialized to 0
M (Multiplicand): n-bit register holding the multiplicand

At each step, examine the LSB of Q (Q₀) and Q₋₁:

Q₀	Q₋₁	Operation
0	0	No arithmetic operation. Arithmetic Shift Right.
0	1	Add M to A. Arithmetic Shift Right.
1	0	Subtract M from A. Arithmetic Shift Right.
1	1	No arithmetic operation. Arithmetic Shift Right.

Numerical Example: 7 × 3

Step	Q₀Q₋₁	Operation	A	Q	Q₋₁
0	–	Initial	0000	0011	0
1	10	A = A - M	A=0000-0111=1001	1001	0011
		ASR	1100	1001	1
2	11	No op	1100	1001	1
		ASR	1110	0100	1
3	01	A = A + M	A=1110+0111=0101	0101	0100
		ASR	0010	1010	0
4	00	No op	0010	1010	0
		ASR	0001	0101	0

Result: A:Q = 0001:0101 = 21 (decimal). ✓

Code Example

python

def booth_multiply(M: int, Q: int, bits: int = 4) -> int:
    A = 0
    Q_1 = 0
    mask = (1 << bits) - 1
    M_neg = ((~M) + 1) & mask  # two's complement negation

    for step in range(bits):
        q0 = Q & 1
        if q0 == 0 and Q_1 == 1:
            A = (A + M) & mask
        elif q0 == 1 and Q_1 == 0:
            A = (A + M_neg) & mask
        
        # arithmetic shift right (A:Q:Q_1)
        lsb_A = A & 1
        msb_A = (A >> (bits - 1)) & 1
        A = (A >> 1) | (msb_A << (bits - 1))
        Q = (Q >> 1) | (lsb_A << (bits - 1))
        Q_1 = q0

    result = (A << bits) | Q
    sign = (result >> (2 * bits - 1)) & 1
    return result if sign == 0 else result - (1 << (2 * bits))

Interview Questions

Why is Booth's Algorithm used in hardware multiplication?

Booth's Algorithm allows multiplication of signed binary numbers using only addition, subtraction, and shifting operations. It reduces the number of partial products, especially when the multiplier has consecutive 1s or 0s, making it efficient for hardware implementation in ALUs.

How does Booth's Algorithm handle negative multipliers?

Unlike simple multiplication algorithms, Booth's Algorithm naturally handles negative multipliers because it works with two's complement representation. The algorithm examines pairs of bits (Q₀ and Q₋₁) and subtracts M when it sees a '10' pattern, which effectively handles the sign extension needed for negative numbers.

What is the difference between Booth's Algorithm and the modified Booth's Algorithm?

The modified (Booth-2/radix-4) algorithm examines 3 bits at a time (overlapping by 1), reducing the number of partial products by half. While standard Booth's does n steps for n-bit numbers, the modified version does n/2 steps, using operations like +M, +2M, -M, -2M instead of just +M and -M.