Multiplication Algorithms

Introduction

Binary multiplication is considerably more complex than addition, requiring multiple addition steps and careful handling of partial products. While addition can be completed in a single clock cycle using a fast adder, multiplication of two n-bit numbers produces a 2n-bit result and traditionally requires n addition steps. Over decades of research, computer engineers have developed increasingly sophisticated algorithms and hardware structures to accelerate this critical operation — from the basic shift-and-add approach to Booth's algorithm and parallel array multipliers.

Understanding multiplication algorithms is essential because multiplication appears everywhere in computing: array indexing, floating-point calculations, graphics transformations, signal processing filters, and cryptographic operations all depend heavily on fast multiplication.

Basic Shift-and-Add Algorithm

Binary multiplication follows the same principle as longhand decimal multiplication. Each bit of the multiplier is examined one at a time, starting from the least significant bit. If the bit is 1, the multiplicand (appropriately shifted) is added to a running partial product. If the bit is 0, nothing is added (or equivalently, zero is added).

For two 4-bit numbers, the process works as follows. Consider multiplying M = 1101 (13) by Q = 1011 (11):

Verification: 13 × 11 = 143. Correct!

Hardware Implementation

The hardware uses three registers: the Multiplicand register (M), the Multiplier register (Q), and the Accumulator (A) for the partial product. The algorithm for n-bit multiplication:

1. Initialize: A = 0, load M and Q
2. Repeat n times:

• If Q0 (LSB of multiplier) = 1, add M to A
• Shift the combined A-Q register right by 1 bit (the carry from addition goes into MSB of A, LSB of A shifts into MSB of Q)

1. Result is in the combined A-Q register (2n bits)

This requires n clock cycles — one per multiplier bit. For a 32-bit multiplication, that means 32 cycles, which is quite slow.

Booth's Algorithm

Booth's algorithm (1951) is a clever improvement that handles signed numbers directly and can be faster for multipliers with long runs of consecutive 1s. The key insight: instead of adding the multiplicand for each 1 in the multiplier, we can treat a run of 1s (like 01111110) as the difference between two powers of two (10000000 - 00000010). This replaces multiple additions with one subtraction and one addition.

How Booth's Algorithm Works

The algorithm examines pairs of adjacent multiplier bits (current bit Qi and previous bit Qi-1, where Q-1 = 0 initially):

After each step, arithmetically shift the A-Q register right by 1 bit (preserving the sign bit).

Worked Example

Multiply +7 (0111) by -3 (1101) using Booth's algorithm with 4-bit numbers:

M = 0111 (+7), Q = 1101 (-3), A = 0000, Q-1 = 0

• Step 1: Q0=1, Q-1=0 → Subtract M. A = 0000-0111 = 1001. Shift right: A-Q = 1100 1110, Q-1=1
• Step 2: Q0=0, Q-1=1 → Add M. A = 1100+0111 = 0011. Shift right: A-Q = 0001 1111, Q-1=0
• Step 3: Q0=1, Q-1=0 → Subtract M. A = 0001-0111 = 1010. Shift right: A-Q = 1101 0111, Q-1=1
• Step 4: Q0=1, Q-1=1 → No operation. Shift right: A-Q = 1110 1011, Q-1=1

Result: 1110 1011. In 8-bit two's complement, this is -21. Check: 7 × (-3) = -21. Correct!

Booth's algorithm works directly with signed two's complement numbers without any special conversion, which is a significant advantage over the basic shift-and-add approach.

Array Multiplier

The array multiplier takes a completely different approach: instead of sequential shift-and-add, it generates all partial products simultaneously and adds them all in one pass through a structured array of adders. This trades sequential time for parallel hardware.

For n-bit multiplication, an array multiplier uses:

• n² AND gates to generate all partial product bits (each bit Pi,j = Ai AND Bj)
• An array of approximately n(n-1) full adders arranged in rows to sum the partial products

The result is available after passing through approximately 2n full adder delays — much faster than n sequential add-and-shift cycles, but at the cost of substantially more hardware. A 32-bit array multiplier would require about 1024 AND gates and nearly 1000 full adders.

Wallace Tree Multiplier

The Wallace tree multiplier further reduces delay by using carry-save adders (CSAs) arranged in a tree structure to reduce the partial products in parallel. Instead of adding partial products row by row (which takes O(n) time), the Wallace tree groups them in threes, reduces each group to two numbers using a CSA, then repeats. This reduces n partial products to just two numbers in O(log n) steps. A final fast adder (CLA) produces the result.

For a 32-bit Wallace tree multiplier, the partial products are reduced to two numbers in about 5 CSA stages (log₃/₂(32) ≈ 5), followed by a single fast addition. Total delay is approximately 8-10 gate delays instead of 32 sequential cycles.

Modified Booth Encoding (Radix-4)

Modern multipliers often use modified Booth encoding (radix-4 Booth), which examines 3 bits at a time and generates partial products of 0, +M, -M, +2M, or -2M. This halves the number of partial products (from n to n/2), reducing both the Wallace tree depth and the hardware area. The operation 2M is achieved by a simple left shift. Nearly all modern high-performance multipliers use radix-4 Booth encoding combined with Wallace tree reduction.

Performance Comparison

Key Takeaways

1. Shift-and-add multiplication examines one multiplier bit per cycle, requiring n cycles for n-bit numbers
2. Booth's algorithm handles signed numbers directly and reduces operations for multipliers with runs of 1s
3. Array multipliers generate all partial products in parallel using n² AND gates but require large hardware area
4. Wallace tree multipliers reduce partial products in O(log n) time using carry-save adder trees
5. Modified Booth encoding (radix-4) halves the number of partial products, reducing both area and delay
6. Modern CPUs achieve single-cycle throughput for multiplication using pipelined Wallace tree designs
7. The choice of multiplication algorithm depends on the balance between speed, power, and silicon area