Worked examples — Combinational multipliers

Before anything, a reminder of the three tiny machines we lean on, all built from picture-simple truth tables:

---

The scenario matrix

Every multiplication a combinational multiplier can face falls into one of these case classes. The examples below are labelled with the cell they cover, so you can see the whole space is filled.

#	Case class	What makes it special	Covered by
C1	Zero operand	one input all-zeros → every AND is $0$	Ex. 1
C2	Multiply by power of two	multiplier is a single $1$ → pure left shift, no adding	Ex. 2
C3	Generic mixed bits	a few ones scattered → real partial-product summing	Ex. 3
C4	All-ones (worst carrying)	every AND $=1$ → longest carry ripple, max delay	Ex. 4
C5	Maximum-value / width check	product hits the $n+m$-bit ceiling	Ex. 5
C6	Non-square $n\ne m$	rectangular grid, unequal shifts	Ex. 6
C7	Real-world word problem	map a story to bits, sanity-check units	Ex. 7
C8	Exam twist (spot the carry-into-carry)	a column that overflows twice	Ex. 8
C9	Signed / degenerate: negative operand	naive AND array gives the wrong answer; why & the fix	Ex. 9

The figure below is the map we will reuse: the $2\times 2$ dot diagram showing which AND product lands in which column.

---

Example 1 — Zero operand · Cell C1

Forecast: guess the product and guess how many AND gates fire before reading on.

1. Form every partial product. Each bit is $p_{ij}=a_i\wedge b_j$. Every $b_j=0$. Why this step? The AND gate outputs $1$ only when both inputs are $1$; here one input is always $0$, so every AND outputs $0$. Zero gates "fire".
2. The whole grid is zeros, so all six columns sum to $0$. Why this step? Adding zeros anywhere leaves zero — no carries are ever born.
3. Product $=000000_2=0$.

Verify: $5\times 0=0$, and the multiplier width would give $n+m=6$ bits, all zero. Units check: "5 apples, zero times" = no apples. ✓

---

Example 2 — Multiply by a power of two · Cell C2

Forecast: $4=2^2$. What do you expect multiplying by $2^2$ to look like physically?

1. Locate the single 1 in $B$. Only $b_2=1$; $b_0=b_1=b_3=0$. Why this step? A partial product $P{P}_j$ is nonzero only where $b_j=1$. With one $1$, only one partial product survives.
2. $P{P}_2=A$ shifted left by $2$. $a_i\wedge b_2=a_i$, so $P{P}_2=1101$, placed starting at column $2^2$. Why this step? The master formula weights $P{P}_j$ by $2^j$; shifting a binary number left by $j$ columns multiplies it by $2^j$.
3. No summing needed — only one row is nonzero. Why this step? Adders exist to combine multiple partial products; with a lone survivor there is nothing to add.
4. Product: $1101$ shifted left by $2=110100_2=52$.

Verify: $13\times 4=52$, and $110100_2=32+16+4=52$. ✓ Multiplying by a power of two is purely a shift — the deepest reason binary multiply is easy.

---

Example 3 — Generic mixed bits · Cell C3

Forecast: predict which of the four AND products (Figure s01) are $1$.

1. Fill the four ANDs. $a_1{a}_0=11$, $b_1{b}_0=10$. $a_0{b}_0=1\wedge 0=0,a_1{b}_0=1\wedge 0=0,a_0{b}_1=1\wedge 1=1,a_1{b}_1=1\wedge 1=1.$ Why this step? Each dot in Figure s01 is one AND; we evaluate them so we know which dots are "lit".
2. Column $2^0$: only $a_0{b}_0=0$ → $P_0=0$. Why this step? $P_0$ has just one bit and it is $0$; nothing to add.
3. Column $2^1$: bits $a_1{b}_0=0$ and $a_0{b}_1=1$. Half adder (two bits, no carry in): $s=0\oplus 1=1$, $c_1=0\wedge 1=0$ → $P_1=1$. Why this step? Two bits and no incoming carry is exactly the half-adder situation defined above.
4. Column $2^2$: bit $a_1{b}_1=1$ plus carry $c_1=0$ → $P_2=1$, $c_2=0$.
5. Column $2^3$: just $c_2=0$ → $P_3=0$.
6. Product: $P_3{P}_2{P}_1{P}_0=0110_2=6$.

