Booth’s Algorithm and the Design of Fast Multipliers

Booth’s algorithm is a signed multiplication technique that reduces the number of non-zero partial products needed to form a product, which directly improves multiplier speed in hardware implementations. The core idea is to transform the multiplier bits into a sequence of smaller “control decisions” (recoding) so that long runs of 0s or 1s in the multiplier produce fewer partial-product generation events than straightforward bitwise multiplication. This is especially important in fast multiplier design, where the dominant cost often comes from (i) generating many partial products and (ii) compressing them efficiently using adder-tree structures (e.g., Wallace/Dadda-style compressors).

From a hardware-design perspective, Booth-style recoding typically:

1. Decreases the number of partial products compared with naive multiplication, because it encodes groups of bits into operations like $0, \pm A, \pm 2A$ rather than $0$ or $\pm A$ per single bit.
2. Enables regular, pipelinable partial-product generators (recoder + add/subtract + shifts), which can be matched to fast compression trees.
3. Better supports signed two’s complement multiplication by embedding sign handling into the recoding scheme, avoiding extra correction complexity later.

Key terms

• Booth recoding
• partial product
• two’s complement
• adder tree
• Wallace tree

Academic note: “Fast multipliers” are usually optimized by reducing partial-product count and/or reducing compressor depth and critical-path delay in the adder tree.

1) From naive multiplication to Booth-style recoding

A classical bit-matrix multiplier treats the multiplier $B$ as a sequence of bits and generates partial products by ANDing/replicating the multiplicand $A$ with each multiplier bit (with appropriate shifting), producing up to $n$ partial products for $n$-bit operands. In signed two’s complement multiplication, direct generation plus sign-extension increases the complexity and may increase the number of effective partial-product bits that must be compressed.

Booth’s method replaces “one partial product per multiplier bit” with “partial products generated per recoding group.” The algorithm examines patterns in the multiplier—particularly transitions between consecutive bits—and converts them into a shorter sequence of operations that update an accumulating partial-product term.

Conceptual recoding via transitions (radix-2 view)

For radix-2 Booth recoding, the control decisions are based on pairs of bits (commonly $(B_i, B_{i-1})$), which enables the multiplication to add $+A$ when it detects an upward transition and add $-A$ when it detects a downward transition, with “no action” when bits remain constant. This means runs of repeated bits (many $0$s or many $1$s) generate fewer events.

Mermaid overview (conceptual signal flow):

2) Role of Booth algorithm in fast multiplier design

Fast multiplier performance is largely determined by the critical path through:

1. Partial-product generation (recoding + controlled shifts + add/sub selection),
2. Partial-product compression (many-to-two reduction using carry-save techniques),
3. Final carry-propagate addition (often the last step).

Booth’s algorithm primarily targets (1) and (2) by reducing the number of non-zero partial products and enforcing a structured generation pattern that suits compressor trees.

2.1 Reduction in partial-product count

If you use radix-$k$ Booth recoding (e.g., radix-4 groups bits in chunks), each recoding digit can represent operations of the form $\{0, \pm A, \pm 2A, ...\}$ depending on the digit set. Compared to radix-1 bitwise generation, radix-4 typically reduces the number of partial products by roughly a factor close to $2$ (because you process two multiplier bits per recoding digit).

This reduction matters because the compressor depth depends on how many partial-product rows you must combine.

2.2 Improved regularity for compression trees

Adder trees like Wallace or Dadda rely on repeatedly grouping and compressing partial products. Fewer partial-product rows mean:

• fewer compressor stages,
• less routing congestion,
• typically improved timing.

Booth recoding also yields a more uniform set of shifted terms (e.g., $A$ or $2A$ aligned at predictable positions), which simplifies the wiring into carry-save adders.

2.3 Signed multiplication without “late” correction

In two’s complement multiplication, sign handling can otherwise require careful sign extension and correction terms. Booth recoding incorporates sign into the digit set (using $\pm$ operations), reducing the need for extra corrective add/sub afterward—an advantage for both area and speed.

Pro Tip: In a synthesis-oriented design, the Booth recoder is often implemented as a small combinational block (or pipelined logic), while the remainder of the multiplier benefits from the reduced partial-product count to meet tighter timing.

3) Radix-4 (modified Booth) and design implications

Radix-4 modified Booth recoding processes overlapping groups of three bits $(B_{2i+1}, B_{2i}, B_{2i-1})$ to produce digits that select among $\{0, \pm A, \pm 2A\}$. Hardware implication: the partial-product generator can be built from:

• a small mux/selector for $0$, $A$, $2A$,
• an add/sub mechanism to handle sign (negation via two’s complement),
• simple shifting (wiring) rather than full barrel shifting.

Mermaid decision view:

Why this matters for speed: Because $A$ and $2A$ share the same bit pattern shifted by one position, they can be generated with minimal additional logic, and compression begins with fewer rows.

4) Relationship to Wallace-tree multiplier architecture

A Wallace tree reduces partial products by applying carry-save adders in parallel. Its key performance advantage is that it often achieves logarithmic-ish reduction in levels of compression relative to the number of partial-product rows, using aggressive parallelism.

Booth’s algorithm complements Wallace trees:

• Booth reduces the number of partial-product rows by recoding the multiplier,
• the Wallace tree then compresses those reduced rows faster (fewer stages or less work per stage),
• the final adder is still required, but overall critical path can shrink because the compressor tree becomes shallower.

Conceptual combined architecture: