How many AND gates are required to construct a 4-bit parallel multiplier if…

Concept

A parallel (array) binary multiplier multiplies two n-bit numbers in two stages: partial-product generation, where every bit of one operand is ANDed with every bit of the other operand using 2-input AND gates to form an n × n grid of product bits, and partial-product summation, where the shifted rows of that grid are added together using adders.

The AND-gate count needed for the partial-product stage is always n² for two n-bit operands, independent of how the summation stage is built — so once the adders for summation are supplied, only the AND-gate stage remains to be counted.

Application

Applying this to the given 4-bit × 4-bit multiplier, with four 4-bit parallel adders already supplied:

1. Label the two 4-bit operands as A = a3 a2 a1 a0 and B = b3 b2 b1 b0.

2. Partial-product generation: form every product bit ai·bj with one 2-input AND gate — one gate per (ai, bj) pair.

3. A has 4 bits and B has 4 bits, so the number of (ai, bj) pairs is 4 × 4 = 16; this stage therefore needs 16 two-input AND gates.

4. Partial-product summation: the four 4-bit parallel adders already given in the question sum the 16 partial-product bits (arranged as 4 shifted rows), so no extra gates are needed for this stage.

5. Only the AND-gate stage still needs to be built, so the construction requires 16 two-input AND gates in total.

The 16 partial-product bits form a 4-row × 4-column grid, one AND gate per cell:

Cross-check

Cross-check: for a general n-bit × n-bit array multiplier, the partial-product stage always needs n² two-input AND gates, regardless of the summation scheme used afterward. Substituting n = 4 gives 4² = 16, matching the count obtained directly from the (ai, bj) grid above.