Verify: $3\times 2=6=0110_2$. ✓ Matches the parent note's Worked Example 1.

---

Example 4 — All-ones, worst carrying · Cell C4

Forecast: with all four dots lit, which columns overflow?

1. All four ANDs $=1$ (Figure s02 lights every dot). Why this step? Both operands are all-ones, so $a_i\wedge b_j=1\wedge 1=1$ for every pair — the busiest possible grid.
2. Column $2^0$: single bit $a_0{b}_0=1$ → $P_0=1$, no carry.
3. Column $2^1$: two bits $a_1{b}_0=1$, $a_0{b}_1=1$. Half adder: $1\oplus 1=0$, carry $1\wedge 1=1$ → $P_1=0$, $c_1=1$. Why this step? $1+1=10_2$: the column can hold only one bit, so the "10" writes $0$ and carries a $1$ up — exactly decimal carrying.
4. Column $2^2$: bit $a_1{b}_1=1$ plus carry $c_1=1$. Full adder (now a carry enters): $1\oplus 1=0$, carry $=1$ → $P_2=0$, $c_2=1$.
5. Column $2^3$: just $c_2=1$ → $P_3=1$.
6. Product: $1001_2=9$.

Verify: $3\times 3=9=1001_2$. ✓ Matches the parent's Worked Example 2.

---

Example 5 — Maximum value / width check · Cell C5

Forecast: guess whether the top bit (weight $2^7$) is set.

1. Compute the value directly: $15\times 15=225$. Why this step? We only need the magnitude to test the width bound; the bit-by-bit ripple is the same all-ones pattern as C4, just wider.
2. Convert: $225=128+64+32+1=11100001_2$. Why this step? Reading the bits tells us how many columns are occupied.
3. Count bits: $11100001_2$ has $8$ bits. The ceiling is $n+m=4+4=8$. ✓ Why this step? The parent's bound says $P<2^{n+m}$; $225<256=2^8$, so $8$ bits always suffice and here we hit the top.

Verify: $15\cdot 15=225$, $225<256$, and $\lfloor {\log }_{2}225\rfloor +1=8$ bits. ✓ Matches the parent's Worked Example 3.

---

Example 6 — Non-square $n\ne m$ · Cell C6

Forecast: how many partial-product rows, and how wide is the answer?

