Combinational multipliers: Foundations — Hardware deep dive

This page assumes you know nothing beyond counting. We will build every symbol the parent note throws at you — $a_{i}$ , $2^{i}$ , $\sum$ , $\land$ , $\oplus$ , "shift", "carry" — one brick at a time, each with a picture, before it is ever used in anger.

1. What a binary digit even is

Why does hardware love this? Because a wire is easy to build with exactly two states — low voltage or high voltage. So every number inside a chip is a row of switches.

Compare it to the decimal digits you know: a decimal digit has ten choices ( $0$ through $9$ ); a bit has only two. That is the only difference, and it makes everything simpler, as you will see.

See Binary Number System for the full number system; here we only need enough to read the parent note.

2. Column weights — the meaning of $2^{i}$

You already know decimal column weights without naming them. In the number $305$ :

the $5$ sits in the "ones" column, worth $1 0^{0} = 1$ ,
the $0$ sits in the "tens" column, worth $1 0^{1} = 10$ ,
the $3$ sits in the "hundreds" column, worth $1 0^{2} = 100$ .

So $305 = 3 \times 100 + 0 \times 10 + 5 \times 1$ . Each column is ten times the one to its right.

Binary does the exact same thing, but each column is two times the one to its right.

Why the topic needs this. The whole multiplier formula ends in a factor $2^{i + j}$ . That factor is a pure column address — it tells the circuit which column a bit belongs in. You cannot read the master formula without reading $2^{i}$ as "which column."

3. The subscript notation $a_{i}$ and $b_{j}$

The parent note writes a number as $A = a_{n - 1} \dots a_{1} a_{0}$ . That looks scary; it is just naming each bit by its column number.

So the binary number $1011$ has $a_{3} = 1, a_{2} = 0, a_{1} = 1, a_{0} = 1$ , and its value is $1 \cdot 2^{3} + 0 \cdot 2^{2} + 1 \cdot 2^{1} + 1 \cdot 2^{0} = 8 + 0 + 2 + 1 = 11.$

4. What $n$ and $m$ mean, and "width"

Why does the last column have subscript $n - 1$ and not $n$ ? Because we start counting at $0$ . If you have $n$ columns and the first is column $0$ , the last is column $n - 1$ . (Four columns: $0, 1, 2, 3$ — the last is $3 = 4 - 1$ .)

Why the topic needs it. The famous result " $n$ -bit × $m$ -bit needs $n + m$ bits" is pure width bookkeeping. You must be comfortable that "width" counts columns and that counting starts at zero.

5. The sum symbol $\sum$ — long addition written short

The parent writes $A = \sum_{i = 0}^{n - 1} a_{i} 2^{i}$ . This is the same column expansion we just did, only compressed.

Unrolled for $n = 4$ : $\sum_{i = 0}^{3} a_{i} 2^{i} = a_{0} 2^{0} + a_{1} 2^{1} + a_{2} 2^{2} + a_{3} 2^{3} .$

That is exactly the column expansion of section 3 — nothing new, just a shorthand so we don't have to write "and so on."

In the figure, each grid cell is one pair $(i, j)$ ; the double sum simply promises to touch every cell. That grid is the array multiplier's layout.

6. The AND operation $\land$ — "copy or zero"

Now the punchline the parent leans on: multiply two single bits and you get the AND table. $0 \times 0 = 0$ , $0 \times 1 = 0$ , $1 \times 0 = 0$ , $1 \times 1 = 1$ . Identical. So for bits, $a_{i} \times b_{j} = a_{i} \land b_{j} .$

See AND Gate for the physical gate. Do not confuse this with XOR (next section) — that is the single most common mistake in the parent note.

7. The XOR operation $\oplus$ and "carry" — how a column adds

Forming products was multiplication (AND). Summing the products is addition, and one-bit addition needs two new ideas.

Look at the last row: $1 + 1$ . In binary that is $1 0_{2}$ — a $0$ in this column and a $1$ that must move to the next column left. That moved bit is the carry.

8. "Shift left by $j$ " — the meaning of the $2^{i + j}$ factor

On paper you slide each row one place left as you go down. "Sliding one place left" is exactly "multiply by the base."

Example: $1 1_{2} = 3$ . Shift left by $1$ : $11 0_{2} = 6 = 3 \times 2$ . Shift left by $2$ : $110 0_{2} = 12 = 3 \times 4$ .

Why the topic needs it. The multiplier's row $j$ (its partial product $P P_{j}$ ) is worth $2^{j}$ times more than row $0$ , so it must be planted $j$ columns further left before adding. In the master formula this is the exponent piece: $2^{i + j} = 2^{i} \cdot 2^{j}$ — the column of bit $a_{i}$ ( $= 2^{i}$ ) shifted by the row's weight ( $2^{j}$ ).

9. Big-O notation $O (\cdot)$ — a size label, not a number

The parent claims delay is $O (n)$ and cost is $O (n^{2})$ .

Why the topic needs it. It lets us compare designs without wiring them up: an array multiplier is $O (n)$ delay / $O (n^{2})$ area, while a Wallace Tree cuts delay to $O (lo g n)$ . The grid picture makes both obvious: area = number of cells ( $n \times n$ ); delay = length of the longest path across the grid (about $n$ ).

How the foundations feed the topic

Every arrow says "you need the left idea to understand the right one." Multiplication sits where copy-or-zero (AND), add-with-carry (XOR), shift by weight, and sum over a grid meet.

Equipment checklist

Read a binary number's value from its bits

Multiply each bit by its column weight

2^{i}

and add:

101 1_{2} = 8 + 0 + 2 + 1 = 11

Meaning of the subscript in

a_{2}

The bit of

A

in column

2

, which has weight

2^{2} = 4

Why the top bit of an

n

-bit number is

a_{n - 1}

not

a_{n}

Columns are counted from

0

, so

n

columns end at index

n - 1

Unroll

\sum_{i = 0}^{2} a_{i} 2^{i}

a_{0} 2^{0} + a_{1} 2^{1} + a_{2} 2^{2}

What does the double sum

\sum_{i} \sum_{j}

visit

Every pair

(i, j)

exactly once — every cell of the grid.

Truth value of

1 \land 0

and why AND = single-bit multiply

1 \land 0 = 0

; the AND table matches

x \times y

for bits exactly.

Sum bit and carry when adding

1 + 1

Sum

= 1 \oplus 1 = 0

, carry

= 1 \land 1 = 1

(result

1 0_{2}

Value of

3

shifted left by

2

, and why

12

, because shifting left by

2

multiplies by

2^{2} = 4

What

O (n^{2})

tells you when

n

doubles

The quantity grows roughly four-fold (area-like growth).

Which operation forms a partial product, which one sums them

AND (

\land

) forms products; XOR (

\oplus

) with carry sums them.

Connections

Parent: Combinational multipliers — the topic these foundations unlock
Binary Number System — column weights $2^{i}$ built here
AND Gate — the copy-or-zero switch
Half Adder / Full Adder — the sum + carry cells
Combinational Circuits — the family (no clock, no memory)

$x$	$y$	$x \oplus y$ (sum bit)	$x \land y$ (carry)
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1