Combinational multipliers: Visual walkthrough — Hardware deep dive

We use a running example the whole way: $A = 3$ , $B = 3$ , both written in binary as $1 1_{2}$ . If you can multiply $3 \times 3$ with gates, you understand the machine.

Step 1 — What "multiply" means before any gates

WHAT. Before binary, before AND, let us just recall grade-school long multiplication in the number system we grew up with: base ten. We line up the numbers, multiply the top by each bottom digit, slide each result one column left, and add.

WHY. Every trick a hardware multiplier uses is already hiding in this paper method. If we name the pieces now — partial product, shift, column add, carry — the circuit later is just those pieces made of switches.

PICTURE. Look at Step Figure 1. The top number is multiplied by the ones digit (giving one row), then by the tens digit (giving a second row, shifted one place left). The two rows stack, and each column is added with carries.

Symbol check — we have not used a single strange symbol yet. Just "row", "shift", "add".

Step 2 — Why binary makes every row trivial

WHAT. Now switch the base from ten to two. In binary every digit is either $0$ or $1$ — nothing else exists.

WHY. In base ten, "top number times a digit" could be $\times 7$ , a real multiplication. In base two, "top number times a digit" is only ever:

times $1$ → copy the top number, or
times $0$ → write all zeros.

That is the whole reason binary multiplication is cheap: no multiplication table is needed, only copy-or-zero.

PICTURE. Step Figure 2 shows our example $A = 1 1_{2}$ (that is $3$ ) multiplied by each bit of $B = 1 1_{2}$ . Because both bits of $B$ are $1$ , both partial products are just a copy of $A$ : the first row is $11$ , the second row is $11$ shifted one column left.

Step 3 — One partial-product bit is exactly one AND gate

WHAT. Zoom into a single cell of a row. That cell is "one bit of the top number, times one bit of the bottom number": the product $a_{i} \cdot b_{j}$ of two single bits.

WHY this tool — the AND gate, not XOR, not OR. Ask: when is the single-bit product $a_{i} \cdot b_{j}$ equal to $1$ ? Only when both are $1$ , because $1 \times 1 = 1$ and every other combination gives $0$ . Write that truth table out and it matches one gate exactly — the AND gate, whose output is $1$ only when both inputs are $1$ . So the arithmetic $a_{i} \cdot b_{j}$ is the logic $a_{i} \land b_{j}$ . (XOR would be wrong — it fires on $0, 1$ too — and XOR belongs later, when we add.)

PICTURE. Step Figure 3 puts the multiplication truth table next to the AND-gate truth table so you can see they are the same four rows.

See AND Gate for the gate itself.

Step 4 — Placing each AND result in its column (the weight $2^{i + j}$ )

WHAT. Every AND result must go into a column. Which one? Bit $a_{i}$ carries weight $2^{i}$ , bit $b_{j}$ carries weight $2^{j}$ . When you multiply them, the weights multiply: $2^{i} \cdot 2^{j} = 2^{i + j}$ . So the product $p_{ij}$ lands in the column of weight $2^{i + j}$ .

WHY. This is the single line that turns "long multiplication on paper" into an exact wiring diagram: the exponent $i + j$ is the column number, and column number $=$ how many places you shifted. No shifting is done "by hand" — the geometry of the grid does it.

PICTURE. Step Figure 4 is the placement grid for the $2 \times 2$ multiplier. Each of the four AND outputs $p_{00}, p_{10}, p_{01}, p_{11}$ is dropped into its column $2^{0}, 2^{1}, 2^{1}, 2^{2}$ . Notice two bits land in column $2^{1}$ — that is where addition will be forced.

Positional weights come from the Binary Number System.

Step 5 — Adding a column: the half adder appears

WHAT. Column $2^{1}$ holds two bits: $p_{10} = a_{1} b_{0}$ and $p_{01} = a_{0} b_{1}$ . We must add them. Adding two single bits can produce $1 + 1 = 1 0_{2}$ — a result that needs two output bits: a sum bit that stays here, and a carry bit that moves one column left.

WHY this tool — a half adder. Two inputs, no incoming carry from a lower column: that is precisely a half adder. Its two outputs are built from two gates you already know:

sum $= a_{1} b_{0} \oplus a_{0} b_{1}$ (the XOR gate — output $1$ when the inputs differ, i.e. exactly one is $1$ : that is " $1 + 0$ or $0 + 1 \to 1$ ", and " $1 + 1 \to 0$ with a carry"),
carry $= a_{1} b_{0} \land a_{0} b_{1}$ (AND — a carry happens only when both were $1$ ).

Now XOR is earned. Notice XOR shows up only here, inside adding — never in forming products. That is the whole "multiply = AND, add = XOR" distinction the parent warned about.

PICTURE. Step Figure 5 shows the two bits of column $2^{1}$ entering a half adder, the XOR producing the sum bit that stays, and the AND producing the carry that shoots left into column $2^{2}$ .

See Half Adder and Full Adder for the summing cells.

Step 6 — Full adder where a carry arrives (deeper columns)

WHAT. Column $2^{2}$ is different. It holds the product bit $p_{11} = a_{1} b_{1}$ and the carry that arrived from column $2^{1}$ . That is three things to add potentially (in bigger multipliers, up to three), and there is an incoming carry.

