Booth’s Algorithm for Signed Binary Multiplication

Booth’s multiplication algorithm optimizes the multiplication of signed binary integers in two’s complement representation by minimizing the number of required addition and subtraction operations. By scanning the multiplier and identifying contiguous blocks of binary ones, the algorithm replaces multiple sequential additions with a single addition and subtraction. This approach eliminates the need for separate sign-handling logic, reduces hardware switching activity, and speeds up the calculation process compared to traditional shift-and-add multiplication.

The Underlying Mathematical Principle

Traditional binary multiplication evaluates each bit of the multiplier individually: if a bit is 1, the multiplicand is added to the running total; if 0, no addition occurs. In cases where the multiplier contains long sequences of 1s, standard multiplication performs an addition for every single bit.

Booth’s algorithm exploits the mathematical property that a sequence of \(N\) consecutive ones can be represented as the difference between two powers of two:

\[2^n + 2^{n-1} + 2^{n-2} + \dots + 2^m = 2^{n+1} - 2^m\]

For example, the binary sequence 01110 (decimal 14) can be evaluated as:

\[2^3 + 2^2 + 2^1 = 8 + 4 + 2 = 14\]

Instead of performing three additions, Booth’s algorithm treats this as:

\[2^4 - 2^1 = 16 - 2 = 14\]

This reduces the workload to one subtraction at the start of the sequence and one addition at the end.

How the Algorithm Operates

To implement this logic, the algorithm inspects adjacent bit pairs of the multiplier, tracking the current bit (\(Q_i\)) and the immediately preceding bit (\(Q_{i-1}\)), starting with an implicit \(Q_{-1} = 0\). For each step, it takes one of four actions based on the transition:

1. 10 (Beginning of a sequence of ones): Subtract the multiplicand from the accumulator, then perform an arithmetic right shift.
2. 01 (End of a sequence of ones): Add the multiplicand to the accumulator, then perform an arithmetic right shift.
3. 11 (Middle of a sequence of ones): Perform no addition or subtraction; only execute an arithmetic right shift.
4. 00 (Middle of a sequence of zeros): Perform no addition or subtraction; only execute an arithmetic right shift.

Native Support for Signed Numbers

A major efficiency gain of Booth’s algorithm is its native handling of two’s complement signed integers. In standard array multipliers, negative operands must be converted to positive values, multiplied, and then conditionally negated based on the sign bits.

Booth’s algorithm bypasses this extra overhead entirely. Because it relies on arithmetic right shifts (which preserve the most significant bit to maintain sign integrity) and mathematically accounts for the negative weight of the most significant bit in two’s complement format, it processes positive and negative numbers identically without extra sign-detection hardware.

Performance and Hardware Advantages

• Reduced Adder Cycles: In scenarios with large clusters of 1s (e.g., negative numbers with leading ones or large positive numbers), the number of operations requiring an adder is cut down substantially.
• Uniform Processing: The exact same hardware path handles positive numbers, negative numbers, and mixed-sign multiplication.
• Foundation for Higher Radix Multipliers: The standard (Radix-2) Booth algorithm forms the basis for Modified Booth’s Algorithm (Radix-4), which inspects three bits at a time. Radix-4 guarantees that the number of partial products is halved regardless of the bit pattern, making it a standard design choice in modern ALU and digital signal processor (DSP) architectures.