Booth Multiplier Explained (With Examples)

TL;DR: Booth recoding rewrites runs of multiplier 1 bits as signed digits. Radix-2 Booth examines the pair $(Q_0,Q_{-1})$ on each iteration: 01 adds the multiplicand, 10 subtracts it, and 00 or 11 does nothing before an arithmetic right shift. A width-safe $n$-bit implementation sign-extends the multiplicand and uses an $(n+1)$-bit accumulator, avoiding the special failure at the most-negative value. Radix-4 modified Booth reduces the partial-product count to about half by choosing from $0,\pm M,\pm2M$.

Binary multiplication can be built from shifts and additions. The challenge is not that two’s-complement operands are impossible to multiply without Booth—they are not—but that sign handling and partial-product generation must be designed correctly.

Booth’s method gives a uniform signed recoding and compresses runs of 1 bits. It is useful in two different architectures:

• an iterative multiplier, which reuses one adder across several cycles
• a parallel multiplier, which generates recoded partial products and reduces them with an adder/compressor tree

Those architectures share the recoding idea but have different latency, area, and timing.

The Run-of-Ones Identity

Consider a run of binary ones from bit $j$ through bit $k$, where $k\ge j$:

For example:

Ordinary unsigned shift-and-add would add four shifted copies of the multiplicand for 1111. Booth recoding represents that run with a subtraction at its low boundary and an addition at the position above its high boundary.

This does not guarantee fewer nonzero operations for every bit pattern. A long run benefits; isolated or alternating ones can provide no reduction and can increase the number of add/subtract decisions. A fixed-latency radix-2 iterative multiplier still performs $n$ iterations—the recoding changes the arithmetic action within each iteration, not automatically the cycle count.

Radix-2 Booth Recoding

Append an implicit zero below the multiplier:

At iteration $i$, inspect the current least-significant multiplier bit $Q_0$ and the saved previous bit $Q_{-1}$:

Then arithmetic-shift the combined accumulator, multiplier, and saved bit right by one position.

The pair detects boundaries:

• 10 marks the low end of a run of ones, so subtract
• 01 marks the high end after shifting through the run, so add
• equal adjacent bits are inside a constant run, so no arithmetic action is needed

The table’s bit order matters. Some texts print $(Q_{-1},Q_0)$ instead; that reverses the row labels. Always state the convention.

A Width-Safe Iterative Datapath

Let both input operands be signed $n$-bit two’s-complement values:

• $M$: multiplicand
• $Q$: multiplier

Use:

• $M_e$: $M$ sign-extended to $n+1$ bits
• $A$: an $n+1$-bit accumulator, initially zero
• $Q$: the $n$-bit multiplier register
• $Q_{-1}$: one saved bit, initially zero
• an iteration counter from 0 to $n-1$

For each of $n$ iterations:

1. inspect $(Q_0,Q_{-1})$
2. if 01, set $A \leftarrow A+M_e$
3. if 10, set $A \leftarrow A-M_e$
4. if 00 or 11, leave $A$ unchanged
5. arithmetic-shift the concatenation $\{A,Q,Q_{-1}\}$ right by one

After $n$ iterations, discard the redundant top sign-extension bit of $A$. The remaining $n$ bits of $A$ concatenated with $Q$ form the signed $2n$-bit product.

Why the extra accumulator bit matters

For an $n$-bit two’s-complement number, the representable range is:

The positive magnitude of $-2^{n-1}$ does not fit in $n$ bits. A design that precomputes -M at only $n$ bits can therefore fail when $M$ is the most-negative value. Sign-extending $M$ and using an $(n+1)$-bit accumulator makes both $M_e$ and $-M_e$ representable during the algorithm.

Worked Example: $-3 \times 5$

Use 4-bit operands:

Sign-extend the multiplicand to five bits:

Initialize:

The table shows the pair and arithmetic action, followed by the state after the combined arithmetic right shift:

After four iterations, discard the redundant high sign bit of $A$:

As an 8-bit two’s-complement value:

which matches $-3\times5$.

Trace one combined shift

After the first subtraction:

Arithmetic right shift copies the accumulator sign bit into the new top position and moves every other bit one place:

The shift must act on the whole concatenated register. Shifting $A$ and $Q$ independently would lose the bit transfer across their boundary.

Hardware Blocks

