Combinational multipliers: Question bank — Hardware deep dive

Recap you must have loaded first (self-contained)

Before the traps, here is every symbol this page uses, defined from zero so you never need to leave the note.

True or false — justify

Forming a partial-product bit

a_{i} b_{j}

uses an XOR gate.

False. Forming a partial product is multiplication of two single bits, whose truth table is exactly AND; XOR only appears later, inside the adders that sum the products.

n

-bit

\times

m

-bit multiplier's product fits in

max (n, m) + 1

bits.

False. Multiplication grows magnitude: the largest product is

(2^{n} - 1) (2^{m} - 1) < 2^{n + m}

, so you need up to

n + m

bits, not

max (n, m) + 1

(that bound is for addition).

A combinational multiplier needs a clock to step through each partial-product row.

False. It is pure combinational logic with no memory or clock; all rows form and add simultaneously, and the answer settles after a fixed gate delay.

Every column in the summing grid needs a full adder.

False. A column with only two bits and no incoming carry (like column

2^{1}

in a

2 \times 2

) needs only a Half Adder; full adders are for columns that also receive a carry.

If a multiplier bit

b_{j} = 0

, its whole partial product

P P_{j}

is zero.

True. Every bit of

P P_{j}

a_{i} \land b_{j}

, and ANDing anything with

0

gives

0

, so the entire shifted row is zeros and contributes nothing.

Shifting a partial product left by

j

is optional as long as you add carefully.

False. The shift is the arithmetic:

P P_{j}

carries weight

2^{j}

(the

2^{i + j}

in the master formula). Adding rows unshifted computes a different, wrong number.

An array multiplier and a Wallace Tree multiplier compute different products.

False. Both compute the identical product

\sum_{i, j} (a_{i} \land b_{j}) 2^{i + j}

; they differ only in how fast they sum — array is

O (n)

depth, Wallace is

O (lo g n)

Doubling the operand width

n

roughly doubles the gate count of an array multiplier.

False. Gate count is

O (n^{2})

(one AND per bit pair plus a per-cell adder), so doubling

n

roughly quadruples the gate count.

The AND Gate grid alone is enough to output the product.

False. The ANDs only form the

n \times m

partial-product bits; you still need adders to collapse each column (with carries) into a single product bit

P_{k}

An unsigned array multiplier gives the correct result if you feed it two's-complement negatives unchanged.

False. A two's-complement number's MSB has weight

- 2^{n - 1}

, but the unsigned grid treats it as

+ 2^{n - 1}

, so the products of sign bits land in the wrong (positive) columns; you need sign correction or Booth's Algorithm.

Spot the error

"Column

2^{0}

of a

2 \times 2

multiplier needs a half adder."

Wrong — column

2^{0}

holds only the single bit

a_{0} b_{0}

, so

P_{0} = a_{0} b_{0}

directly. With one bit and nothing to add, no adder is needed at all.

"To multiply by

2

we AND with the constant

1 0_{2}

Wrong — multiplying by

2 = 2^{1}

is a left shift by one column, not an AND. AND forms a single-bit product; the power-of-two factor is handled by wiring/shifting.

"An

n \times n

array multiplier has

O (lo g n)

delay because adders are fast."

Wrong — the array's worst-case path is the carry rippling along the diagonal and bottom carry chain, both length

\sim n

, giving

O (n)

delay.

O (lo g n)

requires a carry-save/tree structure.

P_{1} = a_{1} b_{0} \land a_{0} b_{1}

in the

2 \times 2

multiplier."

Wrong —

P_{1}

is the output bit of column

2^{1}

, which has two bits being added, so it is the XOR sum:

P_{1} = a_{1} b_{0} \oplus a_{0} b_{1}

. The AND of those two bits is the carry

c_{1}

into column

2^{2}

, not the sum.

15 \times 15

(4-bit) can overflow 8 bits, so we need 9 output bits."

Wrong —

15 \times 15 = 225 = 1110000 1_{2} < 256 = 2^{8}

, so it fits in exactly

n + m = 8

bits. The product is always strictly below

2^{n + m}

, so 8 bits never overflow.

"Since

1 + 1 + 1 = 1 1_{2}

can occur in a column, we must add three bits with an XOR."

Wrong — a single Full Adder adds exactly three bits (two operands + one carry-in

c_{k}

) and outputs a sum bit

P_{k}

and a carry-out. A bare XOR only handles two bits and produces no carry.

"Booth's algorithm is needed for any array multiplier."

Wrong — plain array multipliers work directly for unsigned magnitudes. Booth's Algorithm is a technique to handle signed numbers and reduce the count of partial products; it is not mandatory for the basic unsigned circuit.

"For signed multiplication just multiply magnitudes and copy the wider operand's width."

Wrong — a signed

n \times n

product still needs

2 n

bits, and you must handle the sign separately (magnitude+sign, sign extension of partial products, or Booth); copying a single operand width loses both magnitude and sign information.

Why questions

Why is a single-bit multiply exactly an AND gate?

Because