1. Two rows (one per bit of $B$): $P{P}_0$ for $b_0$, $P{P}_1$ for $b_1$. Each row is $n=3$ bits wide. Why this step? Number of rows $=m$ (the multiplier's width); row width $=n$.
2. $P{P}_0$ ($b_0=1$): $A\wedge 1=110$, no shift → $110_2$.
3. $P{P}_1$ ($b_1=1$): $A\wedge 1=110$, shift left by $1$ → $1100_2$. Why this step? $P{P}_1$ carries weight $2^1$; shifting left by $1$ column applies that weight.
4. Add the two rows with a small ripple adder: $\begin{array}{r}0110\\ +1100\\ 10010\end{array}$ Why this step? The two surviving rows are summed exactly like a Ripple Carry Adder; carries propagate left.
5. Product: $10010_2=18$. Width $=n+m=3+2=5$ bits. ✓

Verify: $6\times 3=18=10010_2$, and it occupies $5$ bits $=3+2$. ✓

---

Example 7 — Real-world word problem · Cell C7

Forecast: how many bits will the address counter need to reach this total?

1. Encode the operands: $5=101_2$, $6=110_2$ (both $n=m=3$). Why this step? The multiplier works on bits; we translate the story's decimals first.
2. Partial products (only $b$'s $1$-bits matter: $b_1,b_2=1$, $b_0=0$):
   • $P{P}_1$: $A$ shifted left $1$ = $1010=1010_2$
   • $P{P}_2$: $A$ shifted left $2$ = $10100=10100_2$ Why this step? $b_0=0$ kills $P{P}_0$ (a C1-style zero row); the other two carry weights $2^1,2^2$.
3. Sum the two rows: $\begin{array}{r}01010\\ +10100\\ 11110\end{array}$ Why this step? Summing shifted partial products is the "ADD stacks it" half of the multiplier.
4. Product: $11110_2=30$ bytes.

Verify: $5\times 6=30$ bytes $=11110_2$. Units: (bytes/row)$\times$(rows) $=$ bytes — the "rows" cancel, so a byte count is correct. $30<32=2^5$, so a $5$-bit counter suffices. ✓

---

Example 8 — Exam twist: carry into a carry · Cell C8

Forecast: which column has the most bits stacked?

1. Rows ($b_0=1$, $b_1=0$, $b_2=1$):
   • $P{P}_0=111$ (no shift)
   • $P{P}_1=000$ (since $b_1=0$ — a zero row)
   • $P{P}_2=111$ shifted left $2$ = $11100$ Why this step? Two nonzero rows land with an overlap; we set up the column stacking.
2. Stack by column (weights $2^4{2}^3{2}^2{2}^1{2}^0$): $\begin{array}{r}00111\\ +11100\end{array}$ Column $2^2$ receives $1$ (from $P{P}_0$) $+1$ (from $P{P}_2$) $=10_2$: write $0$, carry into $2^3$. Why this step? This is the "hot" column — the overlap of the two rows.
3. Column $2^3$: original $1$ (from $P{P}_2$) $+$ carry $1=10_2$: write $0$, carry into $2^4$. This is the twist — the carry created its own carry. Why this step? An incoming carry pushed a $1+1$ into another $10$, so the overflow propagates — a full-adder chain, not a single half adder.
4. Column $2^4$: carry $1$ → bit $1$.
5. Assemble: result $=100011_2$.

Verify: $7\times 5=35=100011_2$ ($32+2+1$). The double-overflow column is $2^2\to 2^3$. ✓ This "carry begets carry" is precisely why deep columns need full adders, not half adders.

---

Example 9 — Signed / degenerate: a negative operand · Cell C9

Forecast: guess whether the array gives $-15$ or something else entirely.

1. The array is blind to sign — it just does $\sum (a_i\wedge b_j)2^{i+j}$ on the bit patterns. So it multiplies $1101_2$ as if it were the unsigned value $13$. Why this step? The AND gate has no notion of a sign bit; it treats the top bit as weight $2^3$, positive.
2. Unsigned result: $13\times 5=65=1000001_2$. Why this step? We compute what the hardware literally produces so we can compare to the intended answer.
3. Intended answer: $-3\times 5=-15$, which in $8$-bit two's complement is $11110001_2$. Why this step? This is the correct signed product; it disagrees with step 2 — the naive array is wrong for signed inputs.
4. Why it fails: two's complement treats the top bit as weight $-2^3$, but the AND array treats it as $+2^3$. That single sign flip corrupts every partial product touching bit $3$. Why this step? Identifies the root cause — a weighting mismatch, not a wiring bug.
5. The fix: either (a) sign-extend both operands to the full $n+m$ width and use signed adders, or (b) use Booth's Algorithm, which recodes the multiplier so runs of $1$s become one subtraction, correctly handling the negative weight. Why this step? These are the standard remedies; Booth is the one the parent note flags for signed numbers.

Verify: unsigned array output $13\times 5=65$; the intended signed value $-3\times 5=-15$. These differ, confirming the naive array is invalid for signed operands. ✓

---

Recall Quick self-test across the matrix

Zero operand → product? ::: $0$; no AND fires (C1). Multiply by $2^k$ costs how many adders? ::: None — it is a pure left shift (C2). All-ones input triggers what worst case? ::: Longest carry ripple → $\mathcal{O}(n)$ delay (C4). $15\times 15$ fits in how many bits? ::: $8=n+m$ (C5). Non-square $3\times 2$: rows and product width? ::: $2$ rows, $5$-bit product (C6). Feeding two's-complement bits to an unsigned array gives? ::: A wrong answer; needs sign-extension or Booth (C9).

---

Connections

• Combinational multipliers — parent topic
• AND Gate — forms every partial-product bit
• Half Adder / Full Adder — the summing cells (half where no carry enters)
• Ripple Carry Adder — the carry chain summing rows (Ex. 6)
• Carry Save Adder / Wallace Tree — beat the C4 worst-case delay
• Binary Number System — positional weights $2^{i+j}$
• Booth's Algorithm — the fix for the signed case (C9)
• Combinational Circuits — no clock, product falls out after gate delay