A reusable iterative Booth multiplier contains:

• an $(n+1)$-bit multiplicand register or input path
• an $(n+1)$-bit accumulator
• an $n$-bit multiplier register plus $Q_{-1}$
• an $(n+1)$-bit adder/subtractor
• pair-decode control for add, subtract, or hold
• a combined arithmetic shifter
• an iteration counter and busy/done control

The adder is reused across all iterations, which saves area relative to a fully parallel multiplier but costs latency. Whether one iteration takes one clock or several microsteps depends on the controller and datapath.

The ALU component can supply add/subtract behavior in a teaching circuit, but confirm its width and signed overflow behavior. A shift register illustrates serial movement; the Booth datapath needs a wider combined register whose top bit is sign-filled.

Radix-4 Modified Booth

Radix-4 modified Booth examines overlapping 3-bit windows and recodes two multiplier bits per digit. Append a zero at the low end and sign-extend the multiplier at the high end as required.

For a window $(Q_{2i+1},Q_{2i},Q_{2i-1})$:

The available multiples are:

$2M$ is a left shift, so these partial products are relatively economical to generate. For an $n$-bit multiplier, radix-4 produces approximately $\lceil n/2\rceil$ recoded digits instead of $n$ radix-2 digits.

That reduction can:

• halve the iterations in an iterative radix-4 design
• reduce the number of partial-product rows in a parallel design

It does not make the complete multiplier twice as fast automatically. Recoding, sign correction, partial-product generation, reduction, routing, final addition, and pipelining all contribute to timing.

Parallel Reduction: Wallace, Dadda, and Final Adders

A high-throughput multiplier can generate partial products in parallel, reduce their columns with carry-save compressors, and finish with a carry-propagate adder.

Wallace and Dadda trees are two classic reduction schedules. Modified Booth recoding can be placed before such a tree to reduce the number of rows. The final adder might use a carry-lookahead, parallel-prefix, carry-select, or another structure selected for the target technology.

“Combinational” does not necessarily mean “one processor cycle.” A wide multiplier may be pipelined across several stages to meet a target clock period, and some processors use iterative units for area or power reasons. The architecture is an implementation choice.

Booth vs Other Multiplier Structures

There is no universal winner. Operand width, target cells or FPGA resources, throughput, latency, area, power, and verification effort determine the right structure.

Build It in DigiSim

For a 4-bit teaching implementation:

1. Create a 5-bit accumulator from visible storage elements.
2. Sign-extend the 4-bit multiplicand to 5 bits.
3. Use a 5-bit add/subtract path.
4. Store the 4-bit multiplier and a separate $Q_{-1}$ bit.
5. Decode (Q0, Q−1) into add, subtract, and hold.
6. Implement the arithmetic shift across the complete {A,Q,Q−1} state.
7. Count exactly four iterations.
8. Expose busy, done, and the final 8-bit product.

Step through the $-3\times5$ table and compare every post-shift state. A mismatch on the first iteration usually points to reversed pair order or subtraction polarity; a mismatch after a negative accumulator shift usually points to logical rather than arithmetic shift.

Verification Checklist

For exhaustive verification of a small $n$-bit multiplier, test all:

input pairs against a signed reference product represented at $2n$ bits.

At minimum, include:

• $0\times x$ and $1\times x$
• positive × positive
• positive × negative
• negative × positive
• negative × negative
• maximum positive values
• the most-negative value $-2^{n-1}$
• $-2^{n-1}\times -1$
• multiplier patterns 0000, 1111, 0101, and 1010
• reset or restart while busy

Also assert:

• exactly $n$ radix-2 iterations occur
• done is emitted once per accepted operation
• inputs are either latched or required to remain stable by contract
• the result is not consumed before valid
• the combined shift preserves the accumulator sign

An ideal functional simulation proves arithmetic sequencing, not the maximum hardware clock rate. Use static timing analysis after mapping the design to its target.

Continue Learning

Review two’s-complement arithmetic for sign extension and range, then compare ripple-carry addition with carry-lookahead structures.

Andrew D. Booth introduced the uniform signed method in his 1951 paper, “A Signed Binary Multiplication Technique”. The central recoding remains relevant, but a professional implementation still needs explicit widths, a defined latency contract, exhaustive signed testing, and target-specific timing analysis.