WHY this tool — a full adder. A half adder only takes two inputs; it has no slot for an incoming carry. The moment a column receives a carry from below, you need a full adder: three inputs (the two bits plus carry-in), two outputs (sum + carry-out). That is why the parent says "half adders where no carry enters, full adders elsewhere."

PICTURE. Step Figure 6 shows column $2^{2}$ : the AND product $a_{1} b_{1}$ and the incoming carry $c_{1}$ feeding a full adder, producing $P_{2}$ (stays) and $c_{2}$ (moves to column $2^{3}$ ).

Step 7 — Watch $3 \times 3$ compute, column by column

WHAT. Put numbers in. With $a_{1} = a_{0} = b_{1} = b_{0} = 1$ , every AND $p_{ij} = 1$ . Now walk the columns right to left.

WHY. This is the moment the abstract grid becomes an actual number. Every carry you see is a real "1+1 overflowed" moment, exactly like decimal.

Column $2^{0}$ : only $p_{00} = 1$ . Nothing to add $\Rightarrow P_{0} = 1$ .
Column $2^{1}$ : $p_{10} + p_{01} = 1 + 1 = 1 0_{2}$ . Half adder: $P_{1} = 0$ , carry $c_{1} = 1$ .
Column $2^{2}$ : $p_{11} + c_{1} = 1 + 1 = 1 0_{2}$ . Full adder: $P_{2} = 0$ , carry $c_{2} = 1$ .
Column $2^{3}$ : only $c_{2} = 1 \Rightarrow P_{3} = 1$ .

Reading top bit to bottom bit: $P = P_{3} P_{2} P_{1} P_{0} = 100 1_{2} = 9$ . And indeed $3 \times 3 = 9$ . ✓

PICTURE. Step Figure 7 animates the carry cascade: two carries march left, each column collapses to one output bit, and the amber answer $1001$ appears along the bottom.

Step 8 — The edge cases you must never trip on

WHAT. A derivation is only trustworthy if it survives the weird inputs. Three of them:

Multiply by zero. Let $B = 0$ , so $b_{0} = b_{1} = 0$ . Then every AND $a_{i} \land 0 = 0$ : all partial products vanish, and $P = 0$ . Why it works: AND with $0$ is always $0$ — the "write all zeros" case from Step 2 handled automatically, no special circuitry.
The smallest carry-free case. $A = 1$ , $B = 1$ : only $p_{00} = 1$ , no column ever has two bits, so no adder ever fires. The product is a single wire. This proves the adders are only there for column collisions.
The width bound / largest product. For $n$ -bit numbers the biggest inputs are all-ones. In our $2 \times 2$ world that is $3 \times 3 = 9 = 100 1_{2}$ — 4 bits $= n + m = 2 + 2$ . It never overflows into a 5th column because $9 < 16 = 2^{4}$ . In general the product $< 2^{n + m}$ , so exactly $n + m$ output bits suffice — never fewer.

WHY these matter. Zero tests the degenerate input; $1 \times 1$ tests the no-adder minimum; all-ones tests the maximum width. Between them they show the machine can never surprise you.

PICTURE. Step Figure 8 lines up all three edge cases side by side: an all-dark grid ( $\times 0$ ), a single-lit cell ( $1 \times 1$ ), and the full grid pushing right up to bit $2^{3}$ but never past it ( $3 \times 3$ ).

The one-picture summary

The whole array multiplier is: AND makes the bits, columns place them, adders stack them, carries pace them.

Recall Feynman retelling of the whole walkthrough

Imagine multiplying $3 \times 3$ on paper. You write the top number once for each $1$ in the bottom number, sliding each copy one step left, then add the stacked copies. Binary makes each copy trivial: a bottom bit of $1$ says "copy", a $0$ says "all zeros" — and that copy-or-zero decision for a single bit is one little AND switch. Now every copied bit sits in some column; the column number is just how far you slid, which is why the maths writes it as $2^{i + j}$ . When a column has two bits stacked, you add them: $1 + 1$ makes $0$ here and a $1$ carried one column left — a half adder does exactly that (XOR for the digit that stays, AND for the carry). If a column also catches an incoming carry, you need a full adder, which has room for that extra input. Feed $3 \times 3$ in: every switch turns on, two carries march leftward, and the columns collapse to $1001$ , which is $9$ . Turn a bottom number to zero and every switch goes dark — the answer is zero for free. Make both numbers just $1$ and no adder fires at all — a single wire is the product. And the widest the answer can ever get is $n + m$ bits, because even all-ones times all-ones stays just under $2^{n + m}$ .

Connections

Combinational multipliers — parent topic this page drills into
AND Gate — Step 3, forms every partial-product bit
Half Adder — Step 5, adds a two-bit column
Full Adder — Step 6, adds a column that also receives a carry
Ripple Carry Adder — Step 6/7, the carry chain that sets the delay
Carry Save Adder / Wallace Tree — faster ways to stack the columns
Binary Number System — Step 4, positional weights $2^{i + j}$
Booth's Algorithm — reduces the partial-product count for signed numbers
Combinational Circuits — no clock, no memory: the answer just settles
🇮🇳 Yeh Hinglish mein padho →