Combinational multipliers: Exercises — Hardware deep dive

Before we start, three words we will lean on constantly:

Bit — a single binary digit, always either $0$ or $1$ .
Partial product $P P_{j}$ — the row you get by multiplying the whole multiplicand $A$ by one multiplier bit $b_{j}$ , then sliding it left by $j$ columns. (Slide left = multiply by $2^{j}$ .)
Column — a vertical stack of bits that all carry the same weight $2^{k}$ ; the multiplier adds each column and pushes any overflow (the carry) to the next column up.

The figure above is the picture we return to again and again: AND gates make the dots, dots stack into columns, columns get added with carries flowing left. Keep it in mind.

Level 1 — Recognition

L1.1 — Spot the gate

Which single logic gate produces one partial-product bit $p_{ij} = a_{i} b_{j}$ ? Give the gate and its 1-line truth-table justification.

Recall Solution

AND gate. Multiplying two bits: $1 \times 1 = 1$ , and every other combination gives $0$ . That truth table ( $0 \cdot 0 = 0, 0 \cdot 1 = 0, 1 \cdot 0 = 0, 1 \cdot 1 = 1$ ) is exactly the AND gate. So == $a_{i} \cdot b_{j} = a_{i} \land b_{j}$ ==.

L1.2 — Count the ANDs

An $n$ -bit number times an $m$ -bit number. How many AND gates are needed to form all partial-product bits?

Recall Solution

One AND per pair $(a_{i}, b_{j})$ . There are $n$ choices of $i$ and $m$ choices of $j$ , so $number of ANDs = n \times m .$ For $4 \times 4$ that is $4 \times 4 = 16$ AND gates.

L1.3 — Output width

How many bits does the product of a $6$ -bit number and a $3$ -bit number need?

Recall Solution

The product is at most $(2^{6} - 1) (2^{3} - 1) = 63 \times 7 = 441 < 512 = 2^{9}$ . So it fits in == $n + m = 6 + 3 = 9$ == bits.

Level 2 — Application

L2.1 — Full $2 \times 2$ multiply

Compute $A = 1 1_{2}, B = 1 1_{2}$ using the column method (this is $3 \times 3$ ). Give $P_{3} P_{2} P_{1} P_{0}$ .

Recall Solution

Every $a_{i} b_{j} = 1$ here (all bits are 1).

Column $2^{0}$ : just $a_{0} b_{0} = 1 \Rightarrow P_{0} = 1$ .
Column $2^{1}$ : $a_{1} b_{0} + a_{0} b_{1} = 1 + 1 = 1 0_{2} \Rightarrow P_{1} = 0$ , carry $c_{1} = 1$ .
Column $2^{2}$ : $a_{1} b_{1} + c_{1} = 1 + 1 = 1 0_{2} \Rightarrow P_{2} = 0$ , carry $c_{2} = 1$ .
Column $2^{3}$ : $c_{2} = 1 \Rightarrow P_{3} = 1$ . $P = 100 1_{2} = 9. ✓ (3 \times 3 = 9)$

L2.2 — A zero partial product

Compute $A = 10 1_{2} (= 5)$ times $B = 1 0_{2} (= 2)$ .

Recall Solution

$P P_{0}$ ( $b_{0} = 0$ ): AND with $0$ everywhere → $000$ .
$P P_{1}$ ( $b_{1} = 1$ ): copy of $A = 101$ , shifted left by 1 → $101 0_{2}$ .
Sum: $000 + 1010 = 101 0_{2} = 10$ . $✓ (5 \times 2 = 10)$ . The whole point of a $b_{j} = 0$ row is that it contributes nothing — AND with 0 kills it.

L2.3 — Three-bit product

Compute $A = 11 0_{2} (= 6)$ times $B = 10 1_{2} (= 5)$ , listing the three partial products.

Recall Solution

$A = 110$ .

$P P_{0}$ ( $b_{0} = 1$ ): $110$ (shift 0).
$P P_{1}$ ( $b_{1} = 0$ ): $000$ .
$P P_{2}$ ( $b_{2} = 1$ ): $110$ shifted left by 2 → $11000$ . Add: $00110 + 00000 + 11000 = 1111 0_{2} = 30$ . $✓ (6 \times 5 = 30)$ .

Level 3 — Analysis

L3.1 — Why a half adder in column $2^{1}$ of a $2 \times 2$ ?