1 \times 1 = 1

and every other combination is

0

— that truth table matches AND identically, so

a_{i} \cdot b_{j} = a_{i} \land b_{j}

Why does the exponent

2^{i + j}

appear in the master formula?

a_{i}

sits in column

2^{i}

A

and

b_{j}

in column

2^{j}

B

; multiplying their weights gives

2^{i} \cdot 2^{j} = 2^{i + j}

, which tells you exactly which output column

P_{i + j}

the bit lands in.

Why do carries

c_{k}

exist at all in a multiplier?

Each output column can hold only one bit

P_{k}

, so when a column's bits sum to

2

or more, the excess must "overflow" into the next-higher-weight column — identical to carrying in decimal long multiplication.

Why is the AND-gate count

O (n^{2})

Every pair

(a_{i}, b_{j})

needs its own AND, and there are

n \times m

such pairs; for

n = m

that is

n^{2}

, so the count grows with the square of the width.

Why is the array multiplier's delay

O (n)

and not

O (n^{2})

Delay is set by the longest single path, not total gate count: a signal crosses the diagonal (

\sim n

cells) and then the carry chain (

\sim n

cells), summing to

\sim 2 n

— linear, even though there are

n^{2}

gates working in parallel.

Why does the array multiplier trade area for speed?

It uses many gates (

O (n^{2})

) to compute the whole product in one combinational pass, avoiding the many clock cycles a repeated-addition loop would take — more hardware, but a single fixed delay.

Why do deeper columns use full adders while the first shared column can use a half adder?

A half adder sums only two bits with no carry-in; inner columns receive a carry

c_{k}

propagated from the previous column, so they need a full adder that accepts that third (carry-in) bit.

Why does a Wallace tree beat an array multiplier on delay but not on the number of AND gates?

Both need the same

n \times m

AND gates to form partial products; the tree only reorganizes the summation into

O (lo g n)

depth, so it wins on adder-chain delay, not on the AND count.

Why can't you just widen an unsigned multiplier to handle negatives?

Widening keeps the MSB weight positive (

+ 2^{n - 1}

), but a two's-complement negative needs that weight to be

- 2^{n - 1}

; the sign has to be interpreted, not just given more bits — hence sign correction or Booth.

Edge cases

Multiplying any number by

B = 0

: what does the circuit output and why?

All partial products vanish (

a_{i} \land 0 = 0

for every bit), so every column is zero and the product is

0

— the correct result with no special-case logic needed.

Multiplying by

B = 1

: what happens to the partial products?

Only

P P_{0}

is nonzero and equals

A

unshifted (each bit

a_{i} \land 1 = a_{i}

); all other rows are zero, so the product is just

A

Multiplying by a power of two, e.g.

B = 10 0_{2}

: what does the multiplier effectively do?

Only

b_{2} = 1

, so a single partial product

P P_{2} = A

appears, shifted left by 2 columns — the circuit reduces to a pure left shift by 2, matching "multiply by

2^{2}

The

1 \times 1

(single-bit

\times

single-bit) multiplier: what is its entire circuit?

One AND gate producing

a_{0} \land b_{0}

; there is nothing to shift and no column to add, so no adders are required at all.

What is the maximum product of two

n

-bit numbers, and does it ever reach exactly

2^{2 n}

The maximum is

(2^{n} - 1)^{2} = 2^{2 n} - 2^{n + 1} + 1

, which is strictly less than

2^{2 n}

— so

2 n

output bits always suffice and the top bit is never forced to overflow.

Both operands equal to all-ones (

A = B = 11 \dots 1

): why is this the worst case for both value and carries?

Every

a_{i} \land b_{j} = 1

, so every partial-product bit is set; the columns are maximally full, forcing the longest carry propagation and producing the largest product

(2^{n} - 1)^{2}

Signed edge case: what is the two's-complement product of the most-negative operand times itself, e.g.

- 8 \times - 8

in 4 bits?

- 8 \times - 8 = + 64

, which needs

8 = 2 n

bits (

64 = 0100000 0_{2}

); the result is positive and fits, but the two negatives' sign bits (weight

- 2^{3}

each) must be interpreted correctly, or the unsigned grid would compute

8 \times 8 = 64

only by luck of both being treated positive — for mixed signs it fails without correction.

Signed edge case: multiplying a positive by a negative — where does the naive unsigned grid go wrong?

The negative operand's MSB is read as

+ 2^{n - 1}

instead of

- 2^{n - 1}

, so one partial product is added instead of subtracted; the fix is sign extension of the partial products or Booth encoding to make the subtraction happen.

Connections

AND Gate — the trap "XOR forms partial products" lives here
Half Adder / Full Adder — the "which adder in which column" traps
Ripple Carry Adder — why array delay is $O (n)$
Carry Save Adder / Wallace Tree — the $O (lo g n)$ alternative
Binary Number System — positional weights $2^{i}$ behind $2^{i + j}$
Booth's Algorithm — signed / two's-complement multiplication trap
Combinational Circuits — parent topic (no memory/clock)