In the $2 \times 2$ array, column $2^{1}$ holds bits $a_{1} b_{0}$ and $a_{0} b_{1}$ . Explain why it is summed by a half adder while column $2^{2}$ needs a full adder.

Recall Solution

A half adder adds two bits and has no carry-in. A full adder adds three bits: two plus a carry-in.

Column $2^{1}$ has exactly two bits ( $a_{1} b_{0}, a_{0} b_{1}$ ) and receives no carry from a lower column (column $2^{0}$ produced only one bit, no overflow). Two bits, no carry-in → half adder.
Column $2^{2}$ has $a_{1} b_{1}$ plus the carry $c_{1}$ coming up from column $2^{1}$ . Its stack can reach three bits → needs a full adder. So the number of bits landing in a column dictates the adder type.

L3.2 — Where does the top bit come from?

For an $n$ -bit $\times m$ -bit multiply, which single AND term is responsible for possibly setting the highest-weight bit, and what weight is it?

Recall Solution

In $P = \sum_{i, j} (a_{i} \land b_{j}) 2^{i + j}$ the largest exponent occurs at $i = n - 1, j = m - 1$ : $2^{(n - 1) + (m - 1)} = 2^{n + m - 2} .$ This lone term $a_{n - 1} b_{m - 1}$ can already set bit $n + m - 2$ . After a carry ripples once more it can reach bit $n + m - 1$ — which is why the product needs $n + m$ bits and no more.

L3.3 — Delay reasoning

Explain, in terms of the longest signal path, why an $n \times n$ array multiplier has delay $O (n)$ and not $O (n^{2})$ , even though it has $\sim n^{2}$ cells.

Recall Solution

Delay counts the longest path a signal must travel, not the number of gates. The critical path enters at a top corner, crosses down the diagonal of the grid (about $n$ cells), then runs along the final carry chain at the bottom (about $n$ cells). That is $\sim 2 n$ adder delays, i.e. $O (n)$ . The other $\sim n^{2}$ cells compute in parallel, off the critical path, so they add area but not delay. Area $= O (n^{2})$ , delay $= O (n)$ .

Level 4 — Synthesis

L4.1 — Boolean expressions for a $2 \times 2$ multiplier

Derive closed Boolean formulas for $P_{0}, P_{1}, P_{2}, P_{3}$ of a $2 \times 2$ multiplier ( $A = a_{1} a_{0}$ , $B = b_{1} b_{0}$ ) using only AND ( $\land$ ), XOR ( $\oplus$ ), and the intermediate carry $c_{1}$ .

Recall Solution

From the column table: $P_{0} = a_{0} \land b_{0}$ $P_{1} = (a_{1} \land b_{0}) \oplus (a_{0} \land b_{1}), c_{1} = (a_{1} \land b_{0}) \land (a_{0} \land b_{1})$ $P_{2} = (a_{1} \land b_{1}) \oplus c_{1}, c_{2} = (a_{1} \land b_{1}) \land c_{1}$ $P_{3} = c_{2}$ Check with $A = B = 11$ : $P_{0} = 1, P_{1} = 1 \oplus 1 = 0, c_{1} = 1, P_{2} = 1 \oplus 1 = 0, c_{2} = 1, P_{3} = 1 \Rightarrow 100 1_{2} = 9. ✓$

L4.2 — Count the cells for a $4 \times 4$ array multiplier

Estimate the number of AND gates and the number of adder cells (half + full) in a plain $4 \times 4$ array multiplier.

Recall Solution

AND gates: one per pair $\Rightarrow 4 \times 4 = 16$ .
Adder cells: a standard $n \times n$ array uses $(n - 1)$ rows of adders, each row about $n$ cells, so $\approx n (n - 1) = 4 \times 3 = 12$ adder cells (mix of half and full). This is the $O (n^{2})$ area law in action: $16$ ANDs $+ \sim 12$ adders scales like $n^{2}$ .

L4.3 — Design choice: array vs. tree

You must multiply two $16$ -bit numbers and latency is critical. State which summation structure you would choose over a plain array, name the two building blocks it uses, and give its depth order.

Recall Solution

Replace the rippling column adders with a carry-save adder stage feeding a Wallace (or Dadda) tree.

Building blocks: carry-save adders (which defer carries instead of rippling them) and a final carry-propagate adder at the very end.
Depth: the tree reduces the pile of partial products in $O (lo g n)$ levels instead of $O (n)$ . For $n = 16$ , $lo g_{2} 16 = 4$ reduction levels — far shallower than a $\sim 32$ -stage ripple.

Level 5 — Mastery

L5.1 — Full $3 \times 3$ -bit array trace

Multiply $A = 10 1_{2} (= 5)$ by $B = 01 1_{2} (= 3)$ . Show all three partial products, then add columns with carries and give the final 6-bit product $P_{5} \dots P_{0}$ .

Recall Solution

$A = 101$ .

$P P_{0}$ ( $b_{0} = 1$ ): $000101$ (weight $2^{0}$ ).
$P P_{1}$ ( $b_{1} = 1$ ): $101$ shifted left 1 → $001010$ .
$P P_{2}$ ( $b_{2} = 0$ ): $000000$ . Column addition (right to left), weights $2^{0} .. 2^{5}$ :

weight	$2^{0}$	$2^{1}$	$2^{2}$	$2^{3}$
$P P_{0}$	1	0	1	0
$P P_{1}$	0	1	0	1
$P P_{2}$	0	0	0	0

Adding: $2^{0} : 1$ , $2^{1} : 1$ , $2^{2} : 1$ , $2^{3} : 1$ , rest $0$ → $P = 00111 1_{2} = 15. ✓ (5 \times 3 = 15)$

L5.2 — Width bound at the extreme

For two $4$ -bit numbers, compute the maximum product $15 \times 15$ , write it in binary, and confirm it fits in exactly $n + m$ bits with none to spare.

Recall Solution

$15 \times 15 = 225$ . In binary $225 = 1110000 1_{2}$ , which is 8 bits. Here $n + m = 4 + 4 = 8$ , and $225 < 256 = 2^{8}$ but $225 \geq 128 = 2^{7}$ , so it genuinely occupies bit $7$ (the top of the 8-bit field). The $n + m$ bound is tight — you cannot drop a bit.

L5.3 — Signed multiplication pitfall

You built an unsigned array multiplier. You feed it $A = 110 1_{2}$ and $B = 001 1_{2}$ intending $- 3 \times 3$ in two's complement. What product does the unsigned array give, why is it wrong for signed inputs, and what standard fix repairs it?

Recall Solution

What the unsigned array computes: it treats $110 1_{2}$ as the unsigned value $13$ , so it returns $13 \times 3 = 39 = 10011 1_{2}$ (8-bit: $00100111$ ).
Why wrong: in two's complement $110 1_{2} = - 3$ , so the intended answer is $- 9$ . The array has no idea the top bit means "negative"; it just weights it as $+ 2^{3}$ . So sign is mishandled.
The fix: use Booth's algorithm, which recodes the multiplier to handle the sign bit correctly (or sign-extend and correct the last partial product). Booth also reduces the number of partial products, a bonus for speed.

L5.4 — Tie it all together

In one sentence per blank, connect the four mnemonic ideas ("AND makes it, ADD stacks it, SHIFT places it, CARRY paces it") to the four hardware realities: gate type, adder type, weight, overflow.

Recall Solution

AND makes it → each partial-product bit is one AND gate ( $a_{i} \land b_{j}$ ).
ADD stacks it → full/half adders sum the bits that share a column.
SHIFT places it → the weight $2^{i + j}$ decides which column a bit lands in.
CARRY paces it → column overflow ripples upward and sets the worst-case delay $O (n)$ .

Recall Quick self-quiz

One AND per what pair? ::: Per $(a_{i}, b_{j})$ — that's $n \times m$ ANDs total. Product of $n$ -bit and $m$ -bit needs how many bits? ::: $n + m$ . Delay order of an $n \times n$ array multiplier? ::: $O (n)$ (longest path = diagonal + bottom carry chain). What compresses partial products to $O (lo g n)$ depth? ::: A carry-save / Wallace (Dadda) tree, plus one final carry-propagate adder. Fix for signed multiplication? ::: Booth's algorithm (or sign-extend and correct).

Connections

Combinational Multipliers — parent topic
AND Gate — forms every partial-product bit
Half Adder / Full Adder — the column-summing cells
Ripple Carry Adder — the carry chain limiting array speed
Carry Save Adder / Wallace Tree — faster $O (lo g n)$ summation
Booth's Algorithm — correct signed multiplication
Binary Number System — positional weights $2^{i}$
Combinational Circuits — no clock, pure